#2108: ghci is not tail recursive
--------------------------------+-------------------------------------------
Reporter: george.colpitts | Owner:
Type: bug | Status: closed
Priority: normal | Milestone:
Component: GHCi | Version: 6.8.2
Severity: normal | Resolution: invalid
Keywords: | Testcase:
Architecture: powerpc | Os: MacOS X
--------------------------------+-------------------------------------------
Changes (by JeremyShaw):
* status: new => closed
* resolution: => invalid
Comment:
The stack overflow is not due to lack of tail recursion, but rather
laziness. Since the result (prev + curr) is never needed until you try to
print the result, it is not evaluated until then. So you get a bunch of
unevaluated (prev + curr) thunks building up until the stack overflows.
This version uses $! to force (prev + curr) to be evaluated, fixing the
space leak.
{{{
fib :: Int -> Int -> Int -> Int
fib n prev curr =
if n == 0
then curr
else fib (n -1) curr $! (prev + curr)
}}}
Also note that if you probably want Integer instead of Int for your types.
Integer is unbounded.
I am marking this invalid. People have been running into this since before
Haskell existed (often while implementing fib). If it hasn't been consider
a bug so far, it probably won't ever be ;) (for the same reason that non-
tail recursive functions blowing the stack is not considered a bug).
See this page for additional details:
http://www.haskell.org/haskellwiki/Stack_overflow
If you have more questions about this stack overflow (or anything else),
consider asking on the haskell-cafe mailing list or the #haskell irc
channel on irc.freenode.net.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/2108#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
