Why doesn't GHC do the following optimisation?

[Simon Peyton-Jones]

It's a while since I paid serious attention to making sure that GHC's
transformations are all working right.  Things are usually more
complicated than one might hope.

In this case, 
* foldl is defined in the prelude using explicit recursion, as it
happens

* you've defined foldl' using foldr, and that has the potential to do
list fusion
	with the [1..n]

* but you've exported sum2, so the inlining doesn't happen.  If you keep
sum2 private
	module Main( main ) ...
   you'll see quite different code

* there's an awkwardness with eta-expanding foldl, which I have never
fully
	dealt with -- needs a kind of analysis.  It's described in 3.2.3
of Gill's thesis
	(see also 4.4).  http://www.cse.ogi.edu/~andy/

I wish it were all more predictable!

Simon

| -----Original Message-----
| From: haskell-cafe-bounces at haskell.org
[mailto:haskell-cafe-bounces at haskell.org] On Behalf Of
| andrew cooke
| Sent: 12 November 2003 17:40
| To: haskell-cafe at haskell.org
| Subject: Why doesn't GHC do the following optimisation?
| 
| 
| Hi,
| 
| This question is purely out of curiousity - I'm no expert on this.  I
| wrote the following code:
| 
| sum1 :: [Int] -> Int
| sum1 = foldl (+) 0
| 
| foldl' :: (a -> b -> a) -> a -> [b] -> a
| foldl' f v l = foldr (\x -> \fld -> \v' -> fld $ f v' x) id l v
| 
| sum2 :: [Int] -> Int
| sum2 = foldl' (+) 0
| 
| main :: IO ()
| main = do n <- readLn;
|           print $ sum1 [1..n];
|           print $ sum2 [1..n]
| 
| and ran it through ghc with: ghc Folds.hs -ddump-simpl -O
| 
| I was expecting the two calls to be optimized to something equivalent,
or
| even for the result of a single calculation to be printed twice.
However,
| peering at the Core output, it seems that the two sum functions exist
| separately and have different structure (sum1 appears to have a simple
| recursive definition, while sum2 involves two lamba expressions).
| 
| I did all this because I read a paper introducing folds that showed
how
| you can express foldl in terms of foldr and giving the derivation.
| Unfortunately I don't have the paper/derivation, but I believe my
foldl'
| is correct (that may be the problem, of course - that sum1 and sum2
are
| not equivalent either because of a coding error, or because of some
| subtlety in the types, although I carefully gave them explicit types
to
| try and avoid that).
| 
| The derivation wasn't that complicated (althugh I find it simpler to
| simply write the fold down).  If it's not an error on my part, why
doesn't
| ghc do the same kind of transformation itself?  Or am  mistaken in
| thinking that if derivation is easy then the revrese transformation as
an
| optimisation should also be easy?
| 
| Thanks,
| Andrew
| 
| --
| http://www.acooke.org/andrew
| _______________________________________________
| Haskell-Cafe mailing list
| Haskell-Cafe at haskell.org
| http://www.haskell.org/mailman/listinfo/haskell-cafe