Re: [Haskell-beginners] combinator

On Thu, Sep 20, 2012 at 01:24:54PM +0200, Henk-Jan van Tuyl wrote:

On Thu, 20 Sep 2012 12:59:11 +0200, Christopher Howard wrote:

...

Is there some kind soul who would elaborate somewhat on what exactly a combinator is, and the significance they have in Haskell programming? Is there anything special about the way that we use the term in a Haskell programming context? Are combinators tied into everything we do in Haskell, or is it more of a special branch of study?

A year or two ago I studied some lambda calculus, and I remember some interesting (but rather theoretical) little problems involving properties of certain combinators, and how they behaved when combined with others. But in some Haskell module documentation, it seems like everything and anything is referred to as a "combinator", so I'm getting a bit confused.

There is a short explanation in the HaskellWiki[0]

Regards, Henk-Jan van Tuyl

[0] http://www.haskell.org/haskellwiki/Combinator

The reason you are getting confused is quite simple: there are two distinct meanings of the word "combinator"! The definition on the page Henk-Jan referred to above is a technical meaning, which is the same as what you encountered when studying the lambda calculus. A "function with no free variables" is a pure lambda-expression that refers only to its arguments, like \a -> a \a -> \b -> a \f -> \a -> \b -> f b a and so on. If you hear about the study of "combinatory logic", this is what is being discussed. We do use such things in Haskell -- the examples above are id, const, and flip respectively. Many of the functions involved in the Applicative instance for ((->) e) also fall into this category. But such examples are fairly limited. However, when you read about "combinators" in module documentation, 99% of the time the word is being used with a different meaning. There, it is a more informal sense referring to a style of organizing libraries, centered around the idea of combining things. Usually there is some type T, some functions for constructing "primitive" values of type T, and some "combinators" which can *combine* values of type T in various ways to build up more complex values of type T. For example, my diagrams library (see e.g. http://hackage.haskell.org/package/diagrams%2Dlib) is organized in this way: there are various ways to construct "primitive" diagrams (e.g. 'square', 'circle', etc.) and then a large collection of combinators for combining diagrams into more complex diagrams (e.g. putting them on top of each other, next to each other, in a row, etc.). Hope this helps clear things up. And I guess I really ought to update that wiki page. -Brent