You seem to ignore garbage collection.<br><br><div class="gmail_quote">On Sat, Sep 24, 2011 at 6:40 AM, Arseniy Alekseyev <span dir="ltr"><<a href="mailto:arseniy.alekseyev@gmail.com">arseniy.alekseyev@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="im">> Apparently it doesn't, and it seems to be fixed now.<br>
<br>
</div>Does anyone know what exactly the bug was? Because this seems like a<br>
serious bug to me. I've run into it myself today and wasn't happy.<br>
Linear algorithms should work in linear time however much memory they<br>
allocate (modulo cache thrashing of course). Existence of people<br>
claiming otherwise surprises me!<br>
<div><div></div><div class="h5"><br>
<br>
On 22 September 2011 01:05, John Lato <<a href="mailto:jwlato@gmail.com">jwlato@gmail.com</a>> wrote:<br>
> On Wed, Sep 21, 2011 at 1:57 PM, Tim Docker <<a href="mailto:tim@dockerz.net">tim@dockerz.net</a>> wrote:<br>
>><br>
>> On 09/09/2011, at 8:19 PM, John Lato wrote:<br>
>><br>
>>> Agreed. Whenever I'd like to use mapM (or any other function for<br>
>>> which a *M_ is available), I've found the following rules helpful:<br>
>>><br>
>>> 1. If I can guarantee the list is short (~ n<=20), go ahead and use mapM<br>
>>> 2. Otherwise use mapM_, foldM_, or foldM if a real reduction is<br>
>>> possible (i.e. not "foldM snocM []").<br>
>>><br>
>>> Step 2 sometimes requires changing my design, but it's always been for<br>
>>> the better. `mapM_` tends to require more pipeline composition, so<br>
>>> it's leveraging the language's strengths.<br>
>><br>
>> This thread is really interesting - it relates directly to problems I am<br>
>> currently<br>
>> having with mapM over large lists (see the thread "stack overflow pain").<br>
>><br>
>> Can you explain what you mean by "mapM_ tends to require more pipeline<br>
>> composition"?<br>
>> In what way is it leveraging the language strengths?<br>
><br>
> Hmm, that is suitably cryptic. One way to think of it is an inversion<br>
> of control. Instead of operating on whole collections of things in a<br>
> monad, you specify monadic actions (pipelines) which are applied<br>
> sequentially to each input.<br>
><br>
> Here's a simple example. Suppose you have a bunch of data serialized<br>
> to files, and you want to read each file into a data structure, apply<br>
> some process based upon the last file's data, and write out the output<br>
> to new files. One way to do that would look like:<br>
><br>
> do<br>
> dats <- mapM readMyData files<br>
> let pairs = zip (mempty:dats) dats<br>
> zipWithM_ (\(last, this) fname -> writeMyData (update last this)<br>
> fname) pairs newFiles<br>
><br>
> However, you could also put everything into a single monadic<br>
> operation, like this<br>
><br>
> do<br>
> foldM_ (\last (infile, outfile) -> do<br>
> this <- readMyData infile<br>
> writeMyData<br>
> (update last this) outfile<br>
> return this<br>
> )<br>
> mempty<br>
> (zip files newFiles)<br>
><br>
> The first interleaves control (mapM, zipWIthM_) with monadic actions<br>
> (file IO), whereas the second only has one control function (foldM_)<br>
> which completely processes one input. I say this is more pipeline<br>
> composition because you have to create an entire pipeline from input<br>
> to output, which is then sequentially fed inputs by the control<br>
> function.<br>
><br>
> I say this leverages Haskell's strengths because it's quite easy to<br>
> compose functions and monadic actions in Haskell. It also tends to be<br>
> garbage-collector friendly. I also find it much easier to reason<br>
> about space usage. You don't need to worry if part of a list is being<br>
> retained, because the full list of data doesn't appear anywhere. If<br>
> you need to access prior elements they're specified explicitly so you<br>
> know exactly how much data you're holding on to.<br>
><br>
> My perspective might be warped by my work on iteratees, but I find<br>
> this a very natural approach.<br>
><br>
> John L.<br>
><br>
> _______________________________________________<br>
> Haskell-Cafe mailing list<br>
> <a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
> <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
><br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</div></div></blockquote></div><br>