#2754: Strictness analyzer fails on an implementation of foldl
--------------------------------------+-------------------------------------
Reporter: nimnul | Owner:
Type: run-time performance bug | Status: new
Priority: normal | Milestone:
Component: Compiler | Version: 6.8.3
Severity: normal | Resolution:
Keywords: | Difficulty: Unknown
Testcase: | Architecture: x86
Os: Windows |
--------------------------------------+-------------------------------------
Changes (by simonmar):
* difficulty: => Unknown
Old description:
> foldB has O(1) complexity, but foldA O(N). Looks like a strictness
> analyzer failure.
>
> module Main where
>
> foldA :: (a -> e -> a) -> a -> [e] -> a
> foldA _ r [] = r
> foldA op r (x:xs) = foldA op (op r x) xs
>
> foldB :: (a -> e -> a) -> a -> [e] -> a
> foldB _ r [] = r
> foldB op r (x:xs) = r' `seq` foldB op r' xs where r' = op r x
>
> l :: [Int]
> l = [1..100*1000*1000]
>
> main = print $ foldl (+) 0 l
New description:
foldB has O(1) complexity, but foldA O(N). Looks like a strictness
analyzer failure.
{{{
module Main where
foldA :: (a -> e -> a) -> a -> [e] -> a
foldA _ r [] = r
foldA op r (x:xs) = foldA op (op r x) xs
foldB :: (a -> e -> a) -> a -> [e] -> a
foldB _ r [] = r
foldB op r (x:xs) = r' `seq` foldB op r' xs where r' = op r x
l :: [Int]
l = [1..100*1000*1000]
main = print $ foldl (+) 0 l
}}}
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/2754#comment:1>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
