[Haskell-cafe] following up on space leak

Paul L ninegua at gmail.com
Sun Jul 5 22:06:28 EDT 2009


Previously you had lastOrNil taking m [a] as input, presumably
generated by mapM. So mapM is actually building an entire list before
it returns the argument for you to call lastOrNil. This is where you
had unexpected memory behavior.

Now you are "fusing" lastOrNil and mapM together, and instead of
building a list, you traverse it and perform monadic action along the
way. This can happen in a constant memory if the original pure list is
generated lazily.

I think the real problem you had was a mis-understanding of mapM, and
there was nothing wrong with your previous lastOrNil function. mapM
will only return a list after all monadic actions are performed, and
in doing so, it inevitably has to build the entire list along the way.

-- 
Regards,
Paul Liu

Yale Haskell Group
http://www.haskell.org/yale

On 7/4/09, Uwe Hollerbach <uhollerbach at gmail.com> wrote:
> Good evening, all, following up on my question regarding space leaks,
> I seem to have stumbled across something very promising. I said I was
> using this tiny function "lastOrNil" to get the last value in a list,
> or the empty (scheme) list if the haskell list was empty. The uses of
> it were all of the form
>
>     lastOrNil (mapM <something> <some list>)
>
> so I wrote a different function mapML to do this directly:
>
>> mapML fn lst = mapMLA (List []) fn lst
>>   where mapMLA r _ [] = return r
>>         mapMLA ro fn (x:xs) =
>>            do rn <- fn x
>>               mapMLA rn fn xs
>
> This isn't an accumulator, it's a replacer (or, if you like, the
> "accumulation" is "drop the old one on the floor"), it starts out with
> the scheme empty list that I want as the default, and it never even
> builds the list which it'll just dump an instant later. Shazam! Memory
> usage dropped by roughly an order of magnitude in my little Collatz
> benchmark, and incidentally runtime improved by 25% or so as well. The
> horror! :-)
>
> Having tasted blood, I will of course be continuing to benchmark...
> but not tonight.
>
> Uwe
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>


More information about the Haskell-Cafe mailing list