[Haskell-beginners] one more step backwards

[Felipe Lessa]

On Mon, Feb 01, 2010 at 10:32:00PM +0000, John Moore wrote:
> Hi Felipe,
>               this is way complicated for my level, could you look at this
> below and see if I could use this instead.

I understand you, it also took me some time to understand the
monad transformer library :).

> evalStep :: Expression ->  Expression
> evalStep (Val x)=  (Val x)
> evalStep (Add x y)
>   = case x of
>       (Val a) -> case y of
>                    (Val b) -> Val (a+b)
>                    left -> Add x (evalStep y)
>       right -> Add (evalStep x)y

Even without the Writer monad you capture that pattern in an
auxiliary function.  You just extract the common bits and
abstract the specific ones:

  aux calcOp mkOp x y
     = case x of
         (Val a) -> case y of
                      (Val b) -> Val (a `calcOp` b)
                      left -> mkOp x (evalStep y)
         right -> mkOp (evalStep x) y

Note that:
 - I've changed (+) into calcOp and Add into mkOp.
 - Instead of deconstructing with a pattern match, I receive x
   and y as proper arguments.

The type is

  type CalcOp = Integer    -> Integer    -> Integer
  type MkOp   = Expression -> Expression -> Expression
  aux :: CalcOp -> MkOp -> Expression -> Expression
      -> (Expression -> Expression)

You can write your evalStep as

  evalStep :: Expression -> Expression
  evalStep (Val x)        = Val x
  evalStep (Add x y)      = aux (+) Add x y
  evalStep (Subtract x y) = aux (-) Subtract x y
  evalStep (Multiply x y) = aux (*) Multiply x y
  evalStep (Divide x y)   = aux div Divide x y

Much cleaner ;).

>   What I mean to do is build up a history on a list and then take it of a
> list( Same principle as a stack but a little more simple) the problem is how
> do I get the other elements back of the list as in the line "r" -> evaluate
> (I'm not sure what I put here) Hopes this makes some sort of sense.

It does makes sense.  In most languages this is the sort of code
you would write: when the user tell us to evaluate, we evaluate
and then save the result.  However in our language we can
leverage the laziness:

  buildHistory :: Expression -> [Expression]
  buildHistory expr = expr : buildHistory (evalStep)

You may recognize this function as

  buildHistory = iterate evalStep

(Note that unless your expression is infinite, then this list
will contain an infinite number of duplicates when we reach the
fixed point of the evalStep function.)

The idea is to take everything you can out of IO.  With
buildHistory we take the logic of evaluating the expressions
further out of IO.  Now your function is as trivial as mine.  In
fact, it is the same.

HTH,

--
Felipe.