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