Monads have proved popular in encapsulating state problems in sequential functional programming . 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 , and to formulate a general framework for parallelism . 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.