[Haskell-cafe] Implementing the State Monad

oleg at pobox.com oleg at pobox.com
Sun Nov 11 21:56:17 EST 2007

apfelmus showed the implementation of the state monad as free term
algebra, using GADT. Here's an implementation that does not use GADT

All the smarts are in the observation function. This style is _very_
well explained by Ralf Hinze in his Functional Pearl
`Deriving Backtracking Monad Transformers' (ICFP00)

He also showed how to optimize this term algebra (aka, `initial')
implementation using continuations (sec 3.3).

Where this style begins to break down is with complex monads, such as
backtracking *with cut* or some other control. Note that Hinze was not
able to implement his version of backtracking with cut using _free_
term algebra. The situation can be improved however if we use a
special operation to reflect the search (msplit of MonadMinus). We
obtain an efficient implementation then and no longer have to match on
the contexts.

More information about the Haskell-Cafe mailing list