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

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

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

Dear students,

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

by defining a named function
by partially applying parameters to get a new function expecting only the remaining parameters
by composing a gauntlet of functions together
by defining unnamed lambdas

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:

Some of these other ways (2, 3) will let us create new functions from old ones with very little extra code. The more I have to type, the more opportunity for error.
Some of these other ways (2, 3) will take very generic functions and specialize them or combine them to produce a new function that may take fewer arguments and will have a name more specific to its task. This means my code will be easier to write and read. I won’t need as many explanatory comments.
Some of these other ways (2, 3, 4) treat functions like we treat any data. They make it easy to sequence functions together or pass functions as parameters to other functions.

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?

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 + ">")
```
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:

Read chapter 5 and chapter 6 in Learn You a Haskell.
On a quarter sheet, define three functions of your choosing using one each of partial evaluation, composition, and lambdas.

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

Sincerely,