Remove potential space leak from Data.List.transpose

Previously, `transpose` produced a list of heads
and a list of tails independently. This meant that
a function using only some heads, and only some tails,
could potentially leak space. Use `unzip` to work
around the problem by producing pairs and selector
thunks instead. Time and allocation behavior will
be worse, but there should be no more leak potential.

1 files changed, 7 insertions, 1 deletions

diff --git a/libraries/base/Data/OldList.hs b/libraries/base/Data/OldList.hs
index 0252ae0fd8..9331113d70 100644
--- a/libraries/base/Data/OldList.hs
+++ b/libraries/base/Data/OldList.hs
@@ -550,7 +550,13 @@ intercalate xs xss = concat (intersperse xs xss)
 transpose               :: [[a]] -> [[a]]
 transpose []             = []
 transpose ([]   : xss)   = transpose xss
-transpose ((x:xs) : xss) = (x : [h | (h:_) <- xss]) : transpose (xs : [ t | (_:t) <- xss])
+transpose ((x:xs) : xss) = (x : hds) : transpose (xs : tls)
+  where
+    -- We tie the calculations of heads and tails together
+    -- to prevent heads from leaking into tails and vice versa.
+    -- unzip makes the selector thunk arrangements we need to
+    -- ensure everything gets cleaned up properly.
+    (hds, tls) = unzip [(hd, tl) | (hd:tl) <- xss]
 
 
 -- | The 'partition' function takes a predicate a list and returns