Functions as lists

Yesterday's challenge from Programming Praxis challenges us to rebuild a data structure near and dear to any Lisper's/Schemer's/Racketer's[1]/functional programmer's heart: lists. The idea presented in their sample solution uses two element vectors, directly mimicking the general internal structure of Scheme's lists. How about we do something a bit stranger? smile

If you'd like to follow along with the code, I've pushed it as a GitHub Gist here: jpverkamp/6896457.

The idea is one that was first presented to me in a second year undergraduate programming languages course and really shows the strengths of lambda calculus[2]. You don't need vectors to build lists--all you need are functions.


; Build and take apart lists

So when we have a list, it's actually a function (l) expecting another function in turn (of the form (λ (a d) ...). Let's try it out:

> (pair 'a 'b)
> (first (pair 1 2))
> (rest (pair 3 4))

This works just like you would expect it to. Let's do something I generally don't and hand trace that last example. With this many functions flying about, things can get a bit complicated((Not that the trace is terribly better...)):

((λ (a d) a) 6 7)

So it seems to work as planned. What's next?

Well, we want to be able to represent empty lists. One way we could do it is just using some random value as the 'empty list':

; Empty list
(define empty   (gensym))

This works well enough, but one problem we get is that the empty list (in this case) doesn't look the same as a list. In one case, it's a symbol; in the other, it's a function:

> empty
> (pair 1 2)

But that's okay. We can actually still do this. All we have to do is add a third value to the list functions. In addition to the first and rest values, we'll insert a flag telling us if the list is empty. Instead of (λ (a d) ...), we'll have (λ (a d e) ...). Something like this:

; Empty list

; Build and take apart lists

We could actually raise an error, but at the moment, simply returning the symbol error will suffice. Now we can build 'real' lists rather than just pairs:

> empty
> (empty? empty)
> (first empty)

And that's actually all we need. Technically, the project wants us to to add functions equivalent to Scheme's list-ref, length, reverse, and append. With the four functions we have though, these definitions aren't any different than they would be writing them by hand in Scheme:

; Get the nth item of a list
(define nth
  (λ (l i)
    (if (zero? i)
        (first l)

; Calculate the length of a list
(define length
  (λ (l)
    (if (empty? l)

; Reverse a list
(define reverse
  (λ (l)
      (if (empty? l)
          (loop (rest l)

; Append two lists
(define append
  (λ (l r)
    (if (empty? l)

You can do a few tests to make sure that everything works as you would expect, but it's not particularly pleasant given that the structures we're building are rather opaque. So instead, we'll create functions to convert between traditional lists and these functional lists:

; Helpers to convert with traditional lists
(define list->flist
  (λ (l)
    (foldl pair empty l)))

(define flist->list
  (λ (l)
    (if (empty? l)

Now we can tests a few things:

> (flist->list
    (pair 1 (pair 2 empty))
'(1 2 3 4 5)
> (flist->list
'(8 7 6)
> (length
> (nth

Seems to be working well enough. In practice, you'd likely want to test somewhat more thoroughly, but that's good enough for the time being.

What I really love about this is just how much you can build with just functions. Technically, we don't even need #f or numbers in the examples above. Either can be built with just functions in much the same reason. As a bit of a mental exercise, try to implement if, true, and false using only functions[3]

If you'd like to see the entire code at once, you can see it here: jpverkamp/6896457.

  1. Is there a better term?
  2. I've never understood why most people refer to it as the lambda calculus. Especially when there are so many variations...
  3. Hint: There are only so many ways to arrange functions. smile
comments powered by Disqus