[Haskell-cafe] Re: tail recursion ?

[Jon Fairbairn]

"Simon Brenner" <simbr843 at student.liu.se> writes:

> 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 at cl.cam.ac.uk