Potential space leak in transpose

[Andreas Abel]

On 2020-05-13 22:27, Ryan Reich wrote:
> Why not just inline the definition of unzip and hand-optimize away the 
> pairs?

Isn't this what the original code of transpose is doing?

> On Tue, May 12, 2020, 10:24 David Feuer <david.feuer at gmail.com 
> <mailto:david.feuer at gmail.com>> wrote:
> 
>     Also, the more eager list allocation can increase residency, but I
>     don't think it can cause a leak.
> 
>     On Tue, May 12, 2020, 9:48 AM David Feuer <david.feuer at gmail.com
>     <mailto:david.feuer at gmail.com>> wrote:
> 
>         The cost of allocating the extra pairs.
> 
>         On Tue, May 12, 2020, 5:11 AM Andreas Abel
>         <andreas.abel at ifi.lmu.de <mailto:andreas.abel at ifi.lmu.de>> wrote:
> 
>               > I don't know how much that'll cost in practice.
> 
>             What costs are you worried about?
> 
>             On 2020-05-12 00:08, David Feuer wrote:
>              > In Data.List, we define
>              >
>              > transpose :: [[a]] -> [[a]]
>              > transpose [] = []
>              > transpose ([] : xss) = transpose xss
>              > transpose ((x : xs) : xss) = (x : [h | (h : _) <- xss]) :
>             transpose (xs
>              > : [t | (_ : t) <- xss])
>              >
>              > The potential difficulty is that we essentially mapMaybe
>             over the xss
>              > list twice in the third case. So we hang on to the heads
>             where we need
>              > the tails and the tails where we need the heads. We could
>             fix that with
>              > something like this:
>              >
>              > transpose ((x : xs) : xss) = (x : fronts) : transpose (xs
>             : rears)
>              >    where
>              >      (fronts, rears) = unzip [(h,t) | (h : t) <- xss]
>              >
>              > I don't know how much that'll cost in practice.
>              >
>              > _______________________________________________
>              > Libraries mailing list
>              > Libraries at haskell.org <mailto:Libraries at haskell.org>
>              > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>              >
> 
>     _______________________________________________
>     Libraries mailing list
>     Libraries at haskell.org <mailto:Libraries at haskell.org>
>     http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
> 
> 
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>