Why is there a space leak in my haskell program using `transpose`

Question

I have a space leak in my Haskell programm, I could pinpoint it to a minimal example as follows. I would expect the following code (albeit not terminating but I don't care) to run in constant memory but it doesn't:

head . filter (const False) $ (transpose [[1..]])

while head . filter (const False) $ [1..] does run in constant memory.

So it must have to do with usage of 'transpose' on infinite lists I guess. Ignoring the more complicated base library implementation, if we define transpose like transpose xss = map head xss : transpose (map tail xss) , why is there a space leak ? My assumption was that the garbage collector could free the memory formerly consumed by map head xss in every step of the filter function. I guess that the map tail xss somehow prevents that ?! anyway, could I add some sort of strictness annotation or similar to transpose so that that simple example does run in constant memory?

Answer 1

In your program, the list produced by transpose [[1..]] using the simplified version of transpose looks like this after a few iterations:

map head [[1..]]
  : map head (map tail [[1..]]) 
  : map head (map tail (map tail [[1..]])) 
  : map head (map tail (map tail (map tail [[1..]]))) 
  : transpose (map tail (map tail (map tail (map tail [[1..]]))))

Since your filter function is only forcing the spine of this list, even when those initial values are tossed, you're still growing a infinite chain of nested map tail thunks.

In your example, it should be enough to force the spines of the inner lists, since this will resolve the nested map tail thunks.

For example, this runs in constant space using the transpose from Data.List because the length call forces the spine of each inner list. (It doesn't work with your simplified transpose, though. See @Ben's comment on this answer for an explanation why.)

main =
  print $ head . filter (\x -> length x < 0) $ transpose [[1..]]

For a more explicit solution, the following seems to work fine. The forcelist2 function ensures that every (:) that's forced in the outer list forces the head element, and the forcelist function ensures that the inner lists are forced to the end, where the final [] can be resolved.

import Data.List

transpose' :: [[a]] -> [[a]]
transpose' = forcelist2 . transpose

forcelist2 :: [[a]] -> [[a]]
forcelist2 (x:xs) = let !y = forcelist x in y : forcelist2 xs
forcelist :: [a] -> [a]
forcelist (x:xs) = let !ys = forcelist xs in x : ys
forcelist [] = []

main = print $ head . filter (const False) . forcelist2 $ transpose' [[1..]]