#4219: sequence is not tail recursive, doesn't work with large inputs in strict
monads
----------------------------------------+-----------------------------------
Reporter: EyalLotem | Owner:
Type: bug | Status: new
Priority: normal | Milestone: 7.0.2
Component: Compiler | Version: 6.12.3
Keywords: sequence tail recursive | Testcase:
Blockedby: | Difficulty:
Os: Unknown/Multiple | Blocking:
Architecture: x86 | Failure: None/Unknown
----------------------------------------+-----------------------------------
Comment(by simonpj):
What do you expect to happen here? You are asking GHC to build a big
list. (Yes, it is then discarded, but the loop that produces the list
doesn't know that.) How can we produce a big list? Something like this:
{{{
loop :: Int -> IO [Int]
loop 0 = return []
loop n = do { r <- randomIO; rs <- loop (n-1); return (r:rs) }
}}}
But that is obviously not tail recursive. Maybe you want this?
{{{
loop :: Int -> IO [Int]
loop n = do { rs <- tr_loop n []; return (reverse rs) }
where
tr_loop 0 rs = rs
tr_loop n rs = do { r <- randomIO; tr_loop (n-1) (r:rs)
}}}
Doing that automatically would be hard, esp as you'd want to be sure that
cost of the extra reverse was justified. Oh... the numbers are random so
you don't need to reverse it. But do you expect the compiler to know
that?
In short, I'm dubious that there's a simple, general optimsation that we
are missing. I'd love to know one -- please show me.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4219#comment:5>
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
