On 13-08-26 04:46 AM, Niklas Hambüchen wrote:
Effectively, sequence is a partial function.
(Note: We are not trying to obtain a lazy list of random numbers, use
any kind of streaming or the likes. We want the list in memory and use it.)
We noticed that this problem did not happen if sequence were implemented
with a difference list.
What do you think about this? Should we "fix" functions like this,
probably trading off a small performance hit, or accept that idiomatic
Haskell code can crash at any time?
1. Disputed: "sequence overflows stack, for all monads"
(Bonus: a demo of Control.Monad.ST.Lazy)
(Bonus: a secret of Control.Monad.State revealed)
import Control.Monad.ST.Lazy(runST)
import Control.Monad.State(evalState)
long :: Monad m => m [Int]
long = sequence (map return [1..1000000])
infinite :: Monad m => m [()]
infinite = sequence (repeat (return ()))
-- these take constant time
one_a = take 1 (runST long)
one_b = take 1 (evalState long ())
unit_a = take 1 (runST infinite)
unit_b = take 1 (evalState infinite ())
sequence is exactly right for Control.Monad.ST.Lazy and
Control.Monad.State. If you fix sequence, you will cause idiomatic use
of sequence and Control.Monad.State to use too much time (up to
infinite) and too much memory (up to infinite).
Note: Control.Monad.State = Control.Monad.State.Lazy
For more demos of Control.Monad.ST.Lazy and Control.Monad.State(.Lazy),
see my
http://lpaste.net/41790
http://lpaste.net/63925
2. What to do for IO, Control.Monad.ST, Control.Monad.State.Strict, etc
As you said, we can combine right recursion (foldM) and difference list
(aka Hughes list). I will dispute its questionable benefit in the next
section, but here it is first.
sequence_hughes ms = do
h <- go id ms
return (h [])
where
go h [] = return h
go h (m:ms) = do
x <- m
go (h . (x :)) ms
equivalently,
sequence_hughes ms = do
h <- foldM op id ms
return (h [])
where
op h m = do
x <- m
return (h . (x :))
However, as I said, sequence_hughes is totally wrong for
Control.Monad.State and Control.Monad.ST.Lazy. And this is not even my
dispute of the questionable benefit.
3. Disputed: "stack is limited, heap is unlimited"
sequence_hughes consumes linear heap space in place of linear stack
space. That's all it does. There is no free lunch.
Empirically: on linux i386 32-bit GHC 7.6.3 -O2:
xs <- sequence (replicate 2000000 (return 0 :: IO Int))
print (head xs)
8MB stack, 16MB heap
xs <- sequence_hughes (replicate 2000000 (return 0 :: IO Int))
print (head xs)
24MB heap
What has sequence_hughes saved?
Since a couple of years ago, GHC RTS has switched to growable stack,
exactly like growable heap. It starts small, then grows and shrinks as
needed. It does not need a cap. The only reason it is still capped is
the petty:
"to stop the program eating up all the available memory in the machine
if it gets into an infinite loop" (GHC User's Guide)
Asymmetrically, the heap is not capped by default to stop the program
eating up all the available memory.
And the default stack cap 8MB is puny, compared to the hundreds of MB
you will no doubt use in the heap. (Therefore, on 64-bit, you have to
change 2000000 to 1000000 in the above.) (Recall: [Int] of length n
entirely in memory takes at least 12n bytes: 4 for pointer to Int, 4 for
the number itself, 4 for pointer to next, and possibly a few more bytes
I forgot, and possibly a few more bytes if the Int is lazy e.g. randomIO
as Bryan said. That's just on 32-bit. Multiply by 2 on 64-bit.)
The correct fix is to raise the stack cap, not to avoid using the stack.
Indeed, ghci raises the stack cap so high I still haven't fathomed where
it is. This is why you haven't seen a stack overflow in ghci for a long
time. See, ghci agrees: the correct thing to do is to raise the stack cap.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
