[Haskell-cafe] Transformation sequence

Andrew Coppin andrewcoppin at btinternet.com
Sat Oct 20 13:54:56 EDT 2007

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...) =
      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)

Except that that doesn't quite work properly. As shown above, I actually 
want to go through all the transformation steps for the first branch, 
and *then* all the steps for the second branch.

Any hints?

More information about the Haskell-Cafe mailing list