# Why doesn't GHC do the following optimisation?

Simon Peyton-Jones simonpj at microsoft.com
Thu Nov 13 09:14:46 EST 2003

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

I wish it were all more predictable!

Simon

| -----Original Message-----
| andrew cooke
| Sent: 12 November 2003 17:40
| 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