teaching machines

CS 330: Lecture 25 – Ways of Making Functions: Composition

April 9, 2018 by Chris Johnson. Filed under cs330, lectures, spring 2018.

Dear students:

Let’s warm back up to Haskell by writing some functions to review the ideas we’ve seen in Haskell so far. Here’s our first:

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. We’ll use pattern matching in formals list to break down the pairs:

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)

On to another function. Let’s write contains. We could write this with an if statement, but we saw this wonderfully simple way of spreading out the cases of a decision structure using pattern matching in the function definitions. Let’s make our function work for any type that is equatable using the Eq typeclass. The thing to search for will be the first parameter, and the list to check to will be the second. Thus, our type signature is:

contains :: Eq a => a -> [a] -> Bool

The base case by definition is trivial. When the list is empty, it can’t possibly contain the target element:

contains target [] = False

Notice how target is not being used in this code. When a parameter is ignored, it’s sometimes useful to mark it as ignored to document its lack of involvement. We replace the identifier with an underscore:

contains _ [] = False

When the list is not empty, we either find the target at the head or somewhere in the tail. The logical || captures this choice succinctly:

contains target (first : rest) = first == target || contains target rest

Most of the functions we’ve written so far only return a scalar value. Let’s write one that returns a list. Like this one:

Write a function subdivide that accepts a list and returns a list in which the mean element between each consecutive pair has been interposed. For example subdivide [1, 2] yields [1, 1.5, 2] and subdivide [0, 50, 40] yields [0, 25, 50, 45, 40].

Since we’re doing division to get the mean, the list must be of some type that is an instance of Fractional. That leads us to the type signature:

subdivide :: Fractional a => [a] -> [a]

There are two base cases here: the empty list and the singleton list. Neither situation requires any special processing. We just give back what we are given:

subdivide [] = []
subdivide (first : []) = [first]

In general, however, we have two elements and we need to find their mean and insert it. Something like this does the trick:

subdivide (first : second : rest) = first : mean : subdivide (second : rest)

So, we have seen one way of defining functions in Haskell. We write a named abstraction. We’re going to learn three other ways of building functions, each conferring certain benefits on us as developers.

We first define a word. Arity is the number of parameters a function accepts. Robert Martin says this in Clean Code:

The ideal number of arguments for a function is zero (niladic). Next comes one (monadic), followed closely by two (dyadic). Three arguments (triadic) should be avoided where possible. More than three (polyadic) requires very special justification—and then shouldn’t be used anyway.

He goes on to describe why high arity should be avoided: each parameter is a cognitive burden imposed on the client, and the combinatorical immensity of multiple parameters makes testing difficult.

What’s the arity of +? Two, right? Not in Haskell. In Haskell, you actually provide + (or any function) just one parameter. To what do you suppose that evaluates? We can answer this by examining the type signature. It’s really more general than this, but let’s suppose + worked only with Ints:

(+) :: Int -> Int -> Int

If Haskell behaved more like Java, the type signature of + would look something like this:

(+) :: (Int, Int) -> Int

We feed in the pair of operands all at once and it gives us back the sum. But Haskell doesn’t behave like Java, and it allows to only partially apply parameters. If we provide only a single Int, what’s left of the signature is Int -> Int. That means the value returned by (+) 10 is a function waiting on the second parameter! The arrow syntax makes a lot more sense if you parenthesize it, observing its right associativity:

(+) :: Int -> (Int -> Int)

So, all Haskell functions truly have an arity of 1. If something has an arity of 0, it’s a variable. This behavior leads us to a new way of defining functions: we can supply a subset of the parameters to some existing function to define a convenience function that has a simpler interface.

Consider this very generic function that surrounds a String with some prefix and suffix:

surround :: String -> String -> String -> String
surround prefix suffix body = prefix ++ body ++ suffix

Suppose we want to parenthesize a String. We could say this:

surround "(" ")" "Lincoln 1863"

But if we have to do this a lot, it’d be nice to provide a convenience function:

parenthesize :: String -> String
parenthesize s = surround "(" ")" s

We can take one more step to get to idiomatic Haskell. Function parenthesize doesn’t really need to relist its formal parameters. It gets those from surround. We can, in fact, leave them off:

parenthesize :: String -> String
parenthesize = surround "(" ")"

How I think of this is that parenthesize isn’t so much a function as a synonym for its right-hand side. We know that the right-hand side is only partially evaluated, and that the third parameter is still missing. This practice of chopping off the formals when they can be deduced from partial evaluation is called point-free style. Why this term is called that is not so important, but having a term to identify the practice is.

Partial evaluation allows each function to be a little factory from which we can build other functions. Here are a few more surrounders:

quote = surround "\"" "\""
tag = surround "<" ">"
italicize = surround "*" "*"

This ability to make functions from other functions is a superpower.

Let’s write another really generic function: join. It collects a bunch Strings together, separating each with some specified separation sequence. Here’s our definition:

join :: String -> [String] -> String
join _ [] = []
join _ (only:[]) = [only]
join separator (first:rest) = first ++ separator ++ join separator rest

Now we can write a couple partially evaluated versions of join:

commafy = join ", "
begat = join " begat "

commafy ["Texas", "Florida", "Tennessee"]
begat ["Grandma", "Mom", "Me"]

We now have two ways of defining functions in Haskell: as named abstractions of algorithms or as partially evaluated versions of other functions. Let’s look at a third way of defining functions: composition. Suppose we wanted to get the second element out of a list, the neck. We can write this with a chain of two calls:

neck :: [a] -> a
neck list = head (tail list)

The output of the first function becomes the input of the second function. We’ve seen this idea before in our math classes. When we see f(g(x)), we sometimes rewrite this as f compose g or f o g. In Haskell, we write this as follows:

neck :: [a] -> a
neck list = (head . tail) list

One of the advantages of expressing this as a composition of functions is that we can rewrite it in point-free style. Notice how the left- and right-hand sides share the same suffix. Let’s leave it out:

neck :: [a] -> a
neck = head . tail

Both partial evaluation and composition eliminate a lot of the overhead that we programmers find ourselves doing. Much of our development life is spent gluing together abstractions into some mega-abstraction, and these two techniques give us some of our life back.

Here’s your TODO list for next time:

• Start the Funfun homework, which is due before April 25.

See you then!

Sincerely,

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

I put in two dimes
Out popped a vending machine
Demanding the rest

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

lecture.hs

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

contains :: Eq a => a -> [a] -> Bool
contains _ [] = False
contains target (first : rest) = target == first || contains target rest

subdivide :: Fractional a => [a] -> [a]
subdivide [] = []
subdivide (first : []) = [first]
subdivide (first : second : rest) = first : mean : subdivide (second : rest)
  where mean = (first + second) / 2

surround :: String -> String -> String -> String
surround prefix suffix meat = prefix ++ meat ++ suffix

parenthesize :: String -> String
parenthesize = surround "(" ")"

tag :: String -> String
tag = surround "<" ">"

quote :: String -> String
quote = surround "\"" "\""

join :: String -> [String] -> String
join _ [] = ""
join _ (first : []) = first
join separator (first : rest) = first ++ separator ++ join separator rest

commafy = join ", "
begat = join " begat "