3 
 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我会收到消息“Stake space overflow: current size ... use +RTS -Ksize -RTS to increase ...”。但是当我删除 main 函数中的 if 时，程序可以正常工作。此外，如果我在 ghci 中给出命令Data.Vector.last d ，则计算出的值没有问题。那么为什么要打印此消息？当我将堆栈大小增加到 20M 时，程序可以毫无问题地播放。test1 是可执行文件的名称。

谢谢。

4

1 回答 1

9

问题是您的代码在构建d. 请记住，这Data.Vector.Vector是一个装箱向量类型 - 也就是说，它在内部表示为指向堆对象的指针数组（它们是值或未评估的thunk）。因此，当您填充d时generate，您实际上是在创建一个 thunk 向量。在您的示例中，当n访问 position 处的 thunk 时，它会触发对位置n-1和处的 thunk 的评估n-2，这反过来又会触发对 thunk n-3、n-4等的评估n-5。因此，评估最后一个元素会导致评估先前的1000000 - 1元素，从而导致堆栈增长。这就是为什么您会收到堆栈溢出错误。

在不修改代码的情况下解决此问题的一种简单方法是在访问最后一个元素之前完全评估整个向量。在这种情况下，所有 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]

或者，您可以使用未装箱的向量（Ints 的平面数组）：

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
于 2013-04-13T20:25:21.730 回答