[Haskell-beginners] combinator

[Brent Yorgey]

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
> <christopher.howard at frigidcode.com> 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