Why doesn't GHC do the following optimisation?
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
* you've defined foldl' using foldr, and that has the potential to do
with the [1..n]
* but you've exported sum2, so the inlining doesn't happen. If you keep
module Main( main ) ...
you'll see quite different code
* there's an awkwardness with eta-expanding foldl, which I have never
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!
| -----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?
| 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,
| even for the result of a single calculation to be printed twice.
| 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
| you can express foldl in terms of foldr and giving the derivation.
| Unfortunately I don't have the paper/derivation, but I believe my
| is correct (that may be the problem, of course - that sum1 and sum2
| not equivalent either because of a coding error, or because of some
| subtlety in the types, although I carefully gave them explicit types
| 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
| ghc do the same kind of transformation itself? Or am mistaken in
| thinking that if derivation is easy then the revrese transformation as
| optimisation should also be easy?
| Haskell-Cafe mailing list
| Haskell-Cafe at haskell.org
More information about the Haskell-Cafe