© Copyright 2007 Bolour Computing.
Azad Bolour
Bolour Computing
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.
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.
Depending on context, the word monad actually has four different connotations, designating four different levels of abstraction.
class Monad
, provides the abstract
interface for monadic operations.
monadX
and monadY
are monadic types.
monadX square
and monadY
rectangle
are monadic types of fixed substrates,
square
, and rectangle
, respectively.
[1, 2]
. In Figure 1, each grid (together
with its contents) represents a monadic value.
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.
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.
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
.
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.
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.
(=<<)
to Pipe Monad Producers
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.
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.
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.
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.
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.
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.