Potential space leak in transpose

[David Feuer]

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20200511/48ac5da2/attachment.html>