transpose still leaks

Summary

My recent change to transpose was too fragile. Whoops!

I now have a proper fix and a test, but I don't currently have things set up on my side to integrate the test, so I could use some help. Here's the fix:

transpose :: [[a]] -> [[a]]
transpose [] = []
transpose ([] : xss) = transpose xss
transpose ((x : xs) : xss) = combine x hds xs tls
  where
    (hds,tls) = unzip [(hd, tl) | hd : tl <- xss]
    combine x h xs t = (x:h) : transpose (xs:t)
    {-# NOINLINE combine #-}

The combine function ensures that we allocate the tls selector thunk before we reach the tail of the result. Otherwise, GHC wants to do something like (x:h) : let tls = ... in ..., which is no good at all.

Here's the test:

import Data.List (transpose, foldl')

thingy :: [[[Int]]]
thingy = [ [[1],[2]], [[1..10^7], [3]]]

thingy2 :: [[[Int]]]
thingy2 = [ [[1],[2]], [[3], [2..10^7+1]]]

main = do
  htr : ttr <- pure $ L.transpose thingy
  print $ foldl' (+) 0 . head . tail $ htr
  print ttr

  htr2 : ttr2 <- pure $ L.transpose thingy2
  print $ foldl' (+) 0 . head . tail . head $ ttr2
  print htr2

Maximum residency should be quite low. I get 44,504 bytes, but anything under 200,000 should be fine. With the original transpose implementation, residency jumps to over 354,000,000 and the test goes slow as molasses.

The test works with or without optimization, but we need to be sure to run it with optimization to make sure the optimizer doesn't muck anything up.