teaching machines

CS 330: Lecture 24 – Local Variables, Lists, and Pattern Matching

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

Let’s write a function. Turn to a neighbor and discuss how you’d solve this:

You are given two points. On the perimeter of what circle do both points lie? Write things down and draw pictures to help your thinking.

A very natural thing to do is start off with something like this:

circletween :: Double -> Double -> Double -> Double -> (Double, Double, Double)
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:

circletween :: (Double, Double) -> (Double, Double) -> (Double, Double, Double)

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. Its origin is the average of the two points. And its radius is half the distance between them, which we can compute with the Pythagorean theorem. To access the fields of the tuple, we use fst and snd:

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 = (ox, oy, radius)
  where x1 = fst a
        y1 = snd a
        x2 = fst b
        y2 = snd b
        ox = (x1 + x2) * 0.5
        oy = (y1 + y2) * 0.5
        dx = x2 - x1
        dy = y2 - y1
        radius = 0.5 * sqrt (dx ** 2 + dy ** 2)

This is still longer than it needs to be. To clean it up further, we will use one of Haskell’s most beautiful features: pattern matching. We can use it to automatically decompose parameters into their constituent 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)

On to another function:

Given three points in 2D space, find a fourth which forms a parallelogram.

There are many possible answers to this. The trick is to find the vector between two of the points, and use that vector as an offset from the third. Let’s use the vector from point 1 to point 3 and add it on to point 2:

par4 :: (Double, Double) -> (Double, Double) -> (Double, Double) -> (Double, Double)
par4 (x1, y1) (x2, y2) (x3, y3) = (x4, y4)
  where x4 = (x2 + x3 - x1)
        y4 = (y2 + y3 - y1)

Let’s go for another:

Turn strings into StRiNgS. But do it recursively.

To gradually introduce some Haskelly ideas, let’s start by implementing a boring old lowercasing function. Since Haskell doesn’t have loops, we write it recursively:

import Data.Char -- to get toLower

lowerize :: String -> String
lowerize s =
  if s == [] then
    []
  else
    toLower first : lowerize rest
    where first = head s
          rest = tail s

We could also have written this using guards, which scales better when there are many cases:

lowerize :: String -> String
lowerize s
  | s == [] = []
  | otherwise = toLower first : lowerize rest
    where first = head s
          rest = tail s

We could also have written this in a form that more easily supports pattern matching using a case statement:

lowerize :: String -> String
lowerize s
  case s of
    [] -> []
    (first : rest) -> toLower first : lowerize rest

Which do you like best? Wait, don’t pick yet. It turns out we can define the different cases in a syntactically simpler way. We add the pattern matching directly into the formals:

lowerize [] = []
lowerize (first : rest) = toLower first : lowerize rest

I think this is beautiful. It feels like we are defining multiple versions of the function for different shapes of the parameters. Each version is self-contained and doesn’t have to worry about the others. In reality, this form is just syntactic sugar for the case version.

Now we’re ready to write a function for producing our odd casing:

oddcase :: String -> String
oddcase [] = []
oddcase (first : second : rest) = toUpper first : toLower second : oddcase rest
oddcase (first : rest) = toUpper first : oddcase rest

Note the order here. The third definition is more general than the second, so if we swap their order, the more general will subsume the less general. The compiler is kind enough to warn you about this situation.

On to another function, let’s write sum—recursively.

On to another function, let’s write contains to see if an list contains a certain value.

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:

jack.hs

import Data.Char

circletween :: (Double, Double) -> (Double, Double) -> ((Double, Double), Double)
-- circletween a b = (((fst b + fst a) / 2, (snd b + snd a) / 2), hypotenuse)
-- circletween a b = ((ox, oy), diameter)
circletween (x1, y1) (x2, y2) = ((ox, oy), diameter)
  where ox = (x2 + x1) / 2
        oy = (y2 + y1) / 2
        dx = x2 - x1
        dy = y2 - y1
        diameter = sqrt (dx ** 2 + dy ** 2)

lowerize :: String -> String
lowerize s =
  if s == [] then
    []
  else
    (toLower first) : (lowerize rest)
    where first = head s
          rest = tail s

lowerize' s
  | s == []   = []
  | otherwise = (toLower first) : (lowerize' rest)
    where first = head s
          rest = tail s

lowerize'' s =
  case s of
    [] -> []
    (first : rest) -> toLower first : lowerize'' rest

lowerize''' [] = []
lowerize''' (first : rest) = toLower first : lowerize''' rest

wwitm [] = []
wwitm (first : second : rest) = toUpper first : toLower second : wwitm rest
wwitm (first : rest) = toUpper first : wwitm rest