[Haskell-cafe] Optimizing common subexpressions [Was: ghc has problems with 'zipWith' ?]

[Henning Thielemann]

On Wed, 8 Dec 2004, Derek Elkins wrote:

> > Is it possible and senseful for a compiler to extract common
> > sub-expressions? Naively I think that for a given tree of an
> > expression it is efficiently possible to find all common sub-trees.
> > Referential transparency would assure that equal expressions have the
> > same value, so they can be replaced by the same object. E.g.  the
> > example above could be automatically transformed to: 
> > 
> > ms as =
> >    let tmp0 = zipWith (+) (zipWith (*) as tmp1) (0:tmp1)
> >        tmp1 = 1:tmp0
> >    in  tmp0
> 
> It's possible and will preserve semantics, but isn't always an
> optimization.
> 
> http://www.haskell.org/pipermail/haskell-cafe/2003-December/005574.html

I see the problem but I doubt that it is solved satisfyingly by letting
the user choose whether he prefers storage or re-computing of data
structures. What about the function

double x = x++x

? Here 'x' may be a list that is better re-computed instead of being
stored completely. But the replacement of common sub-expression is already
performed by the one who calls 'double'. Though, GHC seems to have no
problems particularly with this function.