Monad

From HaskellWiki

Revision as of 20:40, 30 January 2010

Monads in Haskell are structures used to supplement pure computations with features like state, common environment or I/O. Even though Haskell is a purely-functional language, side effects can be conveniently simulated using monads.

Because they are very useful in practice but rather mind-twisting for the beginners, numerous tutorials that deal exclusively with monads were created (see monad tutorials).

1 Common monads

Most common applications of monads include:

• Representing failure using
  Maybe
  monad
• Nondeterminism through backtracking using
  List
  monad
• State using
  State
  monad
• Read-only environment using
  Reader
  monad
• I/O using
  IO
  monad

2 Monad class

class Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  return :: a -> m a
  fail :: String -> m a

In addition to implementing the class functions, all instances of Monad should obey the following equations:

return a >>= k  =  k a
m >>= return  =  m
m >>= (\x -> k x >>= h)  =  (m >>= k) >>= h

See this intuitive explanation of why they should obey the Monad laws.

Any Monad can be made a Functor by defining

fmap ab ma = ma >>= (return . ab)

However, the Functor class is not a superclass of the Monad class. See Functor hierarchy proposal.

3 Special notation

thing1 >>= (\x -> func1 x >>= (\y -> thing2 >>= (\_ -> func2 y (\z -> return z))))

which can be written more clearly by breaking it into several lines and omitting parentheses:

thing1 >>= \x ->
func1 x >>= \y ->
thing2 >>= \_ ->
func2 y >>= \z ->
return z

do
  x <- thing1
  y <- func1 x
  thing2
  z <- func2 y
  return z

4 Commutative monads

Commutative monads are monads for which the order of actions makes no difference (they commute), that is when following code:

do
  a <- f x
  b <- g y
  m a b

is the same as:

do
  b <- g y
  a <- f x
  m a b

Examples of commutative include:

• Reader
  monad
• Maybe
  monad

5 Monad tutorials

Monads are known for being deeply confusing to lots of people, so there are plenty of tutorials specifically related to monads. Each takes a different approach to Monads, and hopefully everyone will find something useful.

See Monad tutorials.

6 Monad reference guides

An explanation of the basic Monad functions, with examples, can be found in the reference guide A tour of the Haskell Monad functions, by Henk-Jan van Tuyl.

7 Monad research

A collection of research papers about monads.

8 Monads in other languages

Implementations of monads in other languages.

• C
• C++, doc
• CML.event ?
• Clean State monad
• Clojure
• JavaScript
• Java (tar.gz)
• Joy
• LINQ, more, C#, VB
• Lisp
• Miranda
• OCaml:
  • OCaml
  • more
  • also
  • MetaOcaml
  • A Monad Tutorial for Ocaml
• Perl
• Perl6 ?
• Prolog
• Python
  • Python
  • here
  • Twisted's Deferred monad
• Ruby:
  • Ruby
  • other implementation
• Scala:
  • Scala
  • A continuation monad
• Scheme:
  • Scheme
  • also
• Tcl
• The Unix Shell
• More monads by Oleg
• CLL: a concurrent language based on a first-order intuitionistic linear logic where all right synchronous connectives are restricted to a monad.

Unfinished:

• Slate
• Parsing, Maybe and Error in Tcl

And possibly there exist:

• Standard ML (via modules?)

Please add them if you know of other implementations.

Collection of links to monad implementations in various languages. on Lambda The Ultimate.

9 Interesting monads

A list of monads for various evaluation strategies and games:

• Identity monad
• Optional results
• Random values
• Read only state
• Writable state
• Unique supply
• ST - memory-only effects
• Global state
• Undoable state effects
• Function application
• Functions which may error
• Atomic memory transactions
• Continuations
• IO - unrestricted side effects
• Non-deterministic evaluation
• List monad: computations with multiple choices
• Concurrent threads
• Backtracking computations
• Region allocation effects
• LogicT: backtracking monad transformer with fair operations and pruning
• Pi calculus as a monad
• Halfs, uses a read-only and write-only monad for filesystem work.
• House's H monad for safe hardware access
• Commutable monads for parallel programming
• The Quantum computing monad
• Simple, Fair and Terminating Backtracking Monad
• Typed exceptions with call traces as a monad
• Breadth first list monad
• Continuation-based queues as monads
• Typed network protocol monad
• Non-Determinism Monad for Level-Wise Search
• Transactional state monad
• A constraint programming monad
• A probability distribution monad

There are many more interesting instance of the monad abstraction out there. Please add them as you come across each species.

10 Fun

• If you are tired of monads, you can easily get rid of them.

Categories: Standard classes | Monad