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.

## Types of Combinators

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.

### I Combinator (Identity Bird or Idiot Bird)

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.

### K Combinator (Kestrel)

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.

### S Combinator (Starling)

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!

### B Combinator (Bluebird)

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:

### C Combinator (Cardinal)

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.

### Y combinator (Sage Bird)

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:

## Other combinators

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].

## Conclusion

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!).

## References

• [1] Paul Graham - Biography
• [2] To Mock a Mockingbird - Raymond Smullyman
• [3] StackOverflow - Y Combinator in Haskell