Twan van Laarhoven twanvl at gmail.com
Sat Oct 20 14:28:58 EDT 2007

```Andrew Coppin wrote:
> I'm writing some code where I take an expression tree and transform it
> into another equivilent one.
>
> Now it's moderately easy to write the code that does the transformation.
> But what I *really* want is to print out the transformation *sequence*.
> This appears to be much more awkward.
>
> What I have is a function like this:
>
>  transform :: Expression -> [Expression]
>
> The trouble is, if you want to apply the transformation recursively,
> things get very messy. Oh, it *works* and everything. It's just really
> messy and verbose. In Haskell, this is usually a sign that you want to
> start applying some ingenious trickery... but I'm having an ingeniety
> failure here.
>
> Suppose, for example, that in one case you want to recursively transform
> two subexpressions. I end up writing something like
>
>  transform (...sub1...sub2...) =
>    let
>      sub1s = transform sub1
>      sub2s = transform sub2
>    in map (\sub1' -> put sub1' back into main expression) sub1s ++ map
> (\sub2' -> put sub2' back into main expression) sub2s
>
> After you've typed that a few times, it becomes *very* boring! But I
> can't think of a clean way to abstract it. :-(
>
> It's *almost* like you want to use the list monad:
>
>  transform (...sub1...sub2...) = do
>    sub1' <- transform sub1
>    sub2' <- transform sub2
>    return (put sub1' and sub2' back into the main expression)

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.

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.

Twan
```