How do you identify monadic design patterns?

Question

I my way to learn Haskell I'm starting to grasp the monad concept and starting to use the known monads in my code but I'm still having difficulties approaching monads from a designer point of view. In OO there are several rules like, "identify nouns" for objects, watch for some kind of state and interface... but I'm not able to find equivalent resources for monads.

So how do you identify a problem as monadic in nature? What are good design patterns for monadic design? What's your approach when you realize that some code would be better refactored into a monad?

Answer 1

A helpful rule of thumb is when you see values in a context; monads can be seen as layering "effects" on:

• Maybe: partiality (uses: computations that can fail)
• Either: short-circuiting errors (uses: error/exception handling)
• [] (the list monad): nondeterminism (uses: list generation, filtering, ...)
• State: a single mutable reference (uses: state)
• Reader: a shared environment (uses: variable bindings, common information, ...)
• Writer: a "side-channel" output or accumulation (uses: logging, maintaining a write-only counter, ...)
• Cont: non-local control-flow (uses: too numerous to list)

Usually, you should generally design your monad by layering on the monad transformers from the standard Monad Transformer Library, which let you combine the above effects into a single monad. Together, these handle the majority of monads you might want to use. There are some additional monads not included in the MTL, such as the probability and supply monads.

As far as developing an intuition for whether a newly-defined type is a monad, and how it behaves as one, you can think of it by going up from Functor to Monad:

• Functor lets you transform values with pure functions.
• Applicative lets you embed pure values and express application — (<*>) lets you go from an embedded function and its embedded argument to an embedded result.
• Monad lets the structure of embedded computations depend on the values of previous computations.

The easiest way to understand this is to look at the type of join:

join :: (Monad m) => m (m a) -> m a

This means that if you have an embedded computation whose result is a new embedded computation, you can create a computation that executes the result of that computation. So you can use monadic effects to create a new computation based on values of previous computations, and transfer control flow to that computation.

