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 : http://en.wikipedia.org/wiki/Y_combinator )

Answer 1

This is a good article:

http://www.dreamsongs.com/NewFiles/WhyOfY.pdf

The code examples are in scheme, but they shouldn't be hard to follow.

Answer 2

I gave what I think is a pretty good and reasonably short explanation of the Y-combinator on the Boston Perlmongers list a while ago. The code examples were in JavaScript, but it should be easy to translate into any language that you want. Read that and get back to me on whether that explanation works for you.

Answer 3

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

Answer 4

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 5

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

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 8

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