# What are combinators and how are they applied to programming projects? (practical explanation)

What are combinators?

I'm looking for:

• a practical explanation
• examples of how they are used
• examples of how combinators improve the quality/generality of code

I'm not looking for:

• explanations of combinators that don't help me get work done (such as the Y-combinator)
• Combinators are similar to "adverbs", functions that take in functions then return other functions. They can help remove duplication of code because you don't need in between variables. Some useful ones are twice(f) = \x -> f(f(x)), flip(op)-> \x y -> y op x, (.) as in (f.g) x = f(g(x)), (\$) can help with map(called <\$> in infix) as in (\$5) <\$> [(+1), (*2)] = [6, 10], curry can be used in Lisp/Python/JavaScript for partial application, and uncurry can be used for functions that require records(tuples) in Haskell. When x |> f = f a, x |> (length &&& sum) |> uncurry (/) is the average. – aoeu256 Aug 4 '19 at 20:37

From a practical viewpoint combinators are kind of programming constructs that allow you to put together pieces of logic in interesting and often advanced manners. Typically using them depends on the possibility of being able to pack executable code into objects, often called (for historical reasons) lambda functions or lambda expressions, but your mileage can vary.

A simple example of a (useful) combinator is one that takes two lambda functions without parameters, and creates a new one that runs them in sequence. The actual combinator looks in generic pseudocode like this:

``````func in_sequence(first, second):
lambda ():
first()
second()
``````

The crucial thing that makes this a combinator is the anonymous function (lambda function) on the second line; when you call

``````a = in_sequence(f, g)
``````

the resulting object a is not the result of running first f() and then g(), but it is an object that you can call later to execute f() and g() in sequence:

``````a() // a is a callable object, i.e. a function without parameters
``````

You can similarly then have a combinator that runs two code blocks in parallel:

``````func in_parallel(first, second):
lambda ():
wait(t1)
wait(t2)
``````

And then again,

``````a = in_parallel(f, g)
a()
``````

The cool thing is that 'in_parallel' and 'in_sequence' are both combinators with the same type / signature, i.e. they both take two parameterless function objects and return a new one. You can actually then write things like

``````a = in_sequence(in_parallel(f, g), in_parallel(h, i))
``````

and it works as expected.

Basically so combinators allow you to construct your program's control flow (among other things) in a procedural and flexible fashion. For example, if you use in_parallel(..) combinator to run parallelism in your program, you can add debugging related to that to the implementation of the in_parallel combinator itself. Later, if you suspect that your program has parallelism-related bug, you can actually just reimplement in_parallel:

``````in_parallel(first, second):
in_sequence(first, second)
``````

and with one stroke, all the parallel sections have been converted into sequential ones!

Combinators are very useful when used right.

The Y combinator, however, is not needed in real life. It is a combinator that allows you to create self-recursive functions, and you can create them easily in any modern language without the Y combinator.

It is wrong to brand Y-combinator as something that won't "help to get the work done". I've found it very useful in a number of occasions. The most obvious case is when you have to quickly bootstrap some embedded interpreted language. If you provide a minimal set of primitives, namely `sequence`, `select`, `call`, `const` and a `closure allocation`, it is already sufficient for building up a complete, arbitrary complex language. No special support for recursion is needed - it can be added via a fixed point combinator. Otherwise you'll need much more complicated primitives.

Another obvious case for combinators is obfuscation. A code translated into the SKI calculus is practically unreadable. If you really have to obfuscate an implementation of an algorithm, consider using combinators, here is an example.

And, of course, combinators are an important tool for implementing functional languages. The easiest approach (as in the example above) is via SKI or equivalent calculus. Supercombinators are used in some other implementations. This book talks about it in depth.

This is a joke, but a joke worth a very careful reading, since many arcane programming techniques and theories are covered there.

• @MattFenwick, a need to drop in a simple embedded interpreter often arises where you will never expect it. E.g., in my case it was a language I had to design in order to extend a communication protocol. Simple IPC was not enough, so the protocol had to be executable. – SK-logic Nov 3 '11 at 13:31
• @MattFenwick, as for your question: you can try writing some code in APL or J. Combinators are essential there, so you'll get an idea of how to apply them properly. Also, reading on point-free style may help: en.wikipedia.org/wiki/Tacit_programming – SK-logic Nov 3 '11 at 13:33

Digging around a bit, I found a StackOverflow question, Good explanation of “Combinators” (For non mathematicians) that's a close cousin of this question. One of the answers pointed to Reginald Braithwaite's blog, Homoiconic, which links to several useful examples of combinators in code (e.g. the K combinator, implemented by Ruby's `Object#tap` method - read the page for examples of why it's useful).