Opened 10 years ago

Closed 8 years ago

Last modified 6 years ago

#4219 closed bug (wontfix)

sequence is not tail recursive, doesn't work with large inputs in strict monads

Reported by: EyalLotem Owned by:
Priority: normal Milestone: 7.2.1
Component: Compiler Version: 6.12.3
Keywords: sequence tail recursive Cc:…, cheecheeo@…
Operating System: Unknown/Multiple Architecture: x86
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:


replicateM 10000000 (randomIO >>= evaluate)

blows the stack because of "sequence".

I think it is important for Haskell programmers to be able to compose existing components without having to worry about the operational semantics of laziness, so it is important for GHC to specialize "sequence" calls to a tail-recursive one when a strict monad is in use.

Attached is the test case.

Attachments (1)

TestRandomIO.hs (147 bytes) - added by EyalLotem 10 years ago.

Download all attachments as: .zip

Change History (9)

Changed 10 years ago by EyalLotem

Attachment: TestRandomIO.hs added

comment:1 Changed 9 years ago by igloo

Milestone: 6.14.1

comment:2 Changed 9 years ago by

Cc:… added

comment:3 Changed 9 years ago by igloo


comment:4 Changed 9 years ago by cheecheeo

Cc: cheecheeo@… added

comment:5 Changed 9 years ago 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) }
    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.

comment:6 Changed 9 years ago by igloo


comment:7 Changed 8 years ago by igloo

Resolution: wontfix
Status: newclosed

We don't have a general way to optimise this, so closing.

comment:8 Changed 6 years ago by nh2

difficulty: Unknown

Another way to treat this is to make the stack size unbounded by default.

As far as understand, this is now more feasible than it was when this bug was opened.

This way, the user would not have problems with the operational semantics as originally asked for.

(By the way, while in this bug the problem is seen as something hard to optimize, you could also understand using the stack for lists as an optimization that breaks things.)

I opened to discuss the issue.

Note: See TracTickets for help on using tickets.