[Haskell-cafe] Transformation sequence
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...) =
> 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
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
More information about the Haskell-Cafe