"Simon Brenner"
The key is letting haskell be lazy and produce the output one item at a time.
True.
This solution goes up to 100k in 25M of heap and up to 400k in 200M of heap. While working better, the space requirement seems to be (at least almost) quadratic, so this is probably not a complete solution to your problem (unless all you really needed was those 10k elements, or at most 400k).
Hmmm... what were you testing? :m Data.Array Prelude Data.Array> let test upb = let a = listArray (1,upb) (repeat False) in a//map (\n->(2^n,not (a!(2^n)))) [1..floor (logBase 2 $ fromIntegral upb)] ! upb (0.02 secs, 1567316 bytes) Prelude Data.Array> test 100000 False (0.02 secs, 1310876 bytes) Prelude Data.Array> test 400000 False (0.09 secs, 3710792 bytes) Prelude Data.Array> test 800000 False (0.16 secs, 6913864 bytes) Prelude Data.Array> -- Jón Fairbairn Jon.Fairbairn@cl.cam.ac.uk