Last time, we used pairs to define integers and rational numbers. We also looked at recursion using the Y-combinator. In this post, we'll look at how we can represent lists, as well as some useful functions we can apply on them.

List Representation

There are a few ways to represent lists. If you've worked with linked lists before, you might suspect that pairs are involved, which are indeed one way to represent them! I find they create the most intuitive list representations. The first element of the pair stores the node's value, and the second element stores the rest of the list. The critical idea is that we need some way of differentiating the end of the list (say, nil) with simply an element that contains nil in it.

The simplest list representation is to have a linked list of nodes using pairs, but each node's value is actually a pair itself. The first element of the pair is T or F based on whether it represents the end of the list. The second element is the actual value, or in the case where that node is at the end of the list, it can just hold anything (I have it hold false).

nil = (pair T F)

(cons a l) = (pair (pair false a) l)

(empty? l) = (fst l)

And so on. This cleanly bypasses the difficulty of determining whether we've the end of the list. However, this representation isn't very compact: it needs to store an extra boolean for every node. Instead, we'll look at a representation using just 1 pair for each node.

nil = false

(cons a l) = (pair a l)

The clever part is defining empty?, where we have to be able to distinguish between a pair and F:

(empty? l) = (l (λh,t -> (λd -> F)) T)

• When l is nil, it's equivalent to F, which just takes 2 arguments and returns the 2nd (T). So this case works.
• When l is a pair, then applying it to a function results in its first and second parts being passed to that function. This is why the arguments are named h and t, for head and tail. However, we don't want to do anything with these: we know now that the list is non-empty, so we just need to consume the extra T that this function is going to be applied to and always return F, hence (λd -> F).

Let's just see how this would work on a pair (2, 3):

(empty? (λz -> (z 2 3)))
    = ((λz -> (z 2 3)) (λh,t -> (λd -> F)) T)
    = ((λh,t -> (λd -> F)) 2 3) T)
    = ((λd -> F) T)
    = F

We can easily define some other useful functions:

(head l) = (fst l)

(tail l) = (snd l)

** last and init are particularly hard for a linked list. Try thinking about how you might implement them. The functions in the next section may help.

List Operations

One of the most useful operations on a list is fold (sometimes called reduce), which accumulates a value based on applying an operation to the accumulator and each element, starting at an initial value. We can fold a list from the left or the right side, which are aptly named foldl and foldr respectively. For example:

(foldr (λc,a -> (+ a c)) 0 [2, 3, 4])
    = 0 + (2 + (3 + 4)) = 9

where:

• c represents the "current" element
• a represents the accumulated value

Let's try writing these! Obviously, these will need to be recursive:

foldrRH =
(λr,l -> (l (λh,t -> (λd -> (f h (r t)))) i))

• r is the recursive function
• l is the list (or what's left of it after recursing)
• h and t are the head and tail of l
• f is the function of two parameters being applied
• i is the initial value

When the list is empty, l is nil/F, which just returns the second argument i.

When the list is non-empty, l is a pair, so applying it to the (/h,t -> function correctly assigns the head and tail. This returns a new function that consumes the initial value (we won't need it right now) and calls the combining function on the head and recursively on the tail.

Note that this definition has f and i as free variables. We must abstract them and pass them directly as part of R when using foldr. We need:

foldR = (λf,i -> foldrRH)

The full definition is thus:

(foldr f i l) = ((Y (foldrR f i)) l)

Here's the above example using this definition of foldr:

(foldr (λc,a -> (+ a c)) 0 [2, 3, 4])
    = ((Y (foldrR (λc,a -> (+ a c)) 0)) [2, 3, 4])

Let f = (λc,a -> (+ a c)).
Let R = (foldrR (λc,a -> (+ a c)) 0).
    = (λr,l -> (l (λh,t -> (λd -> (f h (r t)))) 0)))

    => ((R (Y R)) [2, 3, 4])
    = ([2, 3, 4] (λh,t -> (λd -> (f h (R t))) 0)
    = ((λd -> (f 2 (R [3, 4]))) 0)
    = ((λc,a -> (+ a c)) 2 (R [3, 4]))
    = (+ 2 (R [3, 4]))
..and so on.

Observe that every usage of R already has the initial value 0 and the function f embedded inside.

foldl is similar, but left-associative:

foldlRH
= (λr,a,c -> (c (λh,t -> (λd -> (r (f a h) t))) a))

Here, we need an explicit parameter to keep track of the accumulator, since we can't just "delegate" the rest to the right side. Then we simply apply the current list to the provided function, consuming the extra variable if non-empty and recursively calling this function on the left side. Notice how the accumulator is on the left in foldl and it was on the right in foldr. When c is nil, then it acts like F and just returns a, making it the base case. This time, we only have f as a free variable: i only needs to be passed in once, and can be done at the very beginning

foldlR = (λf -> foldlRH)

(foldl f i l) = (Y (R f) i l)

We can work out a similar example to see how i gets used:

(foldl (λa,c -> (+ a c)) 0 [2, 3, 4])
    = ((Y (R f)) 0 [2, 3, 4])
    = ((R f) (Y (R f)) 0 [2, 3, 4])
    = ((λr,a,c -> (c (λh,t -> (λd -> (r (f a h) t))) a)) (Y (R f)) 0 [2, 3, 4])
    = ([2, 3, 4] (λh,t -> (λd -> ((Y (R f)) (f 0 h) t))) 0))
    = ((λd -> ((Y (R f)) (f 0 2) [3, 4]))) 0)
    = ((Y (R f)) (+ 0 2) [3, 4])
    = ((Y (R f)) 2 [3, 4])
... and so on.

Once we have folds, it's simply a functional programming exercise to define helper functions:

(length l) = (foldr (λa,c -> (succ a)) 0 l)

(map f l) = (foldr (λa,c -> (cons (f c) a)) nil l)

(filter f l)
    = (foldr (λa,c -> ((f c) (cons c a) a) nil l)

(reverse l) = (foldl (λa,c -> (cons c a)) nil l)

(append a l) = (reverse (cons a (reverse l)))

(concat a b) = (foldlr (λa,c -> (cons c a)) b a)

Note that we need to use foldr for most functions so that we don't accidentally reverse the list.

The last interesting function is nth, which indexes into a list. We could write it using recursion, but I find it simpler to use tail:

(nth i l) = (head (i tail l))

Simply call tail on the list i times, then get the head. Nice and straightforward.

From here it's fairly easy to continue defining functions like take, any and indexOf, but those are mainly using everything we've already defined. Still, they're good exercises to try out.

That's it for lambda calculus! We've now covered everything I mentioned in the introduction: numbers, booleans, control flow, recursion, and lists. Next time we'll explore even simpler forms of computation: the SKI combinator calculus and the iota combinator.