Beautiful Code: Code == Data

I found this in an exercise in SICP. Instead of the original Scheme, which IMHO is a little difficult to read, I’ve translated it to Haskell.


pair x y = \acc -> (acc x y)
first pair = pair (\x y -> x)
second pair = pair (\x y -> y)


Haskell tends to look a little discouraging at first, but its actually quite straightforward. \x -> expr is how you create a lambda in Haskell. Even though Haskell is statically typed, note that we haven’t specified any types at all. This is because Haskell’s system of type inference is quite powerful.

That said, what does the above do? The function names should make it clear that we’re somehow providing a function that creates a pair, and the first and second functions are accessor methods for the elements of the pair. For instance, they’d be used like this:


*Main> let n1 = pair 10 20
*Main> first n1
10
*Main> second n1
20


Question is: how does this work? Lets look at at the pair function carefully. It’s returning a function that accepts a single parameter acc, and calls acc with the parameters x and y.

The function first accepts a single argument pair as input, and calls pair with an argument that is a function. This function accepts two arguments, and returns the first of those two arguments.

It should all make sense now. pair 10 20 returned a function that would accept a function as parameter, and call that function with the parameters 10 and 20. The functions first and second second call this function (the returned value of pair) with a function as a parameter such that this passed function (the lambda’s in definitions of first and second) returns the appropriate element of the pair.

Pretty cool, no?