[Haskell-cafe] Transformation sequence

[Twan van Laarhoven]

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)

How about:

    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