#3076: Make genericLength tail-recursive so it doesn't overflow stack
-------------------------------------+--------------------------------------
Reporter: Syzygies | Owner:
Type: run-time performance bug | Status: new
Priority: normal | Component: Compiler
Version: 6.10.1 | Severity: normal
Keywords: | Testcase:
Os: Unknown/Multiple | Architecture: Unknown/Multiple
-------------------------------------+--------------------------------------
A likely use for genericLength is to count lists of more than Int
elements. However, the source code is not tail-recursive, making a poor
"consumer", so genericLength easily overflows stack.
Here is the source code from 6.10.1:
{{{
genericLength :: (Num i) => [b] -> i
genericLength [] = 0
genericLength (_:l) = 1 + genericLength l
}}}
Here is a proposed alternative:
{{{
genericLength ∷ (Num i) ⇒ [b] → i
genericLength = len 0 where
len n [] = n
len n (_:xt) = len (n+1) xt
}}}
In my test application (enumerating the 66,960,965,307 atomic lattices on
six atoms) this alternative avoids overflowing the stack.
[This is not the same issue as
http://hackage.haskell.org/trac/ghc/ticket/2962]
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3076>
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
