Potential space leak in transpose

[Andreas Abel]

 > 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
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>