Combinators Part I: The fall of society

Inevitably the title has you thinking "shit, some self-important ass is trying to convince me his favorite technology is the real silver bullet". Actually, I only put the fall of society in the title because I couldn't come up with anything meaningful, so I chose something fun instead. Bet you've never written anything titled The fall of society have you?

So are combinators a silver bullet? No. What? No, that doesn't even make sense.

Now that's out of the way, what are combinators? I'm glad I'm asking that because it's kind of a trick question. Unfortunately I have to answer it, so bear with me as my answer will be wrong. Well, not technically wrong, just not always right. The term has been used with a variety of rules to define it, so let's build the definition rule by rule, and hopefully after we're done you will understand why these rules matter.

Also side note, as I go I'll be giving examples in C# just because it's a language familiar to enough people which is capable of creating combinators.

Rule #1 A combinator may treat a function like a parameter, this is known as being a "higher-order function".
To give some quick examples of higher-order functions here:

A function that takes a function is a higher-order function:

public int Alter(int numberToAlter, Func<int,int> functionAsParameter)
{
    return functionAsParameter(numberToAlter);
}

This is useful because the extra layer of abstraction we get by letting our consumer's give us a function allows them to tell our code how to behave rather than relying on us to implement every permutation of our code they could possibly want.

A function that returns a function is a higher-order function:

public Func<int,int> GetAdder(int numberToAdd)
{
    return new Func<int,int>(x => x + numberToAdd);
}

Returning a function is great anytime you want to give your consumers something they can execute later, or give them a stencil they can reuse with various values if they have a selection of things they need to affect.

Rule #2 A combinator must be Pure. Pure? Yeah I know, people have weird words for this stuff. It just means it cannot change anything, only create things. For example:

public Person SetName(Person personWhoseNameToSet, string name)
{
    return new Person(personWhoseNameToSet.Age, personWhoseNameToSet.Height, name);
}

Notice how this function doesn't actually change anything at all, it just creates something new and returns it. A pure function by definition is incapable of affecting any other part of your system, this means it is both unaffected by the entire application and incapable of affecting it. Since it is not affected by any part of your application, it will not be broken by other parts of your application, and since it doesn't affect other parts it may not break other parts of your application. Let that sink in for a moment before moving on, because this is important, and surprisingly valuable behaviour. Also, it will be "idempotent" (yeah I know, I'm not even sure how to pronounce that one), which just means given the same inputs, it will return the same outputs every single time. Purity gives us idempotence which means the results from a unit test are guaranteed identical to the results from the same call in the real world.

Rule #3 A combinator may only use function application and earlier defined combinators. Function application simply means applying a function to a value or executing a function with a parameter in more imperative terms. For example:

int someNum = Increment(42);
int anotherNum = Increment(someNum);

You can see in the first line, the function Increment is applied to the value 42. On the second line the function Increment is being applied to the value someNum. This is "function application", nothing fancy or complex. But what good does only using function application or other combinators do for us? A number of things actually:

• Guarantee's purity so you get the benefits from applying rule #2 above without having to think about how.
• Give's a great deal of information about what it's going to do simply by the knowledge that it's only got one tool at it's disposal, function application.
• Ensures (generally) the function will be small, since there is one statement in the whole function due to no assignment. Multiple statements would be pointless, as only the result from the last one can be returned, and the previous ones being pure wouldn't do anything in the system.
• Makes it altogether easy to reason about.

Ok, so these all sound like beneficial rules to abide by, but what do we get for utilizing them together? The Combinator!! It may sound silly, but after you've worked with them for a while you'll find them exciting too. The true magic of the combinator is hidden right in it's name: it combines things. Think of it like a blender, you put some juice, fruit, yogurt, and ice all in there together, and it combines them, the result being far more pleasant than the sum of it's parts (try putting those things together in a cup without blending them first, clearly the version that went through the combinator came out more valuable).

However with combinator's in programming the result is less the point, it's the simplicity of that activity that makes them great. To a consumer, combinator's present a simple to use API for taking little parts, and combining them into greater wholes.

The perfect example I like to use for showing people this truth is (and bear with me if you don't know this technology) LINQ. In .NET there is a whole library of combinators called LINQ, and few fans of .NET wouldn't agree LINQ hugely changed the way they write code. The magic as I mentioned is the ease in which you can take small parts, and build them up into larger and larger more complete systems. Let's look at an example of this.

public int AverageNumberOfBrownHairs(IEnumerable<Person> people)
{
    return people
        .Select(person => person.Hairs.Where(hair => hair.Color == Brown))
        .Select(hairs => hairs.Count())
        .Average();
}

Look how simple and small that is, and yet it's got 3 outer loops, 1 nested loop, and tons of assignments for you to keep track of in it's logic if you were to implement it imperatively. Thanks to the Select, Where, and Average combinators though we are able to do the whole thing by simply combining 3 itty bitty functions which exist as parameters. The other huge bonus is, we could now use AverageNumberOfBrownHairs as a combinator to combine with other combinators, since using combinators was so easy the only tool we needed was function application therefore we created another combinator. This is a totally common result of using combinators and how using them makes your code not only easier to implement, but also easier to consume and reason about.

That's really it in a nut shell, think about the imperative implementation of the above and you'll see that the version relying on combinators is far simpler while still being extremely easy to reason about.

So just to repeat what I said at the beginning here, am I trying to sell a silver bullet? No, absolutely not. A program built only from combinators may become a huge mess for all I know, but judicious use of combinators for the right tasks have the ability to really help DRY up your code as well as making it easier to reason about. Think of it again like the blender analogy, the best use of a blender is with the addition of substantive things like limes, ice, coke, and meyers. So it is with combinators in code, they're great for combining independent pieces of substantive code into cohesive modules, and then again combining those modules into a whole program.

Das Ende. Fin. Stay tuned for Part II which will go in-depth into a particular use-case for combinators and detail a few scenarios which should trigger you to start using them.