hwechtla-tl: Monadic composition instead of monad transformers

Mikä on WikiWiki?
nettipäiväkirja
koko wiki (etsi)
viime muutokset

---

As we probably all know, monads are handy programming constructs that let us express different "execution environments" and operations therein in a uniform way. Every monad gives the programmer some kind of environment where it is possible perform arbitrary computations in the ordinary way, while the monad controls the workings of the environment and usually provides some additional services specific to that environment. For instance, the state monad provides an environment with two additional services, storing a value for later reference and querying the stored value. The monad takes care of threading this stored value through the whole computation, including recursive calls, etc. Any kind of effect that could be achieved through "side effects" (violations of functional purity) can be modelled as services in a monad that is specifically designed to be able to provide those services.

Different monads, then, provide useful but different services, and sometimes it happens that programmers would like to use many of those services at the same time. The topic of this article is how to best go about that. The article uses Haskell syntax with as few combinatory quirks as possible.

Problem statement

Monadic parsers are a prime example of monadic composition. A parser is a function that takes an "input stream" (a string, for instance), and returns a value (the result of parsing the beginning of the input stream) and an updated input stream, with the already parsed content removed.

 parseInt "300 square meters"  ==>  (300, " square meters")

But, it also happens that parsers are functions that can fail under invalid input. For instance, the result of parseInt "you suck" should probably not be any trash integer but rather a value denoting failure. So a parser is also an instance of the so called exception monad, a monad whose sole service is to give a possibility to abort the computation and return nothing. (The exception monad can also provide some service to perform "alternative computations", trying out another computation in case the first one fails.)

 parseInt "300 square meters"  ==>  Just (300, " square meters")
 parseInt "you suck"  ==>  Nothing

But now we have a situation where we would like to write our parsers in a monad that provides the services of both the state monad (for tracking the processing of parser input), and the exception monad (for being able to fail to parse in a practical manner, and for writing parsers that can try out several possible parses). For this, we want to compose the two monads into a single one:

 data State s a = State (s -> (a, s))
 data Maybe a = Nothing | Just a
 data Parser s a = Parser (s -> Maybe (a, s))

In Haskell, the operating system services are all provided by a mystic IO monad. Because operating systems (and the users interacting with them) live in a world where things happen in a particular order, the IO monad also imposes an order on the computation at least where it uses the operating system services in some specific fashion. Together with the IO monad, we often want to use all kinds of services, some of which can readily be modelled as monads. For instance, take the logging monad. The logging monad is a specific kind of state monad, where that only thing you can do for the "state" (which is a log of messages) is to append new messages to it. Say, we want to process a file and log messages as we go. We might have processing functions like this:

 getNextLine handle ["started processing"]
  ==>
 ("Introduction:", ["skipped comment", "processed #include", "started processing"])

Again, we would like to compose the two monads into a single one that provides both the file handling services and the logging services. There are many ways to do this, more specific ones and more generic ones.

First way: write a new monad from scratch

This isn't as bad as you think. It gives a lot of freedom to control how the monad combines the services of its component monads (in this case, components as in "sources of inspiration"). Let's see how the parser monad looks like, compared to the state and exception monads:

 instance Monad (State s) where
   State st >>= f = State (\s -> let (a, s') = st s
                                     st' = f a
                                  in st' s')
   return a = State (\s -> (a, s))

 instance Monad Maybe where
   Nothing >>= f = Nothing
   Just a >>= f = f a
   return a = Just a

 instance Monad (Parser s) where
   Parser st >>= f = \s -> case st s of
                                Nothing -> Nothing
                                Just (a, s') -> let st' = f a in st' s'
   return a = \s -> Just (a, s)

The downside, of course, is that you can't use the services provided by the existing monads but you'll have to write wrapper services for the services, in addition to the definitions of bind (>>=) and return.

Second way: transform the first monad with a monad transformer

A more efficient way (programming-wise) is to write the exception monad in a parametric form: as a monad transformer that takes an argument monad and returns a new monad with the services of the original, augmented with the fail service. The new bind (>>=) is written using the bind of the original monad, and similarly for return:

 newtype (Monad m) => MaybeT m a = MaybeT (m (Maybe a))
 instance (Monad m) => MonadPlus (MaybeT m) where
   mzero = MaybeT (return Nothing)
   mplus (MaybeT m1) m2 = m1 >>= \a -> case a of Nothing -> m2
                                                 Just x -> MaybeT (return a)
 instance (Monad m) => Monad (MaybeT m) where
   return a = MaybeT (return (Just a))
   MaybeT m >>= f = m >>= \a -> case a of Nothing -> mzero
                                          Just x -> f x
 newtype Parser s a = Parser (MaybeT (State s) a)

Now we can use the mzero and mplus services of MaybeT for failing and alternative parses, respectively, but how do we use the state-handling services of State? For that, we need to provide a service of MaybeT that lifts services of the argument monad into services of MaybeT:

 instance MonadTrans MaybeT where
   lift op = MaybeT (op >>= \a -> return (Just a))

This is all good and well, but it required us to write one of our monads in a new way, so that it can be parameterised with another. So, even if MaybeT can be composed over all other monads to provide new, exception-augmented monads, it still duplicates code with the original Maybe. The natural end result with this way of thinking is that all monads should be written as monad transformers, stacked on the serviceless identity monad (or the opaque IO monad) where no services are needed.

Third way: use the original monads to write a new one

If we can reuse the definition of the original state monad in our implementation, why not use the definition of the exception monad, too? Monad composition is fairly analogical to function composition. Our first solution above corresponds to writing a totally new function h that just happens to do everything f and g do. The second solution is equivalent to a higher order function that accepts another function and composes its workings with something of its own. But if we want to compose two functions f and g, we usually write a new function that uses f and g for its work:

 h x = g (f x)

This corresponds to the following definition, which reuses the binds and returns of the state and exception monads for providing its own definitions. (TODO: can this actually be done?)

kategoria: ohjelmointi kategoria: keskeneräiset

Pikalinkit:

• Problem statement
• First way: write a new monad from scratch
• Second way: transform the first monad with a monad transformer
• Third way: use the original monads to write a new one