monad

theory, functional programming /mo'nad/ A technique from

category theory which has been adopted as a way of dealing

with state in functional programming languages in such a

way that the details of the state are hidden or abstracted out

of code that merely passes it on unchanged.

A monad has three components: a means of augmenting an

existing type, a means of creating a default value of this new

type from a value of the original type, and a replacement for

the basic application operator for the old type that works

with the new type.

The alternative to passing state via a monad is to add an

extra argument and return value to many functions which have

no interest in that state. Monads can encapsulate state, side

effects, exception handling, global data, etc. in a purely

lazily functional way.

A monad can be expressed as the triple, (M, unitM, bindM)

where M is a function on types and (using Haskell notaion):

unitM :: a -@# M a

bindM :: M a -@# (a -@# M b) -@# M b

I.e. unitM converts an ordinary value of type a in to monadic

form and bindM applies a function to a monadic value after

de-monadising it. E.g. a state transformer monad:

type S a = State -@# (a, State)

unitS a = s0 -@# (a, s0)

m `bindS` k = s0 -@# let (a,s1) = m s0

in k a s1

Here unitS adds some initial state to an ordinary value and

bindS applies function k to a value m. (`fun` is Haskell

notation for using a function as an infix operator). Both m

and k take a state as input and return a new state as part of

their output. The construction

m `bindS` k

composes these two state transformers into one while also

passing the value of m to k.

Monads are a powerful tool in functional programming. If a

program is written using a monad to pass around a variable

(like the state in the example above) then it is easy to

change what is passed around simply by changing the monad.

Only the parts of the program which deal directly with the

quantity concerned need be altered, parts which merely pass it

on unchanged will stay the same.

In functional programming, unitM is often called initM or

returnM and bindM is called thenM. A third function, mapM is

frequently defined in terms of then and return. This applies

a given function to a list of monadic values, threading some

variable (e.g. state) through the applications:

mapM :: (a -@# M b) -@# [a] -@# M [b]

mapM f [] = returnM []

mapM f (x:xs) = f x `thenM` ( x2 -@#

mapM f xs `thenM` ( xs2 -@#

returnM (x2 : xs2) ))

(2000-03-09)