Good explanation of "Combinators" (for non-mathematicians)

Question

Has anyone received a good explanation of "combinators" (Y-combinators, etc., not the company)

I am looking for one for a practical programmer who understands recursion and higher order functions, but does not have a strong theory or mathematical background.

(Note that I'm talking about these things: http://en.wikipedia.org/wiki/Y_combinator )

Answer 1

If you delve deeply into theory, you can evaluate Y combinator as a neat trick with features like monads.

Monads let you chain actions, Y combinator lets you 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 available inside fun , so we can easily call it.

But what if Python were different and fun not available inside fun ?

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

The solution is to pass fun 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 this possible:

 > def Y(f): > f(f) > Y(fun) bla bla bla ... 

All this, he calls the function with himself as an argument.

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

Answer 2

Reginald Braithwaite (aka Raganwald) writes on his new blog an excellent series about combinators in Ruby, homoiconic .

While he (as far as I know) does not look at the Y-combinator itself, he looks at other combinators, for example:

• Kestrel
• Thrush
• Cardinal
• Obdurate kestrel
• other fancy birds

and a few posts on how you can use them.

Answer 3

Quote Wikipedia:

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

What does it mean? This means that the combinator is a function (the output is determined solely by its input), the input of which includes the function as an argument.

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

(fog)(x) = f(g(x))

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

Combinators can be used to hide logic. Let's say we have a NumberUndefined data NumberUndefined , where NumberUndefined can take a numeric value Num x or an Undefined value, where x a is Number . Now we want to build addition, subtraction, multiplication and division for this new numerical type. The semantics are the same as for Number , except that if Undefined is an input, the output must also be Undefined , and when divided by 0 output is also Undefined .

You can write tedious code, as shown 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) 

Note that all have the same logic with respect to Undefined input values. Only division does a little more. The solution is to extract 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 (+) xy x -' y = comb (-) xy x *' y = comb (*) xy x /' y = if y == Num 0 then Undefined else comb (/) xy 

This can be generalized to the so-called Maybe monad, which programmers use in functional languages ​​such as Haskell, but I won’t go there.

Answer 4

The combinator works with no free variables . This means, among other things, that the combinator has no dependencies on things outside the function, only on the parameters of the function.

Using F #, this is my understanding of combinators:

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

In the sum above, the sum is a combinator, since both a and b tied to the parameters of the function.

 let sum3 abc = sum((sum ab) c);; 

The above function is not a combinator, as it uses sum , which is not a related variable (i.e. it does not 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 abc sumFunc = sumFunc((sumFunc ab) c);; 

This way sumFunc is connected , and therefore the whole function is a combinator.

So this is my understanding of combinators. On the other hand, their significance is still eluding me. As others noted, fixed-point combinators allow you to express a recursive function without explicit recursion. That is, instead of calling the recusrsive function, it calls lambda, which is passed as one of the arguments.

Here is one of the most understandable combinators parsers I've found:

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

Answer 5

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

Answer 6

This is a good article:

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

Code examples are provided in the diagram, but it should not be difficult to follow with them.

Answer 7

I am pretty short on theory, but I can give an example that makes my imagination rise, which may be useful to you. The simplest interesting combinator is probably a "test".

I hope you know Python

 tru = lambda x,y: x fls = lambda x,y: y test = lambda l,m,n: l(m,n) 

Using:

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

test evaluates 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 created from several basic combinators.

(This example is more or less copied from the types and programming languages ​​by Benjamin S. Pierce)

Answer 8

Soon, Y combinator is a higher-order function that is used to implement recursion on lambda expressions (anonymous functions). Check out the article How to succeed in recursion without real recursion by Mike Wannier - this is one of the best practical explanations of this issue that I have seen.

Also scan SO archives:

• What is y-combinator?
• Y-Combinator Case Study