apfelmus showed the implementation of the state monad as free term
algebra, using GADT. Here's an implementation that does not use GADT
http://okmij.org/ftp/Haskell/types.html#state-algebra
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)
http://citeseer.ist.psu.edu/hinze00deriving.html
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.
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
