<div dir="auto"><div>The cost of allocating the extra pairs.<br><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, May 12, 2020, 5:11 AM 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"> > 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]) : transpose (xs <br>
> : [t | (_ : t) <- xss])<br>
> <br>
> The potential difficulty is that we essentially mapMaybe over the xss <br>
> list twice in the third case. So we hang on to the heads where we need <br>
> the tails and the tails where we need the heads. We could fix that with <br>
> something like this:<br>
> <br>
> transpose ((x : xs) : xss) = (x : fronts) : transpose (xs : 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><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>