14

In Real World Haskell, they describe combinators like this:

In Haskell, we refer to functions that take other functions as arguments and return new functions as combinators.

And then later they state that maybeIO function is a combinator and its type signature looks like this:

maybeIO :: IO a -> IO (Maybe a)

But all I can see is that maybeIO is a function that takes a value wrapped in IO monad and returns a value in IO monad. Then how does this function become a combinator ?

2
  • 3
    There are some technical meanings of the word "combinator" but for the most part Haskell people completely ignore them. In colloquial usage it usually means "value" or "thingy".
    – shachaf
    Nov 17, 2013 at 8:58
  • 1
    The Haskell wiki has a page called Combinator with two definitions for you: haskell.org/haskellwiki/Combinator Nov 17, 2013 at 11:03

3 Answers 3

23

There are really 2 things that we could mean when we say combinator. The word is a bit overloaded.

  1. We usually mean a function which "combines" things. For example your function takes in an IO value and builds up a more complex value. Using these "combinators" we can combine and create new complex IO values from relatively few primitive functions to create IO values.

    For example, rather than creating a function which reads 10 files, we use mapM_ readFile. Here combinators are functions that we use to combine and build values

  2. The stricter computer sciencey term is a "function with no free variables". So

     -- The primitive combinators from a famous calculus, SKI calculus.
     id a         = a -- Not technically primitive, genApp const const
     const a b    = a
     genApp x y z = x z (y z)
    

    This is part of a grander field called "Combinatory logic" in which you seek to essentially eliminate free variables and replace it with combinators and a few primitive functions.

TLDR: usually when we say combinator, we refer to a more general notion called the "combinator pattern" where we have a handful of primitive functions and a lot of user-defined functions to build up more complex values.

13

There's no strict definition of a combinator, so it doesn't really mean anything in that sense. However, it is very common in Haskell to build more complex functions or values out of simpler ones, and sometimes functions doesn't fit together completely, so we use some glue to make them stick together. The bits of glue we use to do that we call combinators.

For example, if you want to compute the square root of a number rounded to the closest integer, you can write that function as

approxSqrt x = round (sqrt x)

You may also realise that what we are really doing here is taking two functions and building a more complex function using them as building blocks. We need some kind of glue to put them together, however, and that glue is (.):

approxSqrt = round . sqrt

So the function composition operator is a combinator of functions – it combines functions to create new functions. Another example is that perhaps you want to read each line of a file into a list. You could do this the obvious way:

do
  contents <- readFile "my_file.txt"
  let messages = lines contents
  ...

But! What would we do if we had a function that reads a file and returns the contents as strings? Then we could do

do
  messages <- readFileLines "my_file.txt"
  ...

As it turns out, we have a function that reads a file and we have a function that takes a big string and returns a list of the lines in it. If we only had some glue to stick those two functions together in a meaningful way, we could build readFileLines! But of course, this being Haskell, that glue is readily available.

readFileLines = fmap lines . readFile

Here we use two combinators! We use the (.) from before, and fmap is actually a very useful combinator as well. We say that it "lifts" a pure computation into the IO monad, and what we really mean is that lines has the type signature

lines :: String -> [String]

but fmap lines has the signature

fmap lines :: IO String -> IO [String]

so fmap is useful when you want to combine pure computations with IO computations.


These have just been two very simple examples. As you learn more Haskell, you'll find yourself needing (and inventing) more and more combinator functions for yourself. Haskell is very powerful in the way you can take functions and transform them, combine them, turn them inside out and then stick them together. The bits of glue we sometimes need when we do that, those bits we call combinators.

2
  • 1
    There is a strict definition of what combinator is and it comes from combinatory logic. Combinators as applied to programming languages were not invented in Haskell. The fact is that Haskell community borrowed a well-established term from computer science and started to use it here and there, polluting its meaning.
    – ᄂ ᄀ
    Jul 13, 2017 at 11:28
  • human language is like that, it's a virus. domain specific meanings need not always mean exclusivity over the use of a word or phrase. to the extent it causes little confusion in Haskell conversations it's not a big deal. And if anybody queries hackage, a first stop surely(?), the strict CL domain meaning is described first, and the casual Haskell domain usage second. Nothing to complain about, no pollution that I can see. wiki.haskell.org/Combinator May 20, 2021 at 18:56
5

"Combinator" is not exactly precisely defined in it's use in Haskell. It's most correct to use it to refer to functions which take other functions as arguments a la Combinator Calculus but in Haskell terminology it's frequently overloaded to also mean a "modification" or "combination" function, especially of a Functor or Monad. In this case you might say a combinator is a function which "takes some action or value in context and returns a new, modified action or value in context".

Your example, maybeIO is often called optional

optional :: Alternative f => f a -> f (Maybe a)
optional fa = (Just <$> fa) <|> pure Nothing

and it has a combinator-like nature because it takes the computation f a and modifies it generically to reflect failure in its value.

The reason these are called combinators as well has to do with how they're used. A typical place to see optional (and indeed, Alternative generally) is in parser combinator libraries. Here, we tend to build basic parsers using simple Parsers like

satisfy :: (Char -> Bool) -> Parser Char
anyChar    = satisfy (const True)
whitespace = satisfy isSpace
number     = satisfy isNumeric

and then we "modify" their behavior using "combinators"

-- the many and some combinators
many :: Alternative f => f a -> f [a] -- zero or more successes
some :: Alternative f => f a -> f [a] -- one  or more successes

many f = some f <|> pure []
some f = (:) <$> f <*> many f

-- the void combinator forgets what's inside the functor
void :: Functor f => f a -> f ()
void f = const () <$> f

-- from the external point of view, this is another "basic" Parser
-- ... but we know it's actually built from an even more basic one
-- and the judicious application of a few "combinators"
blankSpace = Parser ()
blankSpace = void (many whitespace)

word :: Parser String
word = many (satisfy $ not . isSpace)

Oftentimes we also call functions which combine multiple functions/Functors/Monads "combinators" as well, which perhaps makes mnemonic sense

-- the combine combinator
combine :: Applicative f => f a -> f b -> f (a, b)
combine fa fb = (,) <$> fa <*> fb

-- the ignore-what's-next combinator
(<*) :: Applicative f => f a -> f b -> f a
fa <* fb = const <$> fa <*> fb

-- the do-me-then-forget-me combinator
(*>) :: Applicative f => f a -> f b -> f b
fa *> fb = flip const <$> fa <*> fb

line = Parser String
line = many (satisfy $ \c -> c /= '\n') <* satisfy (=='\n')

But ultimately, combinators are more about the intent and usage of an API than its strict denotation. You'll frequently see libraries built up from "basic pieces" like functions or satisfy which are then modified and combined with a set of "combinators". The Parser example above is a quintessential example, but altogether this is a very common Haskell pattern.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.