haskell - 为什么我在 Haskell 中收到堆栈溢出消息？

Question

 import Data.Vector hiding((++))
 import System.Environment 
 d = generate 1000000 (\z->case z of
                      0 -> 2
                      1 -> 3
                      2 -> 5
                      otherwise -> if odd z then (d ! (z-1)) +2 else (d ! (z-1)) + 4)
 algorithmA _ _  1 pt  = pt
 algorithmA t k n pt = let dk = d ! k
                       q = div n dk
                       r = mod n dk
                      in if r /=0 then
                            if q>dk then
                              algorithmA t (k+1) n pt
                            else (n:pt)
                         else
                             algorithmA (t+1) k q (dk:pt)

main = do
        args<-getArgs
        let n = read (args !! 0)
        if (floor(sqrt(fromInteger n))) > Data.Vector.last d  then error ("The square  root of number is greater than " ++ show (Data.Vector.last d))
     else
         print (algorithmA 0 0 n [])

当我编译上述程序并在命令行中给出例如 test1 2222 时，我收到消息“权益空间溢出:当前大小...使用 +RTS -Ksize -RTS 来增加 . ..”。但是当我删除主函数中的 if 时，程序就可以正常运行。另外，如果我在 ghci 中输入命令 Data.Vector.last d ，则计算值不会出现问题。那么为什么会打印这条消息呢？当我将堆栈大小增加到 20M 时，程序运行没有问题。test1 是可执行文件的名称。

谢谢。

Answer 1

问题是你的代码在构造d时太懒了。请记住，Data.Vector.Vector 是一个装箱向量类型 - 也就是说，它在内部表示为指向堆对象的指针数组(这些对象可以是值，也可以是未计算的 thunks )。因此，当您使用 generate 填充 d 时，您实际上是在创建一个 thunk 向量。在您的示例中，当访问位置 n 处的 thunk 时，它会触发对位置 n-1 和 n-2 处的 thunk 的求值，进而触发对 thunk n-3、n-4、n-5 等的求值。因此，计算最后一个元素会导致之前的 1000000 - 1 元素被计算，从而导致堆栈增长。这就是您收到堆栈溢出错误的原因。

无需修改代码即可解决此问题的简单方法 is to fully evaluate the whole vector before accessing the last element 。在这种情况下，所有 thunk 都会按顺序求值，并且不会出现堆栈溢出(因为一旦对 thunk 求值，它就会被它所表示的表达式的值替换，因此当您求值元素 n 时在已经评估了元素 n-1 和 n-2 后，只需访问这两个元素，并且不会触发所有先前 thunk 的级联评估):

import Control.DeepSeq (($!!))
...
let l = V.last $!! d
...

测试:

$ ghc -O2 Test.hs
[1 of 1] Compiling Main             ( Test.hs, Test.o )
Linking Test ...
$ ./Test 2222    
[101,11,2]

或者，您可以 use unboxed vectors(Int 的平面数组):

d :: U.Vector Int
d = U.create $ do
  v <- M.new dSize
  go 0 v
    where
      dSize = 1000000
      go i v | i >= dSize = return v
             | otherwise = do
               val <- case i of
                 0 -> return 2
                 1 -> return 3
                 2 -> return 5
                 _ -> if odd i
                      then (+2) <$> (M.read v (i-1))
                      else (+4) <$> (M.read v (i-1))
               M.write v i val
               go (i+1) v