Interestingly, this can be a weakness of structuring things monadically: with Applicative, the structure of the computation is static (i.e. a given Applicative computation has a certain structure of effects that cannot change based on intermediate values), whereas with Monad it is dynamic. This can restrict the optimisation you can do; for instance, applicative parsers are less powerful than monadic ones (well, this isn't strictly true, but it effectively is), but they can be optimised better.

Note that (>>=) can be defined as

m >>= f = join (fmap f m)

and so a monad can be defined simply with return and join (assuming it's a Functor; all monads are applicative functors, but Haskell's typeclass hierarchy unfortunately doesn't require this for historical reasons).

As an additional note, you probably shouldn't focus too heavily on monads, no matter what kind of buzz they get from misguided non-Haskellers. There are many typeclasses that represent meaningful and powerful patterns, and not everything is best expressed as a monad. Applicative, Monoid, Foldable... which abstraction to use depends entirely on your situation. And, of course, just because something is a monad doesn't mean it can't be other things too; being a monad is just another property of a type.

So, you shouldn't think too much about "identifying monads"; the questions are more like:

• Can this code be expressed in a simpler monadic form? With which monad?
• Is this type I've just defined a monad? What generic patterns encoded by the standard functions on monads can I take advantage of?

Answer 2

Follow the types.

If you find you have written functions with all of these types

• (a -> b) -> YourType a -> YourType b
• a -> YourType a
• YourType (YourType a) -> YourType a

or all of these types

• a -> YourType a
• YourType a -> (a -> YourType b) -> YourType b

then YourType may be a monad. (I say “may” because the functions must obey the monad laws as well.)

(Remember you can reorder arguments, so e.g. YourType a -> (a -> b) -> YourType b is just (a -> b) -> YourType a -> YourType b in disguise.)

Don't look out only for monads! If you have functions of all of these types

• YourType
• YourType -> YourType -> YourType

and they obey the monoid laws, you have a monoid! That can be valuable too. Similarly for other typeclasses, most importantly Functor.

Answer 3

There's the effect view of monads:

• Maybe - partiality / failure short-circuiting
• Either - error reporting / short-circuiting (like Maybe with more information)
• Writer - write only "state", commonly logging
• Reader - read-only state, commonly environment passing
• State - read / write state
• Resumption - pausable computation
• List - multiple successes

Once you are familiar with these effects its easy to build monads combining them with monad transformers. Note that combining some monads needs special care (particularly Cont and any monads with backtracking).

One thing important to note is there aren't many monads. There are some exotic ones that aren't in the standard libraries e.g the probability monad and variations of the Cont monad like Codensity. But unless you are doing something mathematical its unlikely you will invent (or discover) a new monad, however if you use Haskell long enough you'll build many monads that are different combinations of the standard ones.

Edit - Also note that the order you stack monad transformers results in different monads:

If you add ErrorT (transformer) to a Writer monad, you get this monad Either err (log,a) - you can only access the log if you have no error.

If you add WriterT (transfomer) to an Error monad, you get this monad (log, Either err a) which always gives access to the log.

Answer 4

This is sort of a non-answer, but I feel it is important to say anyways. Just ask! StackOverflow, /r/haskell, and the #haskell irc channel are all great places to get quick feedback from smart people. If you are working on a problem, and you suspect that there's some monadic magic that could make it easier, just ask! The Haskell community loves to solve problems, and is ridiculously friendly.

Don't misunderstand, I'm not encouraging you to never learn for yourself. Quite the contrary, interacting with the Haskell community is one of the best ways to learn. LYAH and RWH, 2 Haskell books that are freely available online, come highly recommended as well.

Oh, and don't forget to play, play, play! As you play around with monadic code, you'll start to get the feel of what "shape" monads have, and when monadic combinators can be useful. If you're rolling your own monad, then usually the type system will guide you to an obvious, simple solution. But to be honest, you should rarely need to roll your own instance of Monad, since Haskell libraries provide tons of useful things as mentioned by other answerers.

Answer 5

There's a common notion that one sees in many programming languages of an "infectious function tag" -- some special behavior for a function that must extend to its callers as well.

• Rust functions can be unsafe, meaning they perform operations that can potentially violate memory unsafety. unsafe functions can call normal functions, but any function that calls an unsafe function must be unsafe as well.
• Python functions can be async, meaning they return a promise rather than an actual value. async functions can call normal functions, but invocation of an async function (via await) can only be done by another async function.
• Haskell functions can be impure, meaning they return an IO a rather than an a. Impure functions can call pure functions, but impure functions can only be called by other impure functions.
• Mathematical functions can be partial, meaning they don't map every value in their domain to an output. The definitions of partial functions can reference total functions, but if a total function maps some of its domain to a partial function, it becomes partial as well.

While there may be ways to invoke a tagged function from an untagged function, there is no general way, and doing so can often be dangerous and threatens to break the abstraction the language tries to provide.

The benefit, then, of having tags is that you can expose a set of special primitives that are given this tag and have any function that uses these primitives make that clear in its signature.

Say you're a language designer and you recognize this pattern, and you decide that you want to allow user-defined tags. Let's say the user defined a tag Err, representing computations that may throw an error. A function using Err might look like this:

function div <Err> (n: Int, d: Int): Int
    if d == 0
        throwError("division by 0")
    else
        return (n / d)

If we wanted to simplify things, we might observe that there's nothing erroneous about taking arguments - it's computing the return value where problems might arise. So we can restrict tags to functions that take no arguments, and have div return a closure rather than the actual value:

function div(n: Int, d: Int): <Err> () -> Int
    () =>
        if d == 0
            throwError("division by 0")
        else
            return (n / d)

In a lazy language such as Haskell, we don't need the closure, and can just return a lazy value directly:

div :: Int -> Int -> Err Int
div _ 0 = throwError "division by 0"
div n d = return $ n / d

It is now apparent that, in Haskell, tags need no special language support - they are ordinary type constructors. Let's make a typeclass for them!

class Tag m where

We want to be able to call an untagged function from a tagged function, which is equivalent to turning an untagged value (a) into a tagged value (m a).

    addTag :: a -> m a

We also want to be able to take a tagged value (m a) and apply a tagged function (a -> m b) to get a tagged result (m b):

    embed :: m a -> (a -> m b) -> m b

This, of course, is precisely the definition of a monad! addTag corresponds to return, and embed corresponds to (>>=).

It is now clear that "tagged functions" are merely a type of monad. As such, whenever you spot a place where a "function tag" could apply, chances are you've got a place suitable for a monad.

P.S. Regarding the tags I've mentioned in this answer: Haskell models impurity with the IO monad and partiality with the Maybe monad. Most languages implement async/promises fairly transparently, and there seems to be a Haskell package called promise that mimics this functionality. The Err monad is equivalent to the Either String monad. I'm not aware of any language that models memory unsafety monadically, it could be done.