#3076: Make genericLength tail-recursive so it doesn't overflow stack
-----------------------------------------+----------------------------------
Reporter: Syzygies | Owner:
Type: run-time performance bug | Status: reopened
Priority: normal | Milestone:
Component: Compiler | Version: 6.10.1
Severity: normal | Resolution:
Keywords: genericLength | Difficulty: Unknown
Testcase: | Os: Unknown/Multiple
Architecture: Unknown/Multiple |
-----------------------------------------+----------------------------------
Changes (by Syzygies):
* keywords: => genericLength
* status: closed => reopened
* resolution: invalid =>
Comment:
That was enlightening. Thanks.
The library genericLength blows stack on very short lists. My first
proposal fails on infinite lists, using Peano arithmetic. So they both
fail reasonable tests. However, one can make a logarithmic improvement in
the stack usage of the library function, and pass both tests:
{{{
module Main where
import Data.Int
data Nat = Zero | Succ Nat
deriving (Show, Eq)
instance Num Nat where
fromInteger 0 = Zero
fromInteger n = Succ $ fromInteger $ n - 1
Zero + n = n
Succ m + n = Succ (m + n)
Zero * _ = Zero
Succ m * n = n + m * n
abs n = n
signum Zero = Zero
signum (Succ _) = Succ Zero
instance Ord Nat where
compare Zero Zero = EQ
compare Zero _ = LT
compare _ Zero = GT
compare (Succ m) (Succ n) = compare m n
genericLength1 ∷ (Num i) ⇒ [b] → i
genericLength1 [] = 0
genericLength1 (_:l) = 1 + genericLength1 l
genericLength2 ∷ (Num i) ⇒ [b] → i
genericLength2 = len 0 where
len n [] = n
len n (_:xt) = len (n+1) xt
genericLength3 ∷ (Num i) ⇒ [b] → i
genericLength3 = len 1 0 where
len _ n [] = n
len m n (_:xt)
| m == n = n + len (n+n) 1 xt
| otherwise = len m (n+1) xt
intLength1, intLength2, intLength3 ∷ [a] → Int64
intLength1 = genericLength1
intLength2 = genericLength2
intLength3 = genericLength3
natLength1, natLength2, natLength3 ∷ [a] → Nat
natLength1 = genericLength1
natLength2 = genericLength2
natLength3 = genericLength3
list :: Int64 -> [Bool]
list 0 = []
list n = True : list (n-1)
main ∷ IO ()
main = do
-- print $ intLength1 $ list $ 2^19 -- fails w/ 8388608 byte stack
print $ intLength2 $ list $ 2^32
print $ intLength3 $ list $ 2^32
print $ natLength1 (repeat 1) > 5
-- print $ natLength2 (repeat 1) > 5 -- fails
print $ natLength3 (repeat 1) > 5
}}}
Getting this to work requires specializing genericLength, to avoid class
overhead. This is nevertheless preferable to writing a length function
from scratch, which might fall into either of these traps.
Getting this to work also requires a "good producer". I was surprised to
discover that in this context, [1..n] isn't a "good producer".
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3076#comment:2>
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
