Implementing Linked List Using Nothing But Lambda Functions in Python

Introduction

My love for Lambda Calculus started about an year ago when I started learning Functional Programming. In this blog I will implement Linked Lists using just lambda functions in python. The real goal of this blog is to not to implement linked list per say, but is to understand a very simple concept-

“Programming is all about composing simple stuff."
- me

(And to also have fun with lambda calculus 😊)

Following is the complete code (in Python) to define linked lists-

If you watch carefully, LinkedList is defined in terms of Pair, and Pair is defined in terms of SK Combinators. In this blog I will explain how to define linked lists (and other interesting data structures) just using the following two functions-

The above representation is rather verbose, so I will use the following representation instead-

1. Function calls are left grouped. e.g-

f(x)    becomes f x
f(x)(y) becomes f x y

2. Braces () are put to disambiguate if necessary

f(g(x)) becomes f (g x)
-- this is done so that we don't confuse between f(g(x)) and f(g)(x)

3. lambda is replaced by \ for terseness

lambda x. y becomes \x. y

So in a nutshell-

Representing f(x)                            as f x
Representing f(x)(y)                         as f x y
Representing f(x)(y)(z)                      as f x y z
Representing lambda x: y                     as \x. y
Representing lambda x: lambda y: z           as \x y. z
Representing lambda x: lambda y: lambda z: w as \x y z. w
Representing f(g(x))                         as f (g x)

You get the picture. Notice the use of braces () to put disambiguate function calls. So the definition of SK Combinators in above notation becomes

S := \f g x. f x (g x)
K := \x y. x

Come back to these rules if you get stuck. Or either watch this video for better description.

Before going on and defining other functions in terms of S and K , let’s intuitively understand what these functions do. In order to do this I would need to define some reduction/ conversion rules that would help us reduce/ convert any functions.

Reduction Rules-

1. Alpha (α) Equivalence/ Substitution-

This is the easiest one every programmer knows, replacing variable a with b everywhere in the expression does not change the meaning of the expression.

\x. f x             is same as \y. f y
\x y. f x (g y) h x is same as \a b. f a (g b) h a

2. Beta (β) reduction-

This might be also the easiest, all this says that arguments are binded one after the other to the function parameters as applied.

(\x. f x) y       is same as f y
(\x y. f x y) a b is same as f a b
(\x. f x) a (\y. g y y) c
is same as f a (\y. g y y) c
is same as f a (g c c)

Ponder upon a bit on this. Maybe write it down on piece of paper and try to really understand what’s going on here.

3. Eta (η) reduction-

All this says is that we can get rid of lambda abstraction if the last argument in present/ used only once in the expression.

\x. f x       is same as f
\x y. f x g y is same as \x. f x g
\x y. f x y   is same as f
-- we can apply the reduction as much as we want

Having defined the above rules, let’s understand intuitively what S and K does-

SK Combinators

S Combinator

S := \f g x. f x (g x)

You can think of this combinator as taking a binary operator (function with two arguments) f, another function g and an input x . Now applying g to x and then passing x and g x to f . The below graph diagrams tries to show this transformation-

K Combinator

It’s the easiest to understand, you can think of this as a combinator taking two inputs x and y and returns the first value x

Identity (I) Combinator

Now, let’s define the most trivial function: the identity function that does nothing to it’s input.

I := \x. x

How would you even approach it. Trick is (or what worked for me) is try to remove the last argument of the lambda expression, focus on it and then shape it in form of already known combinators (in this case only S & K are available) — building on top of what’s already known. Often by introducing K and using it to convert the current expression in the form that can be easily reduced by S.

Here we need to get rid of x . We can rewrite I as-

I := \x. x
  := \x. K x K

This seems rather wasteful, but surprisingly this is the only way to convert it in terms of S and K. You can intuitively think that S and K are more complicated than I, so we need to introduce some wasteful computation and make it more complicated in order to convert it in the form that can easily be reduced (using the Reduction rules).

Now if you see \x. K x K is very close to form of S \f g x. f x (g x) except for the last K

We need a form z x which is equivalent to K . We can do that by conversing K with K K x . We can do this as K K x is same as K . Ponder on this a bit why so. (Use the definition of K and expand)

I := \x. x
  := \x. K x K
  := \x. K x (K K x)

Now we can easily replace K x (K K x) with S K (K K) x

I := \x. x
  := \x. K x K
  := \x. K x (K K x)
  := \x. S K (K K) x
  := S K (K K)         -- by eta-reduction

Kite (KI) Combinator

The kite combinator is similar to the K combinator except it returns the second argument rather than the first one.

KI := \x y. y

We need to remove y . We will do that by using the identity combinator.

KI := \x y. y
   := \x y. I y

We can get rid of y right away-

KI := \x y. y
   := \x y. I y
   := \x. I

Now we need to get rid of x , but there is no x in the expression. We will be using K similar to how we used in the identity combinator ( K ~ K K x ).

KI := \x y. y
   := \x y. I y
   := \x. I
   := \x. K I x

We can immediately remove x

KI := \x y. y
   := \x y. I y
   := \x. I
   := \x. K I x
   := K I

Now you can see I called kite combinator as KI not accidentally

