Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.haskell > #239

Re: Space leak

Show all headers | View raw

Paul Rubin <no.email@nospam.invalid> writes:

> I had a space leak in a program that I distilled down to the following:
>
>    main = print $ length (replicateM 15 "012")
>
> This should generate all the 15-digit ternary numbers (with leading 0's)
> so the length of the list is 3**15=14348907.  It gets that result
> correctly, but uses almost a gigabyte of ram in computing it.
>
> As an exercise I wrote my own version of the List datatype and the monad
> instance for it doing the obvious things, and the same behavior
> happened.  Writing a strict version of the length function using foldl1'
> didn't help either.
>
> It's not real obvious to me what's going on.  Is there a simple
> explanation why replicateM doesn't generate values lazily that are
> consumed by length?

replicateM could produce result lazily, but length still needs to
traverse the whole list in order to determine its length. This process
of traversing the list forces evaluation of all its contents.

In other words, length does not consume values returned by replicateM.
It consumes a single value: a list, and it needs to fully evaluate it's
structure.

Regards,
Piotr Kalinowski

Back to comp.lang.haskell | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Space leak Paul Rubin <no.email@nospam.invalid> - 2012-12-12 14:36 -0800
  Re: Space leak Piotr Kalinowski <pitkali@gmail.com> - 2012-12-13 13:58 +0100
    Re: Space leak Paul Rubin <no.email@nospam.invalid> - 2012-12-13 08:40 -0800
      Re: Space leak Piotr Kalinowski <pitkali@gmail.com> - 2012-12-17 14:18 +0100
      Re: Space leak Wolfgang Ehrlich <wolfgang.ehrlich@googlemail.com> - 2013-01-08 06:15 -0800
        Re: Space leak Wolfgang Ehrlich <wolfgang.ehrlich@googlemail.com> - 2013-01-09 00:15 -0800
  Re: Space leak Dirk Thierbach <dthierbach@usenet.arcornews.de> - 2012-12-14 00:07 +0100
  Re: Space leak "Albert Y. C. Lai" <trebla@vex.net> - 2012-12-24 18:51 -0500

csiph-web