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@haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of | andrew cooke | Sent: 12 November 2003 17:40 | To: haskell-cafe@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@haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe