Re: [Haskell-cafe] STM, newArray, and a stack overflow?

23 Mar 2011

      On 23 March 2011 18:42, Bas van Dijk  wrote:
...
On 23 March 2011 17:19, Jake McArthur  wrote:
...
On 03/23/2011 10:34 AM, Ketil Malde wrote:
...
It works (calling the same function) from GHCi, but breaks when
compiled.  Also when compiling with -O0.
Confirmed for GHC 7.0.2. Works fine in GHCi, but compiling it (in my case,
with -O) and running the executable causes a stack overflow unless I run it
with +RTS -K16m, and even then it spends 90% of its time in GC. This looks
like it is probably a bug, to me. Maybe it should be reported in GHC's Trac?
It looks like a bug indeed.
The problem can be reduced to just:
atomically $ replicateM 1000000 (newTVar undefined)
or even simpler:
replicateM 1000000 (newIORef undefined)
Bas
Maybe it's not really a bug:

For example the following very similar program also overflows the
stack: (note that: replicateM n x = sequence (replicate n x))

main = sequence $ replicate 1000000 $ (randomIO :: IO Int)

This happens because sequence is defined using a right fold:

sequence ms = foldr k (return []) ms
    where
      k m m' = do
        x <- m
        xs <- m'
        return (x:xs)

What happens is that sequence repeatedly pushes an x onto the stack
then continues with m' until your stack overflows.

The stack overflow disappears when you use a left fold:

sequencel xs = foldl k (\r -> return $ r []) xs id
    where
      k g m = \r -> do
        x <- m
        g (r . (x:))

or written with explicit recursion:

sequencel xs = go xs id
    where
      go []     r = return $ r []
      go (m:ms) r = do x <- m
                       go ms (r . (x:))

Note that I used a difference list to keep the list in the right
order. Alternatively you can use a normal list (x:r) and reverse it
when done. I'm not sure what's more efficient.

I'm surprised I haven't encountered this problem with sequence before.
Does this suggest we need the left folded sequencel?

Regards,

Bas