λ-poetry

Home / RSS / Contact me

03.08.2020

Y-Combinator

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:

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

The Identity

id

Booleans

Booleans

Booleans examples

Natural Numbers

Natural Numbers

Natural Numbers examples

Pairs

Pairs

Lists

Lists

Binary Trees

Binary Trees

Recursion

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, 2020 RSS / Contact me