Explanation of combinators for the working man

Question

What is a combinator??

Is it "a function or definition with no free variables" (as defined on SO)?

Or how about this: according to John Hughes in his well-known paper on Arrows, "a combinator is a function which builds program fragments from program fragments", which is advantageous because "... the programmer using combinators constructs much of the desired program automatically, rather than writing every detail by hand". He goes on to say that map and filter are two common examples of such combinators.

Some combinators which match the first definition:

• S
• K
• Y
• others from To Mock a Mockingbird (I may be wrong -- I haven't read this book)

Some combinators which match the second definition:

• map
• filter
• fold/reduce (presumably)
• any of >>=, compose, fmap ?????

I'm not interested in the first definition -- those would not help me to write a real program (+1 if you convince me I'm wrong). Please help me understand the second definition. I think map, filter, and reduce are useful: they allow me to program at a higher level -- fewer mistakes, shorter and clearer code. Here are some of my specific questions about combinators:

1. What are more examples of combinators such as map, filter?
2. What combinators do programming languages often implement?
3. How can combinators help me design a better API?
4. How do I design effective combinators?
5. What are combinators similar to in a non-functional language (say, Java), or what do these languages use in place of combinators?

---

Update

Thanks to @C. A. McCann, I now have a somewhat better understanding of combinators. But one question is still a sticking point for me:

What is the difference between a functional program written with, and one written without, heavy use of combinators?

I suspect the answer is that the combinator-heavy version is shorter, clearer, more general, but I would appreciate a more in-depth discussion, if possible.

I'm also looking for more examples and explanations of complex combinators (i.e. more complex than fold) in common programming languages.

Answer 1

I'm not interested in the first definition -- those would not help me to write a real program (+1 if you convince me I'm wrong). Please help me understand the second definition. I think map, filter, and reduce are useful: they allow me to program at a higher level -- fewer mistakes, shorter and clearer code.

The two definitions are basically the same thing. The first is based on the formal definition and the examples you give are primitive combinators--the smallest building blocks possible. They can help you to write a real program insofar as, with them, you can build more sophisticated combinators. Think of combinators like S and K as the machine language of a hypothetical "combinatory computer". Actual computers don't work that way, of course, so in practice you'll usually have higher-level operations implemented behind the scenes in other ways, but the conceptual foundation is still a useful tool for understanding the meaning of those higher-level operations.

The second definition you give is more informal and about using more sophisticated combinators, in the form of higher-order functions that combine other functions in various ways. Note that if the basic building blocks are the primitive combinators above, everything built from them is a higher-order function and a combinator as well. In a language where other primitives exist, however, you have a distinction between things that are or are not functions, in which case a combinator is typically defined as a function that manipulates other functions in a general way, rather than operating on any non-function things directly.

What are more examples of combinators such as map, filter?

Far too many to list! Both of those transform a function that describes behavior on a single value into a function that describes behavior on an entire collection. You can also have functions that transform only other functions, such as composing them end-to-end, or splitting and recombining arguments. You can have combinators that turn single-step operations into recursive operations that produce or consume collections. Or all kinds of other things, really.

What combinators do programming languages often implement?

That's going to vary quite a bit. There're relatively few completely generic combinators--mostly the primitive ones mentioned above--so in most cases combinators will have some awareness of any data structures being used (even if those data structures are built out of other combinators anyway), in which case there are typically a handful of "fully generic" combinators and then whatever various specialized forms someone decided to provide. There are a ridiculous number of cases where (suitably generalized versions of) map, fold, and unfold are enough to do almost everything you might want.

How can combinators help me design a better API?

Exactly as you said, by thinking in terms of high-level operations, and the way those interact, instead of low-level details.

Think about the popularity of "for each"-style loops over collections, which let you abstract over the details of enumerating a collection. These are just map/fold operations in most cases, and by making that a combinator (rather than built-in syntax) you can do things such as take two existing loops and directly combine them in multiple ways--nest one inside the other, do one after the other, and so on--by just applying a combinator, rather than juggling a whole bunch of code around.

How do I design effective combinators?

First, think about what operations make sense on whatever data your program uses. Then think about how those operations can be meaningfully combined in generic ways, as well as how operations can be broken down into smaller pieces that are connected back together. The main thing is to work with transformations and operations, not direct actions. When you have a function that just does some complicated bit of functionality in an opaque way and only spits out some sort of pre-digested result, there's not much you can do with that. Leave the final results to the code that uses the combinators--you want things that take you from point A to point B, not things that expect to be the beginning or end of a process.

What are combinators similar to in a non-functional language (say, Java), or what do these languages use in place of combinators?

Ahahahaha. Funny you should ask, because objects are really higher-order thingies in the first place--they have some data, but they also carry around a bunch of operations, and quite a lot of what constitutes good OOP design boils down to "objects should usually act like combinators, not data structures".

So probably the best answer here is that instead of combinator-like things, they use classes with lots of getter and setter methods or public fields, and logic that mostly consists of doing some opaque, predefined action.