#3076: Make genericLength tail-recursive so it doesn't overflow stack
-----------------------------------------+----------------------------------
Reporter: Syzygies | Owner:
Type: run-time performance bug | Status: closed
Priority: normal | Milestone:
Component: Compiler | Version: 6.10.1
Severity: normal | Resolution: invalid
Keywords: | Difficulty: Unknown
Testcase: | Os: Unknown/Multiple
Architecture: Unknown/Multiple |
-----------------------------------------+----------------------------------
Changes (by igloo):
* status: new => closed
* difficulty: => Unknown
* resolution: => invalid
Comment:
That isn't an equivalent definition, e.g.:
{{{
data Nat = Zero | Succ Nat
deriving (Show, Eq)
works :: Bool
works = genericLength1 (cycle "foo") > (5 :: Nat)
fails :: Bool
fails = genericLength2 (cycle "foo") > (5 :: Nat)
instance Num Nat where
fromInteger 0 = Zero
fromInteger (n + 1) = Succ (fromInteger n)
Zero + n = n
Succ m + n = Succ (m + n)
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
}}}
`works` works, but `fails` doesn't terminate:
{{{
*Main> works
True
*Main> fails
^CInterrupted.
}}}
If you restrict the type to `Int` or `Integer`, then it will work thanks
to #2962, though.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3076#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
