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

Question

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

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

而

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

thunk 链。

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

map tail

重击。

例如，它使用

transpose

中的

Data.List

在恒定空间中运行，因为

length

调用会强制每个内部列表的主干。 （不过，它不适用于您的简化版

transpose

——我还没有花时间试图找出原因。）

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

对于更明确的解决方案，以下似乎工作正常。

forcelist2

函数确保外部列表中强制执行的每个

(:)

都会强制执行头元素，

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