teaching machines

CS 330 Lecture 18 – Haskell

March 13, 2017 by . Filed under cs330, lectures, spring 2017.

Dear students,

Today we begin our foray in the Haskell language, which is very different from the Java and C that you have been steeped in. I want to introduce its craziness by just solving some problems. We’ll see what we encounter.

Here are the tasks I will ask you to complete with a neighbor:

We solve these in Haskell below:

Problem 1: Let’s write a function to calculate how many people make up a majority. What do we need to know to calculate this? How do we calculate it?

Here’s our first attempt at a Haskell function:

majority n = n / 2 + 1

What happens when we run this?

> majority 100
51.0
> majority 101
51.5

We see that / doesn’t perform integer division. But we didn’t discover this until after we ran our code. What are some ways that we could have made this issue manifest earlier in the process? Recall our discussion of static versus dynamic decision making. In order to discover certain kinds of errors earlier, we need to give more power to the compiler. We need type declarations!

In many situations, Haskell can infer the types for you. Let’s see what is inferred for majority right now:

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

We ready this as “majority has the type of turning an a into an a, where a is some type that belongs to the Fractional typeclass.” But we didn’t didn’t declare this. The type constraints came from the / operator:

> :t (/)
(/) :: Fractional a => a -> a -> a

The / operator takes a first a and a second a, and produces a third a. Technically the + had something to say in the matter too, but it didn’t constrain the types any further. The result is a Fractional.

So, how do we get it to yield something not Fractional? We must use the div function:

majority n = div n 2 + 1

While we’re talking about div, let’s make some observations. When you write your own programming language, your universe starts to collapse in some mind-boggling ways. You learn…

  1. That variables are just functions taking no parameters and always yielding the same value.
  2. That objects are just dictionaries whose indices are the field names. In Javascript, for instance, we can access a field in two different ways: 
    console.log(hero.name);
console.log(hero['name']);
  3. That arrays are just dictionaries whose indices are integers.
  4. That operators are just non-void methods of arity 1 or 2. + is operator+(int a, int b), for instance. Parameters are operands, and both yield values.

Certainly in Haskell, operators are functions and vice versa. We can treat div as an infix operator:

majority n = n `div` 2 + 1

We can mimic Python’s // to perform integer division by adding a new operator:

a // b = a `div` b

Let’s make sure this works. What do we expect as the value of the following expression?

100 `div` 10 // 2

We expect (div 100 10) // 2, which is 5. But we get div 100 (10 // 2), which is 20. What went wrong? Operator precedence. When we create a new operator, it is given very high precedence by default. We can change that. But how? Let’s first inspect the precedence level of /:

> :info /
class Num a => Fractional a where
  (/) :: a -> a -> a
  ...
        -- Defined in ‘GHC.Real’
infixl 7 /

That last line tells us that the / operator has precedence 7, and that its left associative, meaning that a / b / c will parse as (a / b) / c instead of a / (b / c).

Many of our operators are left associative. Can you think of any that are right associative? man operator lists a few: the assignment operators and unary operators like negation, dereferencing, casting, and address-of.

Problem 2: Let’s generate a circle between two 2D points. A very natural thing to do is start off with something like this:

circletween x1 y1 x2 y2 = ...

What’s not so great about this is that all the parameters are loose. x1 and y1 really belong together. As do x2 and y2. We’d like to treat them as such. For that, we can use tuples! On the calling side, we can say:

circletween (0, 0) (1, 1)

Then on the definition side, we can return a tuple of the circle:

circletween a b = (fst b - fst a, snd b - snd a, 0.5 * sqrt ((fst a - fst b) ** 2 + (snd a - snd b) ** 2)

Ick. In any other language, we’d break this code up and introduce some local variables. We can and should do the same in Haskell. Let’s use a where clause:

circletween a b = (x, y, radius)
  where x1 = fst a
        y1 = snd a
        x2 = fst b
        y2 = snd b
        x = (x1 + x2) * 0.5
        y = (y1 + y2) * 0.5
        deltaX = x2 - x1
        deltaY = y2 - y1
        radius = 0.5 * sqrt (deltaX ** 2 + deltaY ** 2)

This is still longer than it needs to be. To clean it up further, we will use on of Haskell’s most beautiful features: pattern matching. We can use it to automatically decompose values into their components:

circletween (x1, y1) (x2, y2) = (x, y, radius)
  where x = (x1 + x2) * 0.5
        y = (y1 + y2) * 0.5
        deltaX = x2 - x1
        deltaY = y2 - y1
        radius = 0.5 * sqrt (deltaX ** 2 + deltaY ** 2)

Here’s your TODO list:

See you next time!

Sincerely,