© Copyright 2007 Bolour Computing.

Monads through Pictures

Azad Bolour
Bolour Computing

Introduction

Monads in functional programming provide a framework for aspect-aware computations to be composed to build higher-level aspect-aware computations. An aspect-aware computation is some basic computation that has been enhanced, augmented, or, more generally, just transformed, to become aware of some generic concern.

Consider, for example, the well-known maybe monad. This monad provides a basis for composing null-aware functions. As an example of the use of this monad, suppose we are working with floating point arithmetic. Monadic null-aware functions would then augment basic floating point functions by returning null values where the underlying floating point function is undefined, as in the square root of negative numbers.

To add the nullability aspect to arithmetic functions, the implementer of the basic floating point library would have to provide null-aware variants for each basic floating point function.

But, and here is the crucial point, once that basis is in place in terms of the maybe monad, that is, once basic arithmetic functions are transformed to return Maybe Float values rather than merely Float values, the maybe monad allows higher-level computations required by an application to be built up from these basic null-aware functions in much the same way as if these functions were being composed by ordinary function application.

The counterpart of ordinary function application for the maybe monad is the maybe monad's bind operator. This bind operator is a generic null-propagating application operator. And by using it, the higher-level application programmer is freed from the burden of doing explicit null propagation in a nested application of arithmetic functions.

In the interest of full disclosure, as we'll see in a later article, this idea of adding aspect-awareness to a system of functions is not the whole story on monads. But it is a great way to start thinking about them. And in much of this article, we'll just go with that interpretation.

An excellent treatment of monads appears in a blog by Dan Piponi, You Could Have Invented Monads and Maybe You Have, where the concept of a monad is clearly motivated and derived from first principles.

I have found that the introduction a few key pieces of terminology, and the pictorial representation of some of the basic concepts of programming with monads, have enhanced my grasp of the idea of a monad, and my conversations about it with others. In this article, I'll share some of that terminology and pictures by using them to retrace the development of the idea of a monad. Of course, such retracing is going to be an elaboration of what has come before. In particular, what follows derives a great deal from You Could Have Invented Monads and Maybe You Have.

Monad Structure

A monad in Haskell is a generic type of a single type parameter, with two main operations: return and bind (>>=), and certain mandated behavioral rules governing these operations. The Haskell type class, Monad, defines the interface for these operations.

  class Monad monad where
    (>>=) :: forall input output .  
      monad input -> (input -> monad output) -> monad output
    return :: input -> monad input
      ...

I'll call an instance of this type class, that is, an implementation of the interface defined by this class, a monadic type. Such a type defines a generic data structure of a single type parameter to represent monadic values, and provides generic implementations for the monadic operations of return and bind. I'll call a monad's type parameter, its substrate.

A simple example of a monad is the list monad, whose generic data structure, the list, represents a sequence of values of its substrate. Thus, the substrate of the list monad [Int] is Int.

As another example, the generic data structure representing the values of the maybe monad is the variant data structure Nothing | Just substrate, where the constant Nothing represents a null value, and the constructor Just substrate represents an actual substrate value.

In general, the generic data structure representing a monad may be arbitrarily composed of the values of the monad's substrate (and possibly of other types), by using data constructors to combine basic structuring primitives such as tuple, list, and function.

Figure 1 shows the static structure of a monadic value as a data structure containing certain designated slots which take on substrate values.

Figure-1

Figure 1. Monads and Substrates

Depending on context, the word monad actually has four different connotations, designating four different levels of abstraction.

In the remainder of this paper, to minimize verbiage, I will sometimes use the word monad loosely without qualification, when there is a reasonable chance that its specific connotation is clear from context.

Monad Producers

As we saw earlier, programming with a given monadic type involves working with aspect-aware functions that know about the generic concern or aspect supported by that monadic type. I'll call such functions monad producers. A monad producer is a function that takes a value of some substrate type as input and produces a monadic value, possibly of another substrate type, as output. Typically, a monad producer is a transformed version of a more primitive substrate-to-substrate computation, that endows that primitive computation with the aspect supported by the monad, and that returns a monadic value that captures the effect of adding that aspect to the primitive computation.

