Re: Potential space leak in transpose

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