項目歐拉23：洞悉這個stackoverflow-ing計劃需要

Question

嗨haskell研究員。我目前正在致力於Project Euler的23rd problem。我在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...增加堆棧內存限制不能解決問題。

編輯2：關於sqrt的事情，我只是從評論的鏈接粘貼它。爲了避免必須將Integer投出雙打併面對舍入問題等......

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中的尾遞歸通常不像其他語言中那樣是個好主意;守護遞歸（在遞歸之前至少生成一個構造函數，或者在生成構造函數之前遞歸少量次數）通常對於懶惰評估更好。事實上，在這裏，發生的事情是，對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只能評估足夠的數據，以瞭解列表是否匹配[]或_:_。下列情況不堆棧溢出：

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)) 

Answer 2

好，我裝上了它，並給了它一個鏡頭。 Daniel Wagner的建議非常好，可能比我的要好。問題確實與工作者功能有關，但我會建議使用Data.MemoCombinators來記憶你的功能。

此外，你的divisors算法是一種愚蠢的。有一個更好的方法來做到這一點。這有點麻煩，需要大量的TeX，所以這裏有一個關於如何做到這一點的math.stackexchange頁面的鏈接。我所說的那個是被接受的答案，儘管其他人提供了一個我認爲會運行得更快的遞歸解決方案。 （它不需要質數分解。）

https://math.stackexchange.com/questions/22721/is-there-a-formula-to-calculate-the-sum-of-all-proper-divisors-of-a-number

Answer 3

由於Daniel Wagner correctly said，問題是

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

構建了一個嚴重嵌套的thunk。通過利用worker這兩個參數在此應用程序中排序的事實，您可以避免這種情況並獲得比deepseq稍好的性能。因此，你可以注意到，在任何步驟都在prev小於2*a不能由兩個數目衆多的總和得到增量輸出，所以

worker (a:as) prev = small ++ worker as (large Set.\\ map (+ a) (a:as)) 
    where 
    (small,large) = span (< a+a) prev 

越辦越好。但是，它仍然不好，因爲(\\)無法使用這兩個列表的排序。如果您有

minus xxs@(x:xs) yys@(y:ys) 
    = case compare x y of 
     LT -> x : minus xs yys 
     EQ -> minus xs ys 
     GT -> minus xxs ys 
minus xs _ = xs    -- originally forgot the case for one empty list 

更換（或使用data-ordlist包的版本），計算設定不同的是O（長度），而不是O（長度^ 2）。