What Are Combinators?
Posted by Daniel Lyons Sun, 02 Sep 2007 22:51:00 GMT
This is my response to the question as asked on programming.reddit.com.
Depends on the kind. In terms of functional programming, I understand a combinator to be just a less frightening word for higher-order function. So a combinator is a function that combines the behavior of another function with its own. A good example is filter, which just removes certain items from a list. You make a short boolean function that tells you whether or not an item is worth keeping and combine it with filter and some list, and you get the list of items you wanted.
The effect is best illustrated in Haskell where you can call a function with fewer arguments than it requires. This is usually called currying. Supposing our function for determining whether or not an item is interesting is just called interesting, you can create a new function which just gives you back the list of interesting items in a list like this:
neatItems = filter interesting
For the sake of argument, suppose you consider every number one less than a number evenly divisible by three to be “interesting.”
interesting x = x `mod` 3 == 2
Try it out:
neatItems [1..10] -- produces [2,5,8]
The fun doesn’t stop here! Functional languages provide functions with no name for those times when you need to pass something to a combinator but don’t want to bother making it a name. This is usually called an anonymous function or a lambda abstraction. This means you can make neatItems without going to the trouble of defining interesting first, if (for example) you would never use it except in this function anyway:
neatItems = filter (\x -> x `mod` 3 == 2)
Incidentally, whenever you define a function that takes one or more parameters without specifying their names by using combinators, as above, you’re using what’s called points-free style. To facilitate points-free style, you can switch between names and operators in Haskell quite easily by inserting parentheses and back-tics. Haskell lets you use any binary function in-line as an operator if you put back-tics around it, or an operator as a prefix function if you surround it with parentheses, such as (-).
If you want to “curry” an operator, such as to produce a function that multiplies by two, you just put the value inside the parentheses on the side you want. Thanks to basic arithmetic, (2*) and (*2) are the same, but the variable which is “curried” is different depending on the form (the first in the first, second in the second). A “curried” operator is called a section, and I have no idea why.
Another common combinator is (.), the dot operator. Dot lets you string together functions. Suppose you have a function which takes bread and makes toast, and another function which takes toast and butters it. You could glue these two functions together with (.) and arrive at a new function which takes bread and makes buttered toast:
butteredToast = butter . toast
We can now take the above example of filter to its logical extreme by defining our “interesting” test function with sections and the dot operator:
neatItems = filter ((==2) . (`mod`3))
Now there’s no points in that function at all. It’s not exactly a win for readability in this case, however. :) A slight improvement can be made by eliminating some of those parentheses with the ($) operator, which just takes everything on the right-hand side and slaps it into parentheses as an argument to the left-hand side:
neatItems = filter $ (==2) . (`mod`3)
Eh. Still not a lot better. I’d probably take the lambda abstraction over that unless I was feeling feisty.
Combinators come up more frequently in making libraries, much like dynamic method resolution in Ruby. A great example is Parsec, which is a parser combinator library. By introducing its own BNF-style operators, Parsec lets you define parsers in a BNF-reminiscent domain specific language. It’s also good for testing because you can separately test each constituent part’s parse directly rather than being stuck with parsing whole documents. It’s also quite fast. An example from Write Yourself a Scheme in 48 Hours:
parseNumber = liftM (Number . read) $ many1 digit
parseExpr = parseAtom <|> parseString <|> parseNumber
It looks like you’re just defining a kind of token. Actually you’re defining a function with a pretty rough specification, but that’s not your problem as the API’s user. All you have to know is how to use it to parse, which looks like this:
readExpr input = case parse parseExpr "lisp" input of
Left err -> "No match: " ++ show err
Right _ -> "Found value"
I hope this answered your question!
