<div dir="auto"><div>My suggestion was much less sophisticated even than that, and is basically what David answered with fusion. Also according to his answer, the original code of transpose lacks the laziness that unzip's actual implementation would provide.</div><div dir="auto"><br></div><div dir="auto">I think what that means is that his concern over allocating extra pairs is about the ones created internally by unzip when it builds the lazy heads-and-tails accessors.<br><br><div class="gmail_quote" dir="auto"><div dir="ltr" class="gmail_attr">On Thu, May 14, 2020, 03:27 Andreas Abel <<a href="mailto:andreas.abel@ifi.lmu.de">andreas.abel@ifi.lmu.de</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On 2020-05-13 22:27, Ryan Reich wrote:<br>
> Why not just inline the definition of unzip and hand-optimize away the <br>
> pairs?<br>
<br>
Isn't this what the original code of transpose is doing?<br>
<br>
> On Tue, May 12, 2020, 10:24 David Feuer <<a href="mailto:david.feuer@gmail.com" target="_blank" rel="noreferrer">david.feuer@gmail.com</a> <br>
> <mailto:<a href="mailto:david.feuer@gmail.com" target="_blank" rel="noreferrer">david.feuer@gmail.com</a>>> wrote:<br>
> <br>
>     Also, the more eager list allocation can increase residency, but I<br>
>     don't think it can cause a leak.<br>
> <br>
>     On Tue, May 12, 2020, 9:48 AM David Feuer <<a href="mailto:david.feuer@gmail.com" target="_blank" rel="noreferrer">david.feuer@gmail.com</a><br>
>     <mailto:<a href="mailto:david.feuer@gmail.com" target="_blank" rel="noreferrer">david.feuer@gmail.com</a>>> wrote:<br>
> <br>
>         The cost of allocating the extra pairs.<br>
> <br>
>         On Tue, May 12, 2020, 5:11 AM Andreas Abel<br>
>         <<a href="mailto:andreas.abel@ifi.lmu.de" target="_blank" rel="noreferrer">andreas.abel@ifi.lmu.de</a> <mailto:<a href="mailto:andreas.abel@ifi.lmu.de" target="_blank" rel="noreferrer">andreas.abel@ifi.lmu.de</a>>> wrote:<br>
> <br>
>               > I don't know how much that'll cost in practice.<br>
> <br>
>             What costs are you worried about?<br>
> <br>
>             On 2020-05-12 00:08, David Feuer wrote:<br>
>              > In Data.List, we define<br>
>              ><br>
>              > transpose :: [[a]] -> [[a]]<br>
>              > transpose [] = []<br>
>              > transpose ([] : xss) = transpose xss<br>
>              > transpose ((x : xs) : xss) = (x : [h | (h : _) <- xss]) :<br>
>             transpose (xs<br>
>              > : [t | (_ : t) <- xss])<br>
>              ><br>
>              > The potential difficulty is that we essentially mapMaybe<br>
>             over the xss<br>
>              > list twice in the third case. So we hang on to the heads<br>
>             where we need<br>
>              > the tails and the tails where we need the heads. We could<br>
>             fix that with<br>
>              > something like this:<br>
>              ><br>
>              > transpose ((x : xs) : xss) = (x : fronts) : transpose (xs<br>
>             : rears)<br>
>              >    where<br>
>              >      (fronts, rears) = unzip [(h,t) | (h : t) <- xss]<br>
>              ><br>
>              > I don't know how much that'll cost in practice.<br>
>              ><br>
>              > _______________________________________________<br>
>              > Libraries mailing list<br>
>              > <a href="mailto:Libraries@haskell.org" target="_blank" rel="noreferrer">Libraries@haskell.org</a> <mailto:<a href="mailto:Libraries@haskell.org" target="_blank" rel="noreferrer">Libraries@haskell.org</a>><br>
>              > <a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
>              ><br>
> <br>
>     _______________________________________________<br>
>     Libraries mailing list<br>
>     <a href="mailto:Libraries@haskell.org" target="_blank" rel="noreferrer">Libraries@haskell.org</a> <mailto:<a href="mailto:Libraries@haskell.org" target="_blank" rel="noreferrer">Libraries@haskell.org</a>><br>
>     <a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
> <br>
> <br>
> _______________________________________________<br>
> Libraries mailing list<br>
> <a href="mailto:Libraries@haskell.org" target="_blank" rel="noreferrer">Libraries@haskell.org</a><br>
> <a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
> <br>
</blockquote></div></div></div>