Re: Potential space leak in transpose

unzip should fuse with its argument, so inlining presumably won't do anything there. The pairs that unzip itself creates are actually what prevent the leak. GHC creates "selector thunks" to deconstruct them, which the garbage collector can reduce. The garbage collector will never reduce the deconstruction of list conses. On Wed, May 13, 2020, 4:27 PM Ryan Reich wrote:

Why not just inline the definition of unzip and hand-optimize away the pairs?

On Tue, May 12, 2020, 10:24 David Feuer 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 wrote:

...

The cost of allocating the extra pairs.

On Tue, May 12, 2020, 5:11 AM Andreas Abel 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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries