haskell - 欧拉计划 23 : insight on this stackoverflow-ing program needed

Question

嗨 haskell伙计们。我目前正在处理 23rd problem的 Project Euler .我在 atm 的地方是我的代码对我来说似乎是正确的 - 不是“好算法”的意思，而是“应该工作”的意思 - 但会产生堆栈内存溢出。

我知道我的算法并不完美(特别是我当然可以避免在我的 worker 函数的每个递归步骤中计算如此大的中间结果)。

不过，在学习Haskell的过程中，我想了解为什么这段代码失败得如此惨，以免下次出现这种错误。

任何有关此程序错误原因的见解将不胜感激。

import qualified Data.List as Set ((\\))

main = print $ sum $ worker abundants [1..28123]

-- Limited list of abundant numbers
abundants :: [Int]
abundants = filter (\x -> (sum (divisors x)) - x > x) [1..28123]

-- Given a positive number, returns its divisors unordered.
divisors :: Int -> [Int]
divisors x  | x > 0     =   [1..squareRoot x] >>=
                            (\y ->  if      mod x y == 0
                                    then    let d = div x y in
                                            if y == d
                                            then [y]
                                            else [y, d]
                                    else    [])
            | otherwise = []


worker :: [Int] -> [Int] -> [Int]
worker (a:[]) prev = prev Set.\\ [a + a]
worker (a:as) prev = worker as (prev Set.\\ (map ((+) a) (a:as)))


-- http://www.haskell.org/haskellwiki/Generic_number_type#squareRoot
(^!) :: Num a => a -> Int -> a
(^!) x n = x^n

squareRoot :: Int -> Int
squareRoot 0 = 0
squareRoot 1 = 1
squareRoot n =
   let twopows = iterate (^!2) 2
       (lowerRoot, lowerN) =
          last $ takeWhile ((n>=) . snd) $ zip (1:twopows) twopows
       newtonStep x = div (x + div n x) 2
       iters = iterate newtonStep (squareRoot (div n lowerN) * lowerRoot)
       isRoot r  =  r^!2 <= n && n < (r+1)^!2
   in  head $ dropWhile (not . isRoot) iters

编辑:确切的错误是 Stack space overflow: current size 8388608 bytes. .通过 +RTS -K... 增加堆栈内存限制不能解决问题。

Edit2:关于 sqrt 的事情，我只是从评论中的链接复制粘贴它。为了避免不得不将整数转换为 double 并面临舍入问题等......

Answer 1

将来，尝试自己进行一些最小化是有礼貌的。例如，玩了一会儿，我发现下面的程序也会发生堆栈溢出(使用 8M 堆栈):

main = print (worker [1..1000] [1..1000])

......这真的确定了什么功能让你搞砸了。一起来看看 worker :

worker (a:[]) prev = prev Set.\\ [a + a]
worker (a:as) prev = worker as (prev Set.\\ (map ((+) a) (a:as)))

即使在我第一次阅读时，这个函数在我的脑海中也被标记为红色，因为它是尾递归的。 Haskell 中的尾递归通常不像其他语言那样是一个好主意。 protected 递归(在递归之前至少生成一个构造函数，或者在生成构造函数之前递归少量次)通常更适合惰性求值。事实上，这里发生的事情是每次递归调用 worker正在 prev 中构建一个越来越深的嵌套 thunk争论。到时候终于返回 prev ，我们必须深入到 Set.\\的长链中。呼吁找出我们最终拥有的东西。

这个问题被明显的严格性注释没有帮助的事实稍微混淆了。让我们按摩 worker直到它起作用。第一个观察结果是第一个子句完全被第二个子句包含。这是风格；它不应该影响行为(空列表除外)。

worker []     prev = prev
worker (a:as) prev = worker as (prev Set.\\ map (a+) (a:as))

现在，明显的严格性注释:

worker []     prev = prev
worker (a:as) prev = prev `seq` worker as (prev Set.\\ map (a+) (a:as))

我惊讶地发现这个堆栈仍然溢出!鬼鬼祟祟的是 seq on lists 仅评估足够远以了解列表是否匹配 []或 _:_ .以下不会堆栈溢出:

import Control.DeepSeq

worker []     prev = prev
worker (a:as) prev = prev `deepseq` worker as (prev Set.\\ map (a+) (a:as))

我没有将这个最终版本插入到原始代码中，但它至少适用于最小化的 main以上。顺便说一句，你可能会喜欢下面的实现思路，它也会堆栈溢出:

import Control.Monad

worker as bs = bs Set.\\ liftM2 (+) as as

但是可以使用 Data.Set 来修复而不是 Data.List ，并且没有严格性注释:

import Control.Monad
import Data.Set as Set

worker as bs = toList (fromList bs Set.\\ fromList (liftM2 (+) as as))