生成元组列表时内存泄漏

Question

以下代码为类型的量词计算数字树¹Quant,类似于函数的类型all和any:

treeOfNumbers :: [(Integer, Integer)]
treeOfNumbers =
  [0..] >>= \ row ->
  let 
    inc = [0 .. row]
    dec = reverse inc
  in
  zip dec inc

type Quant = (Integer -> Bool) -> [Integer] -> Bool

check :: Quant -> (Integer, Integer) -> Bool
check q (m,n) =
  q (\ d -> d - m > 0) [1 .. domN]
  where
    domN = m + n

genTree :: Quant -> [(Integer, Integer)]
genTree q =
  filter (check q) treeOfNumbers

例如,take 10 $ genTree allis 的值

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9)]

但是,此代码似乎会导致内存泄漏.随着ghci的堆限制在100M,genTree all被打断了(0,1600).限制在500M,(0,3950)在变得非常慢之后停止.

如何改进？我对Haskell的经验有限,只能猜测我的实现可能treeOfNumbers是罪魁祸首; check适用于大值而没有任何问题.

---

¹参见Compatational Semantics with Functional Programming(Jan van Eijck and Christina Unger),Cambridge University Press,2010,pp.157-159.

Answer 1

这里没有内存泄漏.您明确告诉它通过将其定义为顶级常量来保留整个元组列表.懒惰意味着它在需要之前不会生成值,但这对保留值没有帮助.treeOfNumbers垃圾收集器可以证明它永远不会被再次使用之前不会被垃圾收集.一些粗略的数学表明,(0,1600)到列表中出现时,它将保持大约1,280,000个元组.这会占用大量的内存.