[Haskell] space behaviour of lazy recursive lists

Adrian Hey ahey at iee.org
Sun Jan 30 15:15:48 EST 2005


On Sunday 30 Jan 2005 4:00 pm, Axel Jantsch wrote:
> Main> nth 100 fibs
>   10
>   (2818 reductions, 3730 cells, 1 garbage collection)
>
> Main> nth 200 fibs
>   10
>   (5618 reductions, 7430 cells, 1 garbage collection)
>
> which suggests linear space behaviour.

Hmm, not sure exactly what Hugs is measuring here.
I suspect this is a measure of total allocation during
program execution rather than maximimum memory in use
at any time during execution. So you'd expect to see
this kind of thing anyway.

As it happens, I think both heap and stack requirement
will be proportional to the first arg of nth for the
reasons I indicated earlier. But I think the version
using zipWith' will execute in constant space (but this
doesn't mean constant cell allocation, you'll probably
still see <some large number> of cells used).

Regards
--
Adrian Hey



More information about the Haskell mailing list