Bluebird (B) Combinator (Composition Combinator)

It’s very similar to the S := \f g x. f x (g x) combinator. It composes two functions together.

B := \f g x. f (g x)

We need to get rid of x . After some thinking and scribbling you will see that we need to shape f in the form of z x . We can do that by rewriting f as K f x

B := \f g x. f (g x)
  := \f g x. K f x (g x)

B := \f g x. f (g x)
  := \f g x. K f x (g x)
  := \f g x. S (K f) g x

We can get rid of both g and x immediately. Cool

B := \f g x. f (g x)
  := \f g x. K f x (g x)
  := \f g x. S (K f) g x
  := \f. S (K f)

We need to get rid of f . We can do that similar to how we did for x . We can convert S to K S f .

B := \f g x. f (g x)
  := \f g x. K f x (g x)
  := \f g x. S (K f) g x
  := \f. S (K f)
  := \f. K S f (K f)

B := \f g x. f (g x)
  := \f g x. K f x (g x)
  := \f g x. S (K f) g x
  := \f. S (K f)
  := \f. K S f (K f)
  := \f. S (K S) K f
  := S (K S) K

Let’s take a break and rewrite (with their derivation) all the combinators defined so far below-

S := \f g x. f x (g x)
K := \x y. x
I := \x. x
  := \x. K x K
  := \x. K x (K K x)
  := \x. S K (K K) x
  := S K (K K)
KI := \x y. y
   := \x y. I y
   := \x. I
   := \x. K I x
   := K I
B := \f g x. f (g x)
  := \f g x. K f x (g x)
  := \f g x. S (K f) g x
  := \f. S (K f)
  := \f. K S f (K f)
  := \f. S (K S) K f
  := S (K S) K

Hopefully by little bit of scribbling and exploring you would get how to approach these derivations. Trick is to identify these patterns and move forward. Explore and have fun.

We haven’t still come to the linked list. But before that let me introduce the Thrush Combinator.

Thrush (T) Combinator

Thrush combinator is a very simple combinator. It’s similar to the fundamental definition of function itself, instead of \f x. f x , it takes the data x first before the function f .

T := \x f. f x

This might be familiar to Spark developers. When we write df.transform(func) we are focusing on the data df first before the function func. Here, transform is the Thrush combinator.

We need to get rid of f and then x. I will do this fast, so try to follow along with derivation.

T := \x f. f x
  := \x f. I f x
  := \x f. I f (K x f)
  := \x f. S I (K x) f
  := \x. S I (K x)
  := \x. B (S I) K x
  := B (S I) K

As you can see, I used almost all the combinators we had described so far.

Now comes the pivotal point in this blog, we will define what data actually is, specifically we would define what a Pair is. Pair is the most basic data structure, it’s the glue that lets us define more complex data structures, like Lists , Stacks , Deques , Trees etc.

Vireo (V) Combinator (Pair Combinator)

It’s the most basic data structure. Pair of two things. Notice it’s similarity to the Thrush combinator.

V := \x y f. f x y

Intuitively you can understand Vireo as taking the data items x and y first, and then using f to extract/ transform/ modify x and y . Let’s convert it into combination of already known combinators first. Again, please try to follow along the derivation.

V := \x y f. f x y
  := \x y f. T x f y
  := \x y f. T x f (K y f)
  := \x y f. S (T x) (K y) f
  := \x y. S (T x) (K y)
  := \x y. B (S (T x)) K y
  := \x. B (S (T x)) K
  := \x. B (B S T x) K
  := \x. B B (B S T) x K
  := \x. B B (B S T) x (K K x)
  := \x. S (B B (B S T)) (K K) x
  := S (B B (B S T)) (K K)

Cool, now we have defined Vireo all in terms of S and K. (Note that B and T were already defined in terms of S and K).

Having defined the notion of a Pair, how do we extract both the information from the it. Let’s think about how we would to extract the first value

some_pair = V 2 3
some_pair f = f 2 3
We need to define f in such a way that we get first value.
We already have it, it's called the K combinator.
Similarly you would see we would need the Kite (KI) combinator to extract the second value.
some_pair K = 2
some_pair KI = 3

We would define helper functions for doing this-

fst := \pair. pair K
    := \pair. T K pair
    := T K
snd := \pair. pair KI
    := \pair. T KI pair
    := T KI

So we have

fst (V a b) = a
snd (V a b) = b

Having defined what a Pair is, it’s very trivial to define LinkedLists .

LinkedLists is just a pair of head and rest of the list .

cons = V
head = fst
tail = snd

I am also storing the length of the list in every node of the list (again as a Pair) in the following definition of linked list in Python-

And that’s really it. Once we have defined what a Pair is, now we can define Trees or Deque etc. Here is the Github repo that implements other data structures as well.

The point of this blog was not to implement the fasted linked list on planet, rather this implementation would be very inefficient. It was to understand the fundamental data structure The Pair . And that too using only S and K combinators.

Again I will stress what I said at the beginning of this blog-

“Programming is all about composing simple stuff."
- me

And how do you do that? By recognizing patterns that can be replaced with something simpler.

And with that I will wrap this up. Hopefully this blog was not too long and you were able to follow along.

Continue getting inspired and inspire others as well.