Combinators in Programming – Practical Explanation

functional programmingprogramming practices

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)

Best Answer

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 ():
    t1 = start_thread(first)
    t2 = start_thread(second)
    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.

Related Topic