teaching machines

CS 330 Lecture 22 – Ways to Define Functions: Partial Evaluation

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

Dear students,

There are at least four ways of defining functions in Haskell:

A good first question to ask is this: why do we need more than one way of defining functions? I can think of a few good reasons:

But I don’t expect you to believe any of these things until you’ve seen these alternative ways in action. Let’s start with partial evaluation.

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.

Arguments are hard. They take a lot of conceptual power. That’s why I got rid of almost all of them from the example. Consider, for instance, the StringBuffer in the example. We could have passed it around as an argument rather than making it an instance variable, but then our readers would have had to interpret it each time they saw it. When you are reading the story told by the module, includeSetupPage() is easier to understand than includeSetupPageInto(newPageContent). The argument is at a different level of abstraction than the function name and forces you to know a detail (in other words, StringBuffer) that isn’t particularly important at that point.

Arguments are even harder from a testing point of view. Imagine the difficulty of writing all the test cases to ensure that all the various combinations of arguments work properly. If there are no arguments, this is trivial. If there’s one argument, it’s not too hard. With two arguments the problem gets a bit more challenging. With more than two arguments, testing every combination of appropriate values can be daunting.

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? A function waiting on the second parameter! We can see this by examining the type signature. Let’s stick with Ints:

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

Haskell doesn’t appear to distinguish the final return value apart from the formal parameters. It would make a little more sense if it accepted something like this:

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

But it doesn’t, because Haskell supports partial evaluation. This 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 some has an arity of 0, it’s a variable.

How is partial evaluation useful? It turns every function into a factory that can produce simpler functions. Suppose we want to add 10 to a bunch of numbers. We can write a convenience function add10 that more clearly describes the semantic meaning:

add10 = (+) 10
add10 0

How about some examples?

  1. Let’s write surround which wraps up a string inside a left token and a right token:
    surround :: String -> String -> String -> String
    surround left right middle = left ++ middle ++ right
    This is pretty vanilla. Suppose we want to quote a string. It seems a little silly to say this:
    surround "\"" "\"" "foobag"
    Let’s create a convenience method quote:
    quote s = surround "\"" "\"" s
    Nice, huh? But this doesn’t use partial evaluation. Remember, if we leave off a parameter, we’ll get back a function that’s waiting for that last parameter:
    quote = surround "\"" "\""
    When we define a function that takes in parameters but we leave them off the formal parameter list, we say it is written in point-free style. This has some technical advantages that I don’t think I fully grok. Let’s write a function to produce an HTML element:
    tag element = surround ("<" + element + ">) ("</" + element + ">")
  2. Now let’s write join, which accepts a separator string and a list. It joins all the elements together with an intervening separator:
    join :: Show a => String -> [a] -> -> String
    join _ [] = ""
    join _ (first:[]) = show first
    join separator (first:rest) = show first ++ separator ++ join rest
    We can produce new convenience functions by partially evaluating join:
    commafy = join ","
    begat = join " -> "

Here’s your TODO list:

See you next time, when we discuss the remaining ways to define functions in Haskell!

Sincerely,