Why do we need monads?

In my humble opinion the answers to the famous question "What is a monad?", especially the most voted ones, try to explain what is a monad without clearly explaining why monads are really necessary. Can they be explained as the solution to a problem?

Solution 1:

Why do we need monads?

1. We want to program only using functions. ("functional programming (FP)" after all).

2. Then, we have a first big problem. This is a program:

   f(x) = 2 * x

   g(x,y) = x / y

   How can we say what is to be executed first? How can we form an ordered sequence of functions (i.e. a program) using no more than functions?

   Solution: compose functions. If you want first g and then f, just write f(g(x,y)). This way, "the program" is a function as well: main = f(g(x,y)). OK, but ...

3. More problems: some functions might fail (i.e. g(2,0), divide by 0). We have no "exceptions" in FP (an exception is not a function). How do we solve it?

   Solution: Let's allow functions to return two kind of things: instead of having g : Real,Real -> Real (function from two reals into a real), let's allow g : Real,Real -> Real | Nothing (function from two reals into (real or nothing)).

4. But functions should (to be simpler) return only one thing.

   Solution: let's create a new type of data to be returned, a "boxing type" that encloses maybe a real or be simply nothing. Hence, we can have g : Real,Real -> Maybe Real. OK, but ...

5. What happens now to f(g(x,y))? f is not ready to consume a Maybe Real. And, we don't want to change every function we could connect with g to consume a Maybe Real.

   Solution: let's have a special function to "connect"/"compose"/"link" functions. That way, we can, behind the scenes, adapt the output of one function to feed the following one.

   In our case: g >>= f (connect/compose g to f). We want >>= to get g's output, inspect it and, in case it is Nothing just don't call f and return Nothing; or on the contrary, extract the boxed Real and feed f with it. (This algorithm is just the implementation of >>= for the Maybe type). Also note that >>= must be written only once per "boxing type" (different box, different adapting algorithm).

6. Many other problems arise which can be solved using this same pattern: 1. Use a "box" to codify/store different meanings/values, and have functions like g that return those "boxed values". 2. Have a composer/linker g >>= f to help connecting g's output to f's input, so we don't have to change any f at all.

7. Remarkable problems that can be solved using this technique are:

   • having a global state that every function in the sequence of functions ("the program") can share: solution StateMonad.

   • We don't like "impure functions": functions that yield different output for same input. Therefore, let's mark those functions, making them to return a tagged/boxed value: IO monad.

Total happiness!

Solution 2:

The answer is, of course, "We don't". As with all abstractions, it isn't necessary.

Haskell does not need a monad abstraction. It isn't necessary for performing IO in a pure language. The IO type takes care of that just fine by itself. The existing monadic desugaring of do blocks could be replaced with desugaring to bindIO, returnIO, and failIO as defined in the GHC.Base module. (It's not a documented module on hackage, so I'll have to point at its source for documentation.) So no, there's no need for the monad abstraction.

So if it's not needed, why does it exist? Because it was found that many patterns of computation form monadic structures. Abstraction of a structure allows for writing code that works across all instances of that structure. To put it more concisely - code reuse.

In functional languages, the most powerful tool found for code reuse has been composition of functions. The good old (.) :: (b -> c) -> (a -> b) -> (a -> c) operator is exceedingly powerful. It makes it easy to write tiny functions and glue them together with minimal syntactic or semantic overhead.

But there are cases when the types don't work out quite right. What do you do when you have foo :: (b -> Maybe c) and bar :: (a -> Maybe b)? foo . bar doesn't typecheck, because b and Maybe b aren't the same type.

But... it's almost right. You just want a bit of leeway. You want to be able to treat Maybe b as if it were basically b. It's a poor idea to just flat-out treat them as the same type, though. That's more or less the same thing as null pointers, which Tony Hoare famously called the billion-dollar mistake. So if you can't treat them as the same type, maybe you can find a way to extend the composition mechanism (.) provides.

In that case, it's important to really examine the theory underlying (.). Fortunately, someone has already done this for us. It turns out that the combination of (.) and id form a mathematical construct known as a category. But there are other ways to form categories. A Kleisli category, for instance, allows the objects being composed to be augmented a bit. A Kleisli category for Maybe would consist of (.) :: (b -> Maybe c) -> (a -> Maybe b) -> (a -> Maybe c) and id :: a -> Maybe a. That is, the objects in the category augment the (->) with a Maybe, so (a -> b) becomes (a -> Maybe b).

And suddenly, we've extended the power of composition to things that the traditional (.) operation doesn't work on. This is a source of new abstraction power. Kleisli categories work with more types than just Maybe. They work with every type that can assemble a proper category, obeying the category laws.

1. Left identity: id . f = f
2. Right identity: f . id = f
3. Associativity: f . (g . h) = (f . g) . h