As an example, a list monad producer might augment a normal computation to one that returns a sequence of values of a given substrate rather than just one. For instance, a basic search algorithm might return a single solution to a system of constraints. But an enhanced optimizing search algorithm might return a list of high-valued solutions to the same system of constraints.

Figure 2 represents the general concept of a monad producer.

Figure-2

Figure 2. Monad Producer

Return - The Degenerate Monad Producer

We have seen that a monad producer is typically an aspect-enhanced version of a substrate-to-substrate function. The return function of a given monad may be thought of as the aspect-enhanced version of the identity function. It takes a substrate value and endows it with the aspect supported by that monad.

For example, the return function of the list monad encapsulates a substrate value within a list: return value = [value]; and the return function of the maybe monad encapsulates a substrate value in a Just constructor: return value = Just value.

Bind - The Nester of Monad Producers

The bind operation of a monadic type allows monad producers of that type to be combined in a nested fashion in much the same way that ordinary substrate-to-substrate functions are nested by function composition.

I use the term giver to refer to the nested function, and the term taker to refer to the outer function in such a combination. The giver produces a value that the taker acts on somehow.

Consider such a nesting of monad producers. In the nested combination, the inner monad producer, the giver, produces a monadic value, say, of type monadX input. But the outer monad producer, the taker, would be of type input -> monadX output.

The taker is not directly applicable to the monadic data structure returned by the giver. Instead, the taker is applicable to the individual substrate slots of that data structure. The bind operation of such a monad adapts the taker to work in a natural way on the entire monadic data structure monadX input returned by the giver, and to produce, again, a monadic data structure of type monadX output. Natural here means that the bind causes the correct combination of the aspect-awareness produced by the giver and the aspect-awareness of the taker to propagate aspect-awareness up the monadic call chain.

For example, the monadic bind operation for the list monad takes a list of type [input], a monadic value, and a list-producing function of type input -> [output], a monad producer, as arguments, applies the function to each element of the input list, and concatenates the lists thus produced to create the return list, another monadic value, of type [output].

Reducing the overall output of the entire operation to a monadic value again ensures that the result can be further nested within a higher-level monad producer, and so on, up the nesting chain.

Thus, by using the bind operation for a particular monadic type, we can pipe the output of one monad producer into the input of another. Piping here means propagating the effects produced by a call to a monad producer up a call chain of nested monad producers. Such a call chain may also be called a monadic pipeline. The details of such propagation of effect are coded generically in the bind operation for the given monadic type and hidden away from the application program. Then, at the application level, the code for piping two monad producers together gets to resemble the code for composing two ordinary functions together by regular function application.

Here is how the piping is expressed in Haskell:

  giver input >>= taker

The bind operator (>>=) implicitly associates an output monad produced by the giver with the input substrate parameter of the taker.

So far, we have seen two examples of such a bind operation: The bind operation for the maybe monad propagates nulls in a monadic pipeline; and the bind operation for the list monad propagates multiplicity of output in a monadic pipeline.

Piping, Binding, and Composition

To get a firm handle on the bind operation, let us now consider a few variations of the way the piping of monad producers can be expressed in Haskell.

First, we can make the piping look more symmetric in terms of the giver and the taker by using the monadic return operation to prime the pipeline:

  return input >>= giver >>= taker

The behavioral rules for monads mandate that the return operation act as the left and right unit for monadic binding (a no-op when bound to another monad-producing function).

Another way of expressing this type of piping is through the use of Haskell's flipped bind operation (=<<), which is equivalent to normal bind with its arguments reversed. The flipped bind is defined as:

  (=<<) :: (input -> monad output) -> monad input -> monad output
  monadProducer =<< inputMonad = inputMonad >>= monadProducer

By using the flipped bind, the piping of two monad producers may be expressed as:

  let bindingvalue = giver input
  in taker =<< bindingvalue
Or as:
  taker =<< giver =<< return input

This notation brings to sharp focus the similarity between combining aspect-aware functions by using the monadic bind of the monad for the given aspect, and composing substrate-to-substrate functions by ordinary function application. The latter, of course, is just:

  taker $ giver $ input

