monad

/mo'nad/ [category theory] A 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)         ))