As long as you can prove that your type obeys those three laws, you can turn it into a Kleisli category. And what's the big deal about that? Well, it turns out that monads are exactly the same thing as Kleisli categories. Monad's return is the same as Kleisli id. Monad's (>>=) isn't identical to Kleisli (.), but it turns out to be very easy to write each in terms of the other. And the category laws are the same as the monad laws, when you translate them across the difference between (>>=) and (.).

So why go through all this bother? Why have a Monad abstraction in the language? As I alluded to above, it enables code reuse. It even enables code reuse along two different dimensions.

The first dimension of code reuse comes directly from the presence of the abstraction. You can write code that works across all instances of the abstraction. There's the entire monad-loops package consisting of loops that work with any instance of Monad.

The second dimension is indirect, but it follows from the existence of composition. When composition is easy, it's natural to write code in small, reusable chunks. This is the same way having the (.) operator for functions encourages writing small, reusable functions.

So why does the abstraction exist? Because it's proven to be a tool that enables more composition in code, resulting in creating reusable code and encouraging the creation of more reusable code. Code reuse is one of the holy grails of programming. The monad abstraction exists because it moves us a little bit towards that holy grail.

Solution 3:

Benjamin Pierce said in TAPL

A type system can be regarded as calculating a kind of static approximation to the run-time behaviours of the terms in a program.

That's why a language equipped with a powerful type system is strictly more expressive, than a poorly typed language. You can think about monads in the same way.

As @Carl and sigfpe point, you can equip a datatype with all operations you want without resorting to monads, typeclasses or whatever other abstract stuff. However monads allow you not only to write reusable code, but also to abstract away all redundant detailes.

As an example, let's say we want to filter a list. The simplest way is to use the filter function: filter (> 3) [1..10], which equals [4,5,6,7,8,9,10].

A slightly more complicated version of filter, that also passes an accumulator from left to right, is

swap (x, y) = (y, x)
(.*) = (.) . (.)

filterAccum :: (a -> b -> (Bool, a)) -> a -> [b] -> [b]
filterAccum f a xs = [x | (x, True) <- zip xs $ snd $ mapAccumL (swap .* f) a xs]

To get all i, such that i <= 10, sum [1..i] > 4, sum [1..i] < 25, we can write

filterAccum (\a x -> let a' = a + x in (a' > 4 && a' < 25, a')) 0 [1..10]

which equals [3,4,5,6].

Or we can redefine the nub function, that removes duplicate elements from a list, in terms of filterAccum:

nub' = filterAccum (\a x -> (x `notElem` a, x:a)) []