One of the many ways in which You Could Have Invented Monads and Maybe You Have excels in explaining monads, is its focus on the flipped bind rather than on the normal bind. When viewed as a curried function of its first argument, the flipped bind can be seen as a function that acts on monad producers to elevate them from substrate-to-monad functions to monad-to-monad functions. I'll call the resulting functions elevated monad producers.

Whereas an ordinary monad producer might enhance a basic substrate-to-substrate function to endow some generic aspect to its output, an elevated monad producer enhances an ordinary monad producer to endow it with a knowledge of the same generic aspect appearing in its input. Of course, elevated monad producers both use and return monadic values, and they can therefore be piped together by ordinary function composition.

Which leads to our final variation of the piping operation:

  let input' = return input
      giver' = (=<<) giver
      taker' = (=<<) taker
  in
      taker' $ giver' $ input'

Figure 3 depicts this last variation for piping monad producers.

Figure-3

Figure 3. Using the Flipped Bind Operation (=<<) to Pipe Monad Producers

Nest-and-Collapse: A Pattern for Monadic Binds

The way in which a monad producer of type input -> monadX output is converted by the flipped bind operation of its monadic type to an elevated monad producer is up to the designer of the monadic type, subject to the behavioral rules for monads. [These rules are listed in most sources on monads and need not be repeated here.]

A common pattern for defining the bind operation is what I call nest-and-collapse.

Recall that the bind operation has to adapt a monad producer of type input -> monadX output, to a data structure of type monadX input, some of whose slots hold values of the substrate input.

In the nest step of the nest-and-collapse pattern, we apply the monad producer in a nested fashion to each designated substrate slot of the input monad. Each substrate slot will then contain a nested monad, and the type of the overall nested structure becomes monadX monadX output. Of course, bind is supposed to produce a flat monad, one of type monadX output. So in the collapse step of the nest-and-collapse pattern, the nested structure is normalized to yield a flat monad.

The nested structure is just a conceptual device, of course. Whether or not it exists as a distinct entity in the code for a bind operation is an implementation detail.

Figure 4 is a schematic depiction of this pattern.

Figure-4

Figure 4. The Nest-and-Collapse Binding Pattern

The bind function for lists is perhaps the clearest example of the nest-and-collapse pattern. The nested application of a list-producing function creates a nested list, whose type is [[output]]. But the bind is supposed to produce a flat list of type [output]. So the nested list is collapsed by merging its constituent lists.

Working with Higher-Order Monad Producers

One way to motivate Haskell's pseudo-assignment syntax (substrate <- monad within a do block) for chaining monad producers is to consider how a bind would have to work when the taker is a monad producing function of two substrate parameters rather than just one.

I'll illustrate the idea by using a somewhat contrived application of the list monad, chosen for pedagogical simplicity. Suppose we are to design two functions: pairsUpTo, and pairsUpTo', that each take a positive integer, max, as a parameter, and return, respectively, the list of all pairs (max, le), and the list of all pairs (le, max), where le is a positive integer less than or equal to max. Thus, pairsUpTo 3 would return the list [(3, 1), (3, 2), (3, 3)], and pairsUpTo' 3 would return [(1, 3), (2, 3), (3, 3)].

We'll first implement pairsUpTo by using the explicit monadic bind (>>=) for the list monad. Next we'll see that the seemingly trivial change in the order of the values in each pair needed by pairsUpTo' requires a considerably less readable formulation in terms of the explicit bind. We'll then use an implicit bind through Haskell's pseudo-assignment operator in the context of a do block to increase the readability of the resulting code.

So consider first the function pairsUpTo. Two actions are required in computing this function: the enumeration of a range of positive integers up to a maximum, and the pairing of that maximum with one of the enumerated integers. Clearly, the enumeration action is a list monad producer: it produces an integer list, a monadic value, based on an integer parameter, max, a substrate value:

  upTo :: Int -> [Int]
  upTo max = [1..max]

