Length is not a good consumer

[ariep@…]

The program

module Main where

main = print $ length . filter odd $ [0 .. 999999999]

, compiled with ghc-6.5.20060508 or later with optimisation turned on (-O), overflows the stack when run. It seems that the generated code is not tail-recursive. 6.4.2 and 6.5 snapshots up to 20060507 do not have this problem.

This may be a silly example, but the same thing happens if you replace 'odd' with some more interesting predicate, and let the length of the input list be chosen by the user.

[simonmar]

Thanks for narrowing this down to a particular day! I'd be willing to bet money that this is the culprit:

 http://www.haskell.org/pipermail/cvs-libraries/2006-May/004996.html

[igloo]

I've confirmed that the patch Simon M indicates is indeed the problem, and I've copied it below for reference.

It makes sense to me that the above behaviour is seen: length is now a good consumer, but it generates 1+(1+(1+(1+... as it is consuming, and this causes a stack overflow. I don't think we can fix this while staying with fold/build fusion, so it looks to me like the patch should be reverted and the whole problem looked at post-6.6.

Do you agree, Simon PJ?

Thanks Ian

[Make length a good consumer
simonpj@microsoft**20060508142726

 Make length into a good consumer.  Fixes Trac bug #707.

 (Before length simply didn't use foldr.)

] {
hunk ./GHC/List.lhs 114
-length                  :: [a] -> Int
-length l                =  len l 0#
-  where
-    len :: [a] -> Int# -> Int
-    len []     a# = I# a#
-    len (_:xs) a# = len xs (a# +# 1#)
+length :: [a] -> Int
+length l = lenAcc 0# l
+
+{-# RULES
+"length" [~1] forall xs. length xs = foldr incL (I# 0#) xs
+"lenAcc" [1]  forall n#. foldr incL (I# n#) = lenAcc n#
+ #-}
+
+incL :: a -> Int -> Int        -- Internal
+{-# NOINLINE [0] incL #-}
+incL x n = n `plusInt` oneInt
+
+lenAcc :: Int# -> [a] -> Int   -- Internal
+lenAcc a# []     = I# a#
+lenAcc a# (_:xs) = lenAcc (a# +# 1#) xs
}

[simonmar]

I rolled back the patch for 6.6 - linear stack space is more important than the constant factor speedup from fusion. Let's look at this again for 6.6.1.

[simonpj]

Changing title to reflect current bug

[simonpj]

This will probably get fixed as a result of revising list fusion: task #915

[guest]

probably this ticket should be joined to the #915?