<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">How about the following variant?<div class=""><br class=""></div><div class=""><div class=""> transpose = takeWhile (not . null) . foldr (foldr f id) (repeat [])</div><div class=""> where</div><div class=""> f x xs ~(y:ys) = (x:y) : xs ys</div><div class=""><br class=""></div><div class="">Although I don’t really understand the memory leak situation, I think you might be able to get the pair behaviour with a stream type:</div><div class=""><br class=""></div><div class=""><div class=""> data Stream a = a :< Stream a</div><div class=""><br class=""></div><div class=""> streamToList :: Stream [a] -> [[a]]</div><div class=""> streamToList ([] :< _ ) = []</div><div class=""> streamToList (x :< xs) = x : streamToList xs</div><div class=""><br class=""></div><div class=""> transpose = streamToList . foldr (foldr f id) (fix ([] :<))</div><div class=""> where</div><div class=""> f x xs ~(y :< ys) = (x:y) :< xs ys</div></div><div class=""><br class=""></div><div class="">And you could turn the streamToList function into a good producer like so:</div><div class=""><br class=""></div><div class=""><div class=""> streamToList :: Stream [a] -> [[a]]</div><div class=""> streamToList xs =</div><div class=""> build (\c n -> </div><div class=""> let go ([] :< _ ) = n</div><div class=""> go (x :< xs) = c x (go xs)</div><div class=""> in go xs)</div></div><div><br class=""></div><div>The other advantage of this of course is that transpose becomes a good consumer.</div><div><br class=""><blockquote type="cite" class=""><div class="">On 15 May 2020, at 01:15, David Feuer <<a href="mailto:david.feuer@gmail.com" class="">david.feuer@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="auto" class="">That doesn't look like it works on infinite lists.</div><br class=""><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, May 14, 2020, 8:09 PM Ryan Reich <<a href="mailto:ryan.reich@gmail.com" class="">ryan.reich@gmail.com</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class=""><div class="">Hopefully I'm not fooling myself...how about this?</div><div class=""><br class=""></div><div class="">---</div><div class="">transpose :: [[a]] -> [[a]]<br class="">transpose [] = []<br class="">transpose (r1 : rrest) = zipWith' (:) (:[]) id r1 (transpose rrest)</div><div class=""><br class=""></div><div class="">zipWith' :: (a -> b -> c) -> (a -> c) -> (b -> c) -> ([a] -> [b] -> [c])<br class="">zipWith' _ _ fb [] bs = fb <$> bs<br class="">zipWith' _ fa _ as [] = fa <$> as<br class="">zipWith' f fa fb (a : as) (b : bs) = f a b : zipWith' f fa fb as bs<br class=""><br class="">main = do<br class=""> mapM_ (print . transpose)<br class=""> [<br class=""> [[1,2,3]],<br class=""> [[1,2,3],[4,5,6]],<br class=""> [[1,2,3],[4,5,6],[7,8,9]],<br class=""> [[10,11],[20],[],[30,31,32]]<br class=""> ]</div><div class="">---</div><div class=""><br class=""></div><div class="">I see the output:</div><div class="">---</div><div class="">[[1],[2],[3]]<br class="">[[1,4],[2,5],[3,6]]<br class="">[[1,4,7],[2,5,8],[3,6,9]]<br class="">[[10,20,30],[11,31],[32]]</div><div class="">---</div><div class=""><br class=""></div><div class="">which is correct (the last example is the one from the haddocks).</div><div class=""><br class=""></div><div class="">I was concerned that the definition of zipWith' (which is akin to the Map function unionWith) is not compatible with the build/fold fusion rule, but the implementation of zipWith itself is basically the same.<br class=""></div><div class=""><br class=""></div><div class="">Ryan<br class=""></div></div><br class=""><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, May 14, 2020 at 1:17 PM David Feuer <<a href="mailto:david.feuer@gmail.com" target="_blank" rel="noreferrer" class="">david.feuer@gmail.com</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto" class="">Right. I still think it might be the right thing to do, though. I'm not a big fan of general-purpose library functions that have any unnecessary memory leak hazard. The biggest counterargument is that real code is unlikely to run into that problem.</div><br class=""><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, May 14, 2020, 3:35 PM Ryan Reich <<a href="mailto:ryan.reich@gmail.com" target="_blank" rel="noreferrer" class="">ryan.reich@gmail.com</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto" class=""><div class="">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" class=""><br class=""></div><div dir="auto" class="">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 class=""><br class=""><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" rel="noreferrer noreferrer" target="_blank" class="">andreas.abel@ifi.lmu.de</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On 2020-05-13 22:27, Ryan Reich wrote:<br class="">
> Why not just inline the definition of unzip and hand-optimize away the <br class="">
> pairs?<br class="">
<br class="">
Isn't this what the original code of transpose is doing?<br class="">
<br class="">
> On Tue, May 12, 2020, 10:24 David Feuer <<a href="mailto:david.feuer@gmail.com" rel="noreferrer noreferrer noreferrer" target="_blank" class="">david.feuer@gmail.com</a> <br class="">
> <mailto:<a href="mailto:david.feuer@gmail.com" rel="noreferrer noreferrer noreferrer" target="_blank" class="">david.feuer@gmail.com</a>>> wrote:<br class="">
> <br class="">
> Also, the more eager list allocation can increase residency, but I<br class="">
> don't think it can cause a leak.<br class="">
> <br class="">
> On Tue, May 12, 2020, 9:48 AM David Feuer <<a href="mailto:david.feuer@gmail.com" rel="noreferrer noreferrer noreferrer" target="_blank" class="">david.feuer@gmail.com</a><br class="">
> <mailto:<a href="mailto:david.feuer@gmail.com" rel="noreferrer noreferrer noreferrer" target="_blank" class="">david.feuer@gmail.com</a>>> wrote:<br class="">
> <br class="">
> The cost of allocating the extra pairs.<br class="">
> <br class="">
> On Tue, May 12, 2020, 5:11 AM Andreas Abel<br class="">
> <<a href="mailto:andreas.abel@ifi.lmu.de" rel="noreferrer noreferrer noreferrer" target="_blank" class="">andreas.abel@ifi.lmu.de</a> <mailto:<a href="mailto:andreas.abel@ifi.lmu.de" rel="noreferrer noreferrer noreferrer" target="_blank" class="">andreas.abel@ifi.lmu.de</a>>> wrote:<br class="">
> <br class="">
> > I don't know how much that'll cost in practice.<br class="">
> <br class="">
> What costs are you worried about?<br class="">
> <br class="">
> On 2020-05-12 00:08, David Feuer wrote:<br class="">
> > In Data.List, we define<br class="">
> ><br class="">
> > transpose :: [[a]] -> [[a]]<br class="">
> > transpose [] = []<br class="">
> > transpose ([] : xss) = transpose xss<br class="">
> > transpose ((x : xs) : xss) = (x : [h | (h : _) <- xss]) :<br class="">
> transpose (xs<br class="">
> > : [t | (_ : t) <- xss])<br class="">
> ><br class="">
> > The potential difficulty is that we essentially mapMaybe<br class="">
> over the xss<br class="">
> > list twice in the third case. So we hang on to the heads<br class="">
> where we need<br class="">
> > the tails and the tails where we need the heads. We could<br class="">
> fix that with<br class="">
> > something like this:<br class="">
> ><br class="">
> > transpose ((x : xs) : xss) = (x : fronts) : transpose (xs<br class="">
> : rears)<br class="">
> > where<br class="">
> > (fronts, rears) = unzip [(h,t) | (h : t) <- xss]<br class="">
> ><br class="">
> > I don't know how much that'll cost in practice.<br class="">
> ><br class="">
> > _______________________________________________<br class="">
> > Libraries mailing list<br class="">
> > <a href="mailto:Libraries@haskell.org" rel="noreferrer noreferrer noreferrer" target="_blank" class="">Libraries@haskell.org</a> <mailto:<a href="mailto:Libraries@haskell.org" rel="noreferrer noreferrer noreferrer" target="_blank" class="">Libraries@haskell.org</a>><br class="">
> > <a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer noreferrer noreferrer noreferrer" target="_blank" class="">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br class="">
> ><br class="">
> <br class="">
> _______________________________________________<br class="">
> Libraries mailing list<br class="">
> <a href="mailto:Libraries@haskell.org" rel="noreferrer noreferrer noreferrer" target="_blank" class="">Libraries@haskell.org</a> <mailto:<a href="mailto:Libraries@haskell.org" rel="noreferrer noreferrer noreferrer" target="_blank" class="">Libraries@haskell.org</a>><br class="">
> <a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer noreferrer noreferrer noreferrer" target="_blank" class="">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br class="">
> <br class="">
> <br class="">
> _______________________________________________<br class="">
> Libraries mailing list<br class="">
> <a href="mailto:Libraries@haskell.org" rel="noreferrer noreferrer noreferrer" target="_blank" class="">Libraries@haskell.org</a><br class="">
> <a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer noreferrer noreferrer noreferrer" target="_blank" class="">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br class="">
> <br class="">
</blockquote></div></div></div>
</blockquote></div>
</blockquote></div>
</blockquote></div>
_______________________________________________<br class="">Libraries mailing list<br class=""><a href="mailto:Libraries@haskell.org" class="">Libraries@haskell.org</a><br class="">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries<br class=""></div></blockquote></div><br class=""></div></body></html>