Make genericLength tail-recursive so it doesn't overflow stack
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]
Trac metadata
Trac field | Value |
---|---|
Version | 6.10.1 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | Compiler |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | |
Architecture |