Good explanation of "Combinators" (For non mathematicians)

Question

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

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.

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.

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

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

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