teaching machines

CS 330: Lecture 23 – Haskell

April 2, 2018 by . Filed under cs330, lectures, spring 2018.

Dear students,

This class has hit upon two overall themes so far this semester. The first theme was the recognition and interpretation of a programming language. The second theme was types, which brought with it ideas about object orientation and static vs. dynamic decision-making. The third theme of the semester is functional programming, which has two distinctive qualities that separate it from the imperative programming of C++ and Java:

  1. Functions can be treated as values. They can be assigned to variables. They can be passed as parameters to functions. They can be returned from functions.
  2. We focus on mathematical truths and less on the manipulation of the underlying hardware. The notions of time and mutable state are gone. Manifestations of imperative thinking include loops and pointers; these go away.

The lens we will use to examine functional programming is Haskell. This language is probably very different from other languages you have used. You might not ever use it again after this class. But you know how sometimes it takes extremist revolutionaries to bring about even the smallest of changes? Haskell will be this for us, and we will listen to its heretical ideas, shake our heads in disgust, and be changed forever.

Some of our exploration will be done in scripts and some in a REPL, a read-eval-print-loop. You’ve used a REPL for years: your calculator. It prompts the user for some, executes it, displays the result, and loops back around. We can write a REPL in Ruby like this:

print '> '
while s = gets
  ans = eval s
  puts ans
  print '> '
end

Let’s start with a discussion of values in Haskell in the ghci REPL. Haskell supports the kind of literals and operators you’d expect:

5
7 * 8
5.6
'r'
"foobag"
True
False

The compiler is smart enough to figure out the types of these values. Let’s enter them at the REPL, but first enter a mode where we see what type the REPL has detected for our expressions:

> 5
5
it :: Num p => p
> 7 * 8
56
it :: Num a => a
> 5.6
5.6
it :: Fractional p => p
> 'r'
'r'
it :: Char
> "foobag"
"foobag"
it :: [Char]
> True
True
it :: Bool
> False
False
it :: Bool

The Num and Fractional represent what’s called a typeclass. The integers and reals that you are familiar with are instances of these typeclasses. At this point, however, these literals are undifferentiated. All we know is that they support Num operations or Fractional operations. The notion of a typeclass is a lot like an interface in Java. Num describes what operations a instance of that typeclass must support. It imposes seven operations, and has many instances.

[Char] represents a list of Char, just as [Int] represents a list of Int. it is an automatic variable that holds the last result. The MATLAB folks use ans for this same purpose.

Haskell also supports a few compound types. Here’s a list:

> [1, 2, 3]
[1,2,3]
it :: Num a => [a]

Notice the type inference. The compiler sees that we have a list of a, where a is some instance of Num. What would happen if I put a real number in there?

> [1, 2, 3, 10.1]
[1.0,2.0,3.0,10.1]
it :: Fractional a => [a]

What would happen if I put a character in there?

> [1, 2, 3, 'z']

<interactive>:36:2: error:
    • No instance for (Num Char) arising from the literal ‘1’
    • In the expression: 1
      In the expression: [1, 2, 3, 'z']
      In an equation for ‘it’: it = [1, 2, 3, ....]

The compiler is trying to find a common type for all the elements, and it cannot. What does this tell you about lists in Haskell? They are homogeneous collections. Contrast this to tuples:

> (1, 'a')
(1,'a')
it :: Num a => (a, Char)
> ("Taylor Park", 19, 3.999999)
("Taylor Park",19,3.999999)
it :: (Num b, Fractional c) => ([Char], b, c)

Lists are like arrays. Tuples are like structs, except that indexing inside a struct is done with a field’s name, while indexing inside a tuple is done by the field’s position.

Haskell does have variables, but perhaps variable isn’t the best word. They can’t vary. Once you bind 5 to foo, it will always be 5. Just like in mathematics. The = truly means equals, not assignment. Let’s prove it. I’m going to write this code in a script, not in the REPL:

foo = 5
foo = 6

This fails. Interestingly, it does not fail in the REPL, which does some magic to introduce notions of time and mutability. We won’t get into that magic.

Haskell is statically typed, which means that the types of variables are known at compile time. Do you see any type declarations in there? No. Often, Haskell doesn’t need to be explicitly typed. The compiler can infer the types. There aren’t many popular languages that are both static and implicitly typed, and sometimes people have a hard time dissociating these two features. Maybe that will change now that C++ has auto and C# has var. Until that time, you need to teach them to think correctly about types. Just save your teaching for real people and not those on the web.

Let’s examine the type of foo:

> :type foo
foo :: Integer

Though the compiler can infer the types, I often find myself wanting to declare the types just to be certain I’m doing what I think I’m doing. We declare types like this:

foo :: Integer
foo = 5

That’s enough about types for now. Let’s write some functions. Here’s one:

Write a function majority, which yields the minimum number of people of some population to form a majority.

Turn to a neighbor and discuss the algorithm. How would you compute this?

In Haskell, we define functions like this:

functionName :: TypeOfFormal1 -> TypeOfFormal2 -> ... -> TypeOfReturnValue
functionName idFormal1 idFormal2 ... = expression

For majority, we’d write write something like this:

majority :: Integer -> Integer
majority = n / 2 + 1

But this doesn’t compile. The error message isn’t entirely inscrutable, but the issue is /. If we examine its type signature, we see that it returns a Fractional. Integer is not an instance of Fractional. This is why I like to declare types. If I had left out the declarations, this would have compiled just fine:

> :t majority
majority :: Fractional a => a -> a

But the inferred types wouldn’t have matched my intent.

To get integer division, we use a different operator:

majority :: Integer -> Integer
majority n = div n 2 + 1

Notice the utter lack of balanced punctuation in this language. You can breathe in Haskell.

It may be worth noting that div here looks like a function. Would you rather have an infix operator? Well, you can:

majority n = n `div` 2 + 1

I hope you’re starting to see that functions and operators are often the same thing. In C++, we saw that << was really the operator<< method.

Here’s your TODO list for next time:

See you then!

Sincerely,

P.S. It’s time for a haiku!

I tried foo-5
No good, foo soon lost its 5
foo=5 held

P.P.S. Here’s the code we wrote together:

test.hs

majority :: Integer -> Integer
majority n = div n 2 + 1

-- foo :: Double
-- foo = 5
-- foo = 6