Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder2.hal-mli.net!feeder.erje.net!eu.feeder.erje.net!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail From: Piotr Kalinowski Newsgroups: comp.lang.haskell Subject: Re: Space leak Date: Thu, 13 Dec 2012 13:58:52 +0100 Organization: A noiseless patient Spider Lines: 29 Message-ID: References: <7x1ueuhp8k.fsf@ruckus.brouhaha.com> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: mx04.eternal-september.org; posting-host="1a09fb6db84db8196e17f0b17d92738a"; logging-data="9697"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/t5cs9SPomtYrrq9h3O/rx" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2 (darwin) Cancel-Lock: sha1:tmHdfNDFQjRrp9Xhok94R1NczHo= sha1:5bT9BKAJnVU+BzrFfBdkVsFc5wQ= Xref: csiph.com comp.lang.haskell:239 Paul Rubin 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