参数传递风格的Haskell堆问题

Question

这是一个简单的程序,将我的堆炸到了王国来:

intersect n k z s rs c
  | c == 23   = rs
  | x == y    = intersect (n+1) (k+1) (z+1) (z+s) (f : rs) (c+1)
  | x < y     = intersect (n+1) k (z+1) s rs c
  | otherwise = intersect n (k+1) z s rs c
    where x = (2*n*n) + 4 * n
          y = (k * k + k )
          f = (z, (x `div` 2), (z+s))
p = intersect 1 1 1 0 [] 0

main = do
  putStr (show p)

程序所做的是计算两个无限级数,当它达到23个元素时停止.但这对我来说并不重要.

有趣的是,就我所知,这里应该没有太多东西可以坐在堆上.函数intersect是递归的,所有递归都写为尾调用.国家在争论中积累,而且没有多少.5个整数和一个小元组列表.

如果我是一个投注者,我敢打赌,在我进行递归时,不知何时thunk正在参数中构建,特别是在给定递归上未评估的参数上.但这只是一种疯狂的预感.

这里真正的问题是什么？如何修复它？

Answer 1

如果堆有问题,请运行堆分析器,如下所示:

$ ghc -O2 --make A.hs -prof -auto-all -rtsopts -fforce-recomp
[1 of 1] Compiling Main             ( A.hs, A.o )
Linking A.exe ...

运行时哪个:

$ ./A.exe +RTS -M1G -hy

生成A.hp输出文件:

$ hp2ps -c A.hp

像这样:

所以你的堆已经满了Integer,这表明你的函数的累积参数存在一些问题 - 所有Integers都是.

修改函数,使其在惰性Integer参数中是严格的(基于你从不检查它们的值的事实),如下所示:

{-# LANGUAGE BangPatterns #-}

intersect n k !z !s rs c
  | c == 23   = rs
  | x == y    = intersect (n+1) (k+1) (z+1) (z+s) (f : rs) (c+1)
  | x < y     = intersect (n+1) k (z+1) s rs c
  | otherwise = intersect n (k+1) z s rs c
    where x = (2*n*n) + 4 * n
          y = (k * k + k )
          f = (z, (x `div` 2), (z+s))

p = intersect 1 1 1 0 [] 0

main = do
  putStr (show p)

并且您的程序现在使用您正在生成的参数列表在常量空间中运行(但不会c == 23在任何合理的时间内终止).

Answer 2

如果可以使结果列表反转,则可以利用Haskell的懒惰并在计算时返回列表,而不是递归地将其作为累积参数传递.这不仅可以让您在计算列表时使用和打印列表(从而消除了那里的一个空间泄漏),您还可以分解出您想要的元素数量的决定intersect:

{-# LANGUAGE BangPatterns #-}

intersect n k !z s
  | x == y    = f : intersect (n+1) (k+1) (z+1) (z+s)
  | x < y     = intersect (n+1) k (z+1) s
  | otherwise = intersect n (k+1) z s
    where x = (2*n*n) + 4 * n
          y = (k * k + k )
          f = (z, (x `div` 2), (z+s))
p = intersect 1 1 1 0

main = do
  putStrLn (unlines (map show (take 23 p)))

正如唐所指出的那样,我们需要小心谨慎,以便积累论据及时评估,而不是积累大块.通过使参数z严格,我们确保要求所有参数.

通过每行输出一个元素,我们可以观察生成的结果:

$ ghc -O2 intersect.hs && ./intersect
[1 of 1] Compiling Main             ( intersect.hs, intersect.o )
Linking intersect ...
(1,3,1)
(3,15,4)
(10,120,14)
(22,528,36)
(63,4095,99)
(133,17955,232)
(372,139128,604)
(780,609960,1384)
...