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)

fork1 p q = p `bind` \ x -> q `bind` \ y -> unit (x,y)

It is simple to reformulatefork2 p q = q `bind` \ y -> p `bind` \ x -> unit (x,y)

Unfortunately, the type ofnfib n :: Par Int nfib n = (nfib (n-1) `fork` nfib (n-2)) `bind` \ (n1,n2) -> unit(n1+n2+1)

Thu Jan 4 21:31:10 GMT 1996