Andrew Coppin andrewcoppin at btinternet.com
Sat Oct 20 14:54:16 EDT 2007

```Twan van Laarhoven wrote:
>
>
>    transform ... =
>          (transform sub1 >>= put back into main expression)
>       ++ (transform sub2 >>= put back into main expression)
>
> Or something to that effect? Or maybe
>
>    transform ... = do
>       sub' <- transform sub1 ++ transform sub2
>       put back into main expression)

> It would help if you gave some more information on what 'put back into
> main expression' actually looks like.

It changes for each case. Basically "transform" does a case analysis on
the form of the expression, and decides how to transform it. In some
cases, that involves simply calling itself recursively. But that's where
trying to keep records of the process gets rather tangled.

> A trick I often find useful when working with transformations is to
> have a function
>
>    step :: Expression -> Maybe Expression
>
> that applies a single transformation step, and returns Nothing if no
> further transformations are possible. You then use the maybe monad,
> and run steps with:
>
>    runSteps :: (a -> Maybe a) -> a -> a
>
> Alternatively, the intermediate results could be remebered, then the
> function would return a list instead.
>
> For combining alternatives you can define
>
>    orElse :: (a -> Maybe a) -> (a -> Maybe a) -> (a -> Maybe a)
>
> Again, I am not sure if any of this applies to your problem, but it
> might help.

Yeah, this is the approach I took with one of the earlier transforms.
You start at the top of expressions, look for transformations to apply,
in necessary recurse down the tree, until eventually a transformation is
applied. Then you go right back to the top and start again. Repeat until
no available transforms remain. It basically looks like this:

go1 :: Expression -> Maybe Expression
go = unfoldr (\e -> do e' <- go1 e; return (e,e))

Very simple, very neat.

This new transformation I'm trying to implement works in a different
order. It works from the bottom up, rather than from the top down... if
that makes sense.

```