This is an exploration of two different ways of keeping track of state in Haskell. One uses the State monad, the other doesn't

context.hs

import Control.Monad.Trans.State

data Expression = Var Char
                | Const Int
                | Expression :+: Expression
                | Int :*: Expression
                deriving (Eq, Ord, Show)

type Context = State (Maybe Expression)

-- |Wrapper for the put function.
-- |Takes an Expression and puts it wrapped in a Maybe
write :: Expression -> Context ()
write e = put $ Just e

-- |Puts Nothing
reset :: Context ()
reset = put Nothing

-- |Checks if he new context is equal to the old one
-- |if it is, the new context is returned
-- |if it isn't, evaluate next
(#) :: Expression -> Context Expression -> Context Expression
(#) new next = do
  old <- get
  if old == Just new
  then return new
  else next

-- |Recursively evaluates an expression, saving its previous state in the Context
-- |This context saving is done to prevent potential infinite loops
eval :: Expression -> Context Expression
eval (a :*: Const b) = return . Const $ a * b
eval new@(a :*: (e :+: f)) = new # do
    e' <- eval e
    f' <- eval f
    write new
    eval $ (a :*: e') :+: (a :*: f')
eval new@(a :*: e) = new # do
    e' <- eval e
    write new
    eval $ a :*: e'
eval new@(a :+: b) = new # do
    a' <- eval a
    b' <- eval b
    write new
    eval $ a' :+: b'
eval expr = return $ expr

-- |Similar to the above, except it doesn't carry its context as a State,
-- |but rather just as a Maybe monad.
-- |the first case checks if the new context is equal to the old one, and prevents infinite loops
eval' :: Maybe Expression -> Expression -> Expression
eval' (Just old) new | old == new = new
eval' _ (a :*: Const b) = Const $ a * b

eval' _ new@(a :*: (e :+: f)) = eval'' $ (a :*: e') :+: (a :*: f')
  where eval'' = eval' (Just new)
        e'     = eval'' e
        f'     = eval'' f
eval' _ new@(a :*: e) = eval'' $ a :*: e'
  where eval'' = eval' (Just new)
        e'     = eval'' e
eval' _ new@(a :+: b) = eval'' $ a' :+: b'
  where eval'' = eval' (Just new)
        a'     = eval'' a
        b'     = eval'' b
eval' _ expr = expr