[Haskell-cafe] Transformation sequence

[Andrew Coppin]

Twan van Laarhoven wrote:
>
> 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)

Ooo... that's a tad neater.

> It would help if you gave some more information on what 'put back into 
> main expression' actually looks like.

It changes for each case. Basically "transform" does a case analysis on 
the form of the expression, and decides how to transform it. In some 
cases, that involves simply calling itself recursively. But that's where 
trying to keep records of the process gets rather tangled.

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

Yeah, this is the approach I took with one of the earlier transforms. 
You start at the top of expressions, look for transformations to apply, 
in necessary recurse down the tree, until eventually a transformation is 
applied. Then you go right back to the top and start again. Repeat until 
no available transforms remain. It basically looks like this:

  go1 :: Expression -> Maybe Expression
  go = unfoldr (\e -> do e' <- go1 e; return (e,e))

Very simple, very neat.

This new transformation I'm trying to implement works in a different 
order. It works from the bottom up, rather than from the top down... if 
that makes sense.