What is a Combinator in Haskell

Question

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 ?

Answer 1

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.

Answer 2

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.

Answer 3

"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.