nub' [1,2,4,5,4,3,1,8,9,4] equals [1,2,4,5,3,8,9]. A list is passed as an accumulator here. The code works, because it's possible to leave the list monad, so the whole computation stays pure (notElem doesn't use >>= actually, but it could). However it's not possible to safely leave the IO monad (i.e. you cannot execute an IO action and return a pure value — the value always will be wrapped in the IO monad). Another example is mutable arrays: after you have leaved the ST monad, where a mutable array live, you cannot update the array in constant time anymore. So we need a monadic filtering from the Control.Monad module:

filterM          :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
filterM _ []     =  return []
filterM p (x:xs) =  do
   flg <- p x
   ys  <- filterM p xs
   return (if flg then x:ys else ys)

filterM executes a monadic action for all elements from a list, yielding elements, for which the monadic action returns True.

A filtering example with an array:

nub' xs = runST $ do
        arr <- newArray (1, 9) True :: ST s (STUArray s Int Bool)
        let p i = readArray arr i <* writeArray arr i False
        filterM p xs

main = print $ nub' [1,2,4,5,4,3,1,8,9,4]

prints [1,2,4,5,3,8,9] as expected.

And a version with the IO monad, which asks what elements to return:

main = filterM p [1,2,4,5] >>= print where
    p i = putStrLn ("return " ++ show i ++ "?") *> readLn

E.g.

return 1? -- output
True      -- input
return 2?
False
return 4?
False
return 5?
True
[1,5]     -- output

And as a final illustration, filterAccum can be defined in terms of filterM:

filterAccum f a xs = evalState (filterM (state . flip f) xs) a

with the StateT monad, that is used under the hood, being just an ordinary datatype.

This example illustrates, that monads not only allow you to abstract computational context and write clean reusable code (due to the composability of monads, as @Carl explains), but also to treat user-defined datatypes and built-in primitives uniformly.

Solution 4:

I don't think IO should be seen as a particularly outstanding monad, but it's certainly one of the more astounding ones for beginners, so I'll use it for my explanation.

Naïvely building an IO system for Haskell

The simplest conceivable IO system for a purely-functional language (and in fact the one Haskell started out with) is this:

main₀ :: String -> String
main₀ _ = "Hello World"

With lazyness, that simple signature is enough to actually build interactive terminal programs – very limited, though. Most frustrating is that we can only output text. What if we added some more exciting output possibilities?

data Output = TxtOutput String
            | Beep Frequency

main₁ :: String -> [Output]
main₁ _ = [ TxtOutput "Hello World"
          -- , Beep 440  -- for debugging
          ]

cute, but of course a much more realistic “alterative output” would be writing to a file. But then you'd also want some way to read from files. Any chance?

Well, when we take our main₁ program and simply pipe a file to the process (using operating system facilities), we have essentially implemented file-reading. If we could trigger that file-reading from within the Haskell language...

readFile :: Filepath -> (String -> [Output]) -> [Output]

This would use an “interactive program” String->[Output], feed it a string obtained from a file, and yield a non-interactive program that simply executes the given one.

There's one problem here: we don't really have a notion of when the file is read. The [Output] list sure gives a nice order to the outputs, but we don't get an order for when the inputs will be done.

Solution: make input-events also items in the list of things to do.

data IO₀ = TxtOut String
         | TxtIn (String -> [Output])
         | FileWrite FilePath String
         | FileRead FilePath (String -> [Output])
         | Beep Double

main₂ :: String -> [IO₀]
main₂ _ = [ FileRead "/dev/null" $ \_ ->
             [TxtOutput "Hello World"]
          ]

Ok, now you may spot an imbalance: you can read a file and make output dependent on it, but you can't use the file contents to decide to e.g. also read another file. Obvious solution: make the result of the input-events also something of type IO, not just Output. That sure includes simple text output, but also allows reading additional files etc..

data IO₁ = TxtOut String
         | TxtIn (String -> [IO₁])
         | FileWrite FilePath String
         | FileRead FilePath (String -> [IO₁])
         | Beep Double

main₃ :: String -> [IO₁]
main₃ _ = [ TxtIn $ \_ ->
             [TxtOut "Hello World"]
          ]

That would now actually allow you to express any file operation you might want in a program (though perhaps not with good performance), but it's somewhat overcomplicated:

• main₃ yields a whole list of actions. Why don't we simply use the signature :: IO₁, which has this as a special case?

• The lists don't really give a reliable overview of program flow anymore: most subsequent computations will only be “announced” as the result of some input operation. So we might as well ditch the list structure, and simply cons a “and then do” to each output operation.

data IO₂ = TxtOut String IO₂
         | TxtIn (String -> IO₂)
         | Terminate

main₄ :: IO₂
main₄ = TxtIn $ \_ ->
         TxtOut "Hello World"
          Terminate

Not too bad!

So what has all of this to do with monads?

In practice, you wouldn't want to use plain constructors to define all your programs. There would need to be a good couple of such fundamental constructors, yet for most higher-level stuff we would like to write a function with some nice high-level signature. It turns out most of these would look quite similar: accept some kind of meaningfully-typed value, and yield an IO action as the result.

getTime :: (UTCTime -> IO₂) -> IO₂
randomRIO :: Random r => (r,r) -> (r -> IO₂) -> IO₂
findFile :: RegEx -> (Maybe FilePath -> IO₂) -> IO₂

There's evidently a pattern here, and we'd better write it as

type IO₃ a = (a -> IO₂) -> IO₂    -- If this reminds you of continuation-passing
                                  -- style, you're right.

getTime :: IO₃ UTCTime
randomRIO :: Random r => (r,r) -> IO₃ r
findFile :: RegEx -> IO₃ (Maybe FilePath)

Now that starts to look familiar, but we're still only dealing with thinly-disguised plain functions under the hood, and that's risky: each “value-action” has the responsibility of actually passing on the resulting action of any contained function (else the control flow of the entire program is easily disrupted by one ill-behaved action in the middle). We'd better make that requirement explicit. Well, it turns out those are the monad laws, though I'm not sure we can really formulate them without the standard bind/join operators.

At any rate, we've now reached a formulation of IO that has a proper monad instance:

data IO₄ a = TxtOut String (IO₄ a)
           | TxtIn (String -> IO₄ a)
           | TerminateWith a

txtOut :: String -> IO₄ ()
txtOut s = TxtOut s $ TerminateWith ()

txtIn :: IO₄ String
txtIn = TxtIn $ TerminateWith

instance Functor IO₄ where
  fmap f (TerminateWith a) = TerminateWith $ f a
  fmap f (TxtIn g) = TxtIn $ fmap f . g
  fmap f (TxtOut s c) = TxtOut s $ fmap f c

instance Applicative IO₄ where
  pure = TerminateWith
  (<*>) = ap

instance Monad IO₄ where
  TerminateWith x >>= f = f x
  TxtOut s c >>= f = TxtOut s $ c >>= f
  TxtIn g >>= f = TxtIn $ (>>=f) . g

Obviously this is not an efficient implementation of IO, but it's in principle usable.