Monads have proved popular in encapsulating state problems in sequential functional programming [115]. The idea is derived from category theory, and allows type-based control of certain kinds of state.
Because monads are generally used to program state, their implementations are usually deliberately single-threaded. This is not necessary, however. If the monad is commutative, then the operations captured within it can be computed in parallel. This has been exploited to produce a parallel type inference algorithm [48], and to formulate a general framework for parallelism [70]. In the latter system, for some monad Par, with operations
unit :: a -> Par a bind :: Par a -> (a -> Par b) -> Par b fork :: Par a -> Par b -> Par (a,b)Par is commutative if the following two definitions of fork are equivalent.
fork1 p q = p `bind` \ x -> q `bind` \ y ->
unit (x,y)
fork2 p q = q `bind` \ y -> p `bind` \ x ->
unit (x,y)
It is simple to reformulate nfib in terms of these
operations
nfib n :: Par Int
nfib n = (nfib (n-1) `fork`
nfib (n-2)) `bind` \ (n1,n2) ->
unit(n1+n2+1)
Unfortunately, the type of nfib now precludes its use in
non-monadic functions without some special trickery.