Good explanation of "Combinators" (For non mathematicians)

Question

Anyone got a good explanation of "combinators" (Y-combinators etc. and NOT the company)?

I'm looking for one for the practical programmer who understands recursion and higher-order functions, but doesn't have a strong theory or math background.

(Note: that I'm talking about these things)

Answer 1

Quote Wikipedia:

A combinator is a higher-order function that uses only function application and earlier defined combinators to define a result from its arguments.

Now what does this mean? It means a combinator is a function (output is determined solely by its input) whose input includes a function as an argument.

What do such functions look like and what are they used for? Here are some examples:

(f o g)(x) = f(g(x))

Here o is a combinator that takes in 2 functions , f and g, and returns a function as its result, the composition of f with g, namely f o g.

Combinators can be used to hide logic. Say we have a data type NumberUndefined, where NumberUndefined can take on a numeric value Num x or a value Undefined, where x a is a Number. Now we want to construct addition, subtraction, multiplication, and division for this new numeric type. The semantics are the same as for those of Number except if Undefined is an input, the output must also be Undefined and when dividing by the number 0 the output is also Undefined.

One could write the tedious code as below:

Undefined +' num = Undefined
num +' Undefined = Undefined
(Num x) +' (Num y) = Num (x + y)

Undefined -' num = Undefined
num -' Undefined = Undefined
(Num x) -' (Num y) = Num (x - y)

Undefined *' num = Undefined
num *' Undefined = Undefined
(Num x) *' (Num y) = Num (x * y)

Undefined /' num = Undefined
num /' Undefined = Undefined
(Num x) /' (Num y) = if y == 0 then Undefined else Num (x / y)

Notice how the all have the same logic concerning Undefined input values. Only division does a bit more. The solution is to extract out the logic by making it a combinator.

comb (~) Undefined num = Undefined
comb (~) num Undefined = Undefined
comb (~) (Num x) (Num y) = Num (x ~ y)

x +' y = comb (+) x y
x -' y = comb (-) x y
x *' y = comb (*) x y
x /' y = if y == Num 0 then Undefined else comb (/) x y

This can be generalized into the so-called Maybe monad that programmers make use of in functional languages like Haskell, but I won't go there.

Answer 2

This is a good article. The code examples are in scheme, but they shouldn't be hard to follow.

Answer 3

Reginald Braithwaite (aka Raganwald) has been writing a great series on combinators in Ruby over at his new blog, homoiconic.

While he doesn't (to my knowledge) look at the Y-combinator itself, he does look at other combinators, for instance:

• the Kestrel
• the Thrush
• the Cardinal
• the Obdurate Kestrel
• other Quirky Birds

and a few posts on how you can use them.

Answer 4

This looks a good one : http://www.catonmat.net/blog/derivation-of-ycombinator/

Answer 5

A combinator is function with no free variables. That means, amongst other things, that the combinator does not have dependencies on things outside of the function, only on the function parameters.

Using F# this is my understanding of combinators:

let sum a  b = a + b;; //sum function (lambda)

In the above case sum is a combinator because both a and b are bound to the function parameters.

let sum3 a b c = sum((sum a b) c);;

The above function is not a combinator as it uses sum, which is not a bound variable (i.e. it doesn't come from any of the parameters).

We can make sum3 a combinator by simply passing the sum function as one of the parameters:

let sum3 a b c sumFunc = sumFunc((sumFunc a b) c);;

This way sumFunc is bound and hence the entire function is a combinator.

So, this is my understanding of combinators. Their significance, on the other hand, still escapes me. As others pointed out, fixed point combinators allow one to express a recursive function without explicit recursion. I.e. instead of calling itself the recusrsive function calls lambda that is passed in as one of the arguments.

Here is one of the most understandable combinator derivations that I found:

http://mvanier.livejournal.com/2897.html

Answer 6

Shortly, Y combinator is a higher order function that is used to implement recursion on lambda expressions (anonymous functions). Check the article How to Succeed at Recursion Without Really Recursing by Mike Vanier - it's one of best practical explanation of this matter I've seen.

Also, scan the SO archives:

• What is a y-combinator?
• Y-Combinator Practical Example

Answer 7

I'm pretty short on theory, but I can give you an example that sets my imagination aflutter, which may be helpful to you. The simplest interesting combinator is probably "test".

Hope you know Python

tru = lambda x,y: x
fls = lambda x,y: y 

test = lambda l,m,n: l(m,n)

Usage:

>>> test(tru,"goto loop","break")
'goto loop'
>>> test(fls,"goto loop","break")
'break'

test evaluates to the second argument if the first argument is true, otherwise the third.

>>> x = tru
>>> test(x,"goto loop","break")
'goto loop'

Entire systems can be built up from a few basic combinators.

(This example is more or less copied out of Types and Programming Languages by Benjamin C. Pierce)

Answer 8

Unless you're deeply into theory, you can regard the Y combinator as a neat trick with functions, like monads.

Monads allow you to chain actions, the Y combinator allows you to define self-recursive functions.

Python has built-in support for self-recursive functions, so you can define them without Y:

> def fun():
>  print "bla"
>  fun()

> fun()
bla
bla
bla
...

fun is accessible inside fun itself, so we can easily call it.

But what if Python were different, and fun weren't accessible inside fun?

> def fun():
>   print "bla"
>   # what to do here? (cannot call fun!)

The solution is to pass fun itself as an argument to fun:

> def fun(arg): # fun receives itself as argument
>   print "bla"
>   arg(arg) # to recur, fun calls itself, and passes itself along

And Y makes that possible:

> def Y(f):
>   f(f)

> Y(fun)
bla
bla
bla
...

All it does it call a function with itself as argument.

(I don't know if this definition of Y is 100% correct, but I think it's the general idea.)