For the purpose of this exercise, I'll contrive the second action, the pairing of an integer with the maximum, to be a list monad producer as well:

  pairer :: Int -> Int -> [(Int, Int)]
  pairer first second = [(first, second)]

Now while this latter function does produce a list monad, it is not of the right form for monadic binding, since it has two substrate arguments. But if we apply this function to its first argument, then we get a bindable monad producer. So the binding in this case is slightly different than the examples we have seen so far:

  pairsUpTo :: Int -> [(Int, Int)]
  pairsUpTo max = upTo max >>= pairer max

The taker in this binding is the closure of the pairer function for a particular value of the max parameter. This type of binding involving a higher-order monad producer is illustrated in Figure 5.

Figure-5

Figure 5. Binding to a Closure

In general, whenever the taker in a bind is naturally a function of multiple parameters, all but one of its parameters must be fixed in a closure. The resulting closure is then a first-order monad producer that can accept the monadic output of the giver in a bind.

Now in the implementation of pairsUpTo we were lucky in that our first-order monad producer resulted from the application of our higher-order monad producer to its first parameter.

Consider next the implementation of pairsUpTo', which is to produce a list of type [(le, max)]. Because the fixed elements of our pairs are now the second ones, our simple formulation above for binding to a higher-order monad producer would no longer work. In this case, we would need instead either a named function, or a lambda expression, to designate a function whose second argument is fixed in a closure. The lambda formulation is typically simpler:

  pairsUpTo' :: Int -> [(Int, Int)]
  pairsUpTo' max = upTo max >>= \le -> pairer le max

This pattern of binding is a common occurrence. Let's call it a lambda bind. As a generic pattern, this lambda-bind looks something like:

  monadValue >>= \substrate -> monadProducer substrate constant

where the value constant is fixed in a closure, thus transforming the higher-order monad producer to a first-order monad producer, and where the lambda variable substrate refers to a value of a substrate type.

Now let's view the lambda bind in terms of the nest-and-collapse binding pattern of Figure 4. In this light, the lambda parameter substrate provides a way of referring to a prototypical substrate slot of the monadic value being bound (a blue rectangle of Figure 4). Thus, our binding monad producer is endowed with a mechanism for naming a generic substrate slot value used in the construction of its monadic input. And, of course, such a substrate value is what our monad producer must act on in a nested fashion in the nest step of the nest-and-collapse binding pattern.

This naming mechanism for an input monad's substrate slots in a bind provides a powerful tool for making monadic binding in programs simple and intention-revealing. In particular, it gives the programmer a handle on the intermediate results produced in a nested application of monad-producing functions, through the names of the substrate slots of the resulting intermediate monads.

To summarize, the lambda bind is a special case of bind in which the monad producer is a lambda expression of a single parameter, and that parameter is associated with a prototypical substrate slot of the monadic value being bound. It follows that a lambda-bind can just as well be represented by a notation for associating a monadic value with the lambda variable of a monad producing lambda-expression. And that notation is Haskell's pseudo-assignment, substrate <- monadValue, in the context of a do block.

Here is what the implementation of our pairsUpTo' looks like as a Haskell do block.

  pairsUpTo' max = do
    le <- upTo max
    pairer le max

The do designates a monadic pipeline. The pseudo-assignment operator is a simple rearrangement of the lambda formulation: just take \le ->, flip the arrow around to get \le <-, put the result in front of the entire expression, and lose the lambda. Of course, the pseudo-assignment only associates a monadic value with a substrate variable. The monadic value being pseudo-assigned, and the substrate variable pseudo-assigned to, have different types, and the value is not assignable to the variable in the conventional sense of assignment.

What's Next

We have now seen the basic machinery of monadic programming in terms of some simple pictures and introduced a few pieces of terminology to refer to some of the concepts.

In a subsequent article, I'll use this framework to trace the design of the state monad, a monad for propagating state transformations through a series of nested function calls.

Comments.

Acknowledgments

My thanks to my fellow members of the Silicon Valley Patterns Group for lively discussions on Haskell, and in particular to Sudarsan Piduri for valuable feedback on earlier drafts of this document.