λ-poetry

Trying to escape local optima on a random walk through life. Home / RSS / Contact

03.08.2020

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 your exploration. ;)

Have fun!

The structure

There are three constructs in the untyped lambda calculus:

  1. Variables x,
  2. Abstractions λx. t and
  3. Applications f x.

The Identity

id
id

Booleans

Booleans
Booleans
Booleans examples
Booleans examples

Natural Numbers

Natural Numbers
Natural Numbers
Natural Numbers examples
Natural Numbers examples

Pairs

Pairs
Pairs

Lists

Lists
Lists

Binary Trees

Binary Trees
Binary Trees

Recursion

The Y-Combinator
The Y-Combinator
Applications of the Y-Combinator
Applications of the Y-Combinator

Want to leave a comment?

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


© Niklas Bühler, 2021 RSS / Contact me