The lambda calculus is a formal system that is used to express computations. Like the Turing machine, it’s a universal model of computation, however, it’s much simpler and more elegant than those bulky machines.

I’ve written down the fundamental datastructures and some important functions operating on them, all in the untyped lambda calculus and for the sole purpose of delight.

The datastructures presented differ from ordinary, imperative datastructures, as they are purely functional. That means they don’t describe where and how the data is stored, but rather how functions are applied to that data.

Variable names are often chosen as a hint on the value they’re holding, but aren’t elaborated on. Their exact purpose and meaning is left open for exploration.

Have fun!

The structure

There are three constructs in the untyped lambda calculus:

Variables x,

Abstractions λx. t and

Applications f x.

The Identity

Booleans

Natural Numbers

Pairs

Lists

Binary Trees

Recursion

Want to leave a comment?

If you want to give me some feedback or share your opinion, please contact me via email.