kuniga.me > NP-Incompleteness > Combinators in Haskell

05 Aug 2012

Paul Graham is an essayist, programmer and investor. He holds a degree from Cornell and a PhD from Harvard [1].

As an essayist, he has written several articles, the most famous of which is A plan for spam on the use of a Bayesian filters to combat spam.

As a programmer, Graham is known for his work with Lisp, having written books on the language and developing a dialect called Arc. He also developed the first web application called Viaweb, later acquired by Yahoo!

As an investor, he founded the company Y Combinator in 2005, which invests in start-ups. Some of the companies funded by Y-Combinator include Dropbox, Airbnb and reddit.

According to their FAQ, the motivation behind the company name is:

The Y combinator is one of the coolest ideas in computer science. It’s also a metaphor for what we do. It’s a program that runs programs; we’re a company that helps start companies.

In this post I would like to present some notes from my studies on Haskell combinators, describing some of the main types including the Y combinator.

This post originated from my initial studies of Chapter 9 of Real World Haskell. At a certain point in the chapter the authors mention the term combinators, not making it very clear what they are and what they are for. I did some research on the subject and decided to write a post.

A **combinator** can be defined as a lambda function that has no free variables. A free variable is a variable that has not been passed as a parameter in the lambda function. Some examples of lambda functions in Haskell:

1) The function below is a combinator because the variable `x`

is in the parameter:

2) In the following example `y`

is a free variable and therefore not a combinator.

3) Here both `x`

and `y`

were passed by parameter, so we have a combinator.

4) The example below is not a combinator because `f`

was not passed as a parameter

5) Here’s a tricky one: Note that the `+`

operator is actually a function that takes two arguments, as in example (4). But since the operator was not passed as a parameter, it is also *not* a combinator.

We can think of a combinator as a function that takes in functions and returns another function that results from combining the input functions.

In the next sections, we will introduce some of the most popular combinators. These combinators are named with a single capital letter. However, in the book To Mock a Mocking Bird [2], Raymond Smullyman named the different types of combinators after birds. Therefore, each section will have the name of the combinator and, in parentheses, the nickname given by Smullyman.

This is the simplest combinator, the identity. It is a function that returns its own parameter. In Haskell we can write:

This is precisely the definition of the `id`

function in the Prelude library.

This combinator is the constant combinator, taking two arguments and ignoring the second. In Haskell we can write:

This is precisely the definition of the `const`

function in the Prelude library.

The `S`

combinator is a function that can be defined as follows in Haskell:

We can write the `I`

combinator using just the `S`

and `K`

combinators as

The proof is as follows:

Applying the function `(s k k)`

on an argument `x`

we get

Substituting `s`

for its definition,

Now let `f = (k x)`

be any function. We have `k x f = x`

by definition, so

It is possible to show that any combinator can be written as a function of the combinators `S`

and `K`

!

The `B`

combinator is defined as

Which can be seen as doing the composition of functions `x`

and `y`

(when curried). For example:

This is precisely the definition of Haskell’s `(.)`

operator. `B`

can be written in terms of `S`

and `K`

as:

Let’s see what this function looks like applied to some arguments. Let `f1 = k s`

. Using currying we see that this is a function that takes an argument but always returns `s`

. Applying `b`

over an argument `x`

, we get

Let `f2 = (k x)`

. We have that `f2`

is a function that takes any argument and always returns `x`

. So we have `b x = s f2`

. Let’s apply it over two more parameters `y`

and `z`

:

This combinator can be written as a function of the combinators `K`

, `S`

and `B`

as

It can be shown that this combinator is equivalent to

This is precisely the definition of the operator `flip`

from Prelude, which returns a function with the order of the parameters changed.

Simply put, the `Y`

combinator is a combinator that transforms a non-recursive function into a recursive function!

Before describing it, let’s analyze how we would do it without the Y-combinator. For that, let’s use as an example a function that calculates the factorial [8]. Using recursion, we can write:

The above lambda expression is not a combinator because it depends on `fact`

, which was not passed as a parameter.

Let’s try to pass the function by parameter so

Note that `fact'`

is not a recursive function. Now we do the following:

We are defining `fact`

as the result of `fact'`

when we pass `fact`

as a parameter. Sounds like magic, but in languages with lazy evaluation this will work. Why?

Let’s unwrap the definition of `fact`

one level:

For `n = 0`

, the function will return 1 and will not to the trouble of calculating `fact(n - 1)`

.

Let’s now unwrap the function for 2 steps:

For `n = 1`

, you can see that a lazy evaluation needs no further evaluations than that.

Okay, we’ve managed to turn a non-recursive `fact'`

function into a recursive function. Let’s create a helper function so that the `fact'`

function is passed as a parameter

The `aux`

function does what we want the Y combinator to do: takes a non-recursive function (e.g. `fact'`

) and returns a recursive one (in this case `fact`

). However, `aux`

is not a combinator because the `aux`

that is called recursively is a free variable.

So let’s introduce the Y combinator. Its theoretical definition is given by

I still haven’t been able to understand this definition clearly enough to venture an explanation here. My suggestion is to read [8] where Mike Vaniel derives the above function in Scheme.

Anyway, if we were to implement it in Haskell, we would get a compilation error due to infinite type [3]. To solve this problem, [4] presents the following solution:

To avoid problems with infinite type, we encapsulate the second term `(\x -> f (x x))`

in a new type, `Rec a`

, through the `In`

constructor. Lambda functions take `x`

which is of type `Rec a`

and so we cannot apply `x`

to `x`

directly. Before we must “unwrap: the function contained in it using out.

Remembering, the `newtype`

defines a structure similar to an algebraic data type, with the difference that it only allows a constructor, in the case defined by `In`

, and a “getter”, specified by `out`

.

For example, let’s define a type called `NewType`

that encapsulates a function that takes a generic type and returns that same generic type, that is, with type `a -> a`

.

We can wrap a function that takes and returns an integer. For example:

We can check the type of this variable in ghci:

The getter extracts the function that was encapsulated, that is, we can do:

This site [5] has a more extensive list of combinators. There is a Haskell package called data-aviary [6] containing the implementation of several of these combinators.

Reg Braithwaite discusses some combinators in practice using Ruby in his homoiconic blog/project [7].

I was glad to take a break from reading the Real World Haskell book to learn more about combinators. Thanks to that I ended up discovering interesting things like the origin of Graham’s company name and that some commonly used functions in Haskell are combinators.

Also, while the Y combinator isn’t that useful in practice, the ideas behind it are very interesting (and, in my opinion, complicated!).

- [1] Paul Graham - Biography
- [2] To Mock a Mockingbird - Raymond Smullyman
- [3] StackOverflow - Y Combinator in Haskell
- [4] [Haskell] How to define Y combinator in Haskell
- [5] Combinator Birds
- [6] Hackage – The data-aviary package
- [7] Github – Homoiconic
- [8] Mike’s World-O-Programming – The Y Combinator
- [9] Y-Combinator in Javascript