05 Aug 2012
Paul Graham is an essayist, programmer and investor. He holds a degree from Cornell and a PhD from Harvard .
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
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 , 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.
S combinator is a function that can be defined as follows in Haskell:
We can write the
I combinator using just the
K combinators as
The proof is as follows:
Applying the function
(s k k) on an argument
x we get
s for its definition,
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
B combinator is defined as
Which can be seen as doing the composition of functions
y (when curried). For example:
This is precisely the definition of Haskell’s
B can be written in terms of
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
b over an argument
x, we get
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
This combinator can be written as a function of the combinators
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 . 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
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:
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:
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
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
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  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 . To solve this problem,  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 directly. Before we must “unwrap: the function contained in it using out.
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
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  has a more extensive list of combinators. There is a Haskell package called data-aviary  containing the implementation of several of these combinators.
Reg Braithwaite discusses some combinators in practice using Ruby in his homoiconic blog/project .
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!).