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.