为什么我的 haskell 程序使用“transpose”会出现空间泄漏

Question

我的 Haskell 程序中存在空间泄漏，我可以将其查明为一个最小的示例，如下所示。我希望以下代码（尽管不会终止，但我不在乎）在常量内存中运行，但事实并非如此：

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

whilehead . filter (const False) $ [1..]确实在恒定内存中运行。

所以我猜这一定与在无限列表上使用“转置”有关。忽略更复杂的基础库实现，如果我们定义转置transpose xss = map head xss : transpose (map tail xss)，为什么会出现空间泄漏？map head xss我的假设是垃圾收集器可以释放以前在函数的每个步骤中消耗的内存filter。我想这map tail xss会以某种方式阻止这种情况发生？！无论如何，我可以添加某种严格性注释或类似的注释，transpose以便该简单的示例确实在恒定内存中运行吗？

Answer 1

在您的程序中，经过几次迭代后，transpose [[1..]]使用简化版本生成的列表如下所示：transpose

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..]]))))

由于您的filter函数仅强制此列表的主干，因此即使这些初始值被丢弃，您仍然会增长无限的嵌套重击链map tail。

在您的示例中，它应该足以强制内部列表的脊柱，因为这将解决嵌套的map tail重击。

例如，它使用transposefrom在恒定空间中运行Data.List，因为length调用会强制每个内部列表的主干。（不过，它不适用于您的 simple transpose。有关原因的解释，请参阅@Ben对此答案的评论。）

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

对于更明确的解决方案，以下似乎工作正常。该forcelist2函数确保(:)外部列表中强制的每个元素都会强制 head 元素，并且该forcelist函数确保内部列表被强制到末尾，从而[]可以解决最终问题。

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..]]