如何解決haskell中的「堆棧空間溢出」

Question

運行下面的程序會打印出「空間溢出：當前大小8388608字節」。我已閱讀this和this，但仍不知道如何解決我的問題。我正在使用foldr，它不應該保證是「尾遞歸」嗎？

直到我知道我應該在使用強大的遞歸時應該防止「空間溢出」時，我對Haskell感到非常滿意。 :)

module Main where 
import Data.List 

value a b = 
    let l = length $ takeWhile (isPrime) $ map (\n->n^2 + a * n + b) [0..] 
    in (l, a ,b) 

euler27 = let tuple_list = [value a b | a <-[-999..999] , b <- [-999..999]] 
     in foldr (\(n,a,b) (max,v) -> if n > max then (n , a * b) else (max ,v)) (0,0) tuple_list 
main = print euler27 

編輯：除去isPrime的definiton爲簡單起見

Answer 1

由於皮爾答覆，你應該使用foldl'。欲瞭解更多詳情：

• foldl'計算其「左側」，然後再將它給予您的摺疊步驟。
• foldr爲您的摺疊步驟提供右側值的「thunk」。這個「thunk」將在需要時計算。

讓我們做一個總和與foldr，看看它是如何評估：

foldr (+) 0 [1..3] 
1 + foldr (+) 0 [2..3] 
1 + 2 + foldr (+) 0 [3] 
1 + 2 + 3 + foldl (+) 0 [] -- this is a big thunk.. 
1 + 2 + 3 + 0 
1 + 2 + 3 
1 + 5 
6 

而且隨着foldl'：（標籤代碼省略，因爲SO不能很好地顯示出來）

foldl (+) 0 [1..3] 
-- seq is a "strictness hint". 
-- here it means that x is calculated before the foldl 
x `seq` foldl (+) x [2..3] where x = 0+1 
foldl (+) 1 [2..3] 
x `seq` foldl (+) x [3] where x = 1+2 
foldl (+) 3 [3] 
x `seq` foldl (+) x [] where x = 3+3 
foldl (+) 6 [] 
6 

用於foldr的良好用途，不泄漏。 「步驟」必須：

• 返回不依賴於「右側」，忽略它或包含它的懶惰結構
• 返回右側作爲是
結果好 foldr使用的

例子：

-- in map, the step returns the structure head 
-- without evaluating the "right-side" 
map f = foldr ((:) . f) [] 

filter f = 
    foldr step [] 
    where 
    step x rest = 
     | f x = x : rest -- returns structure head 
     | otherwise = rest -- returns right-side as is 

any f = 
    foldr step False 
    where 
    -- can use "step x rest = f x || rest". it is the same. 
    -- version below used for verbosity 
    step x rest 
     | f x = True -- ignore right-side 
     | otherwise = rest -- returns right-side as is 

Answer 2

更換

foldr (\(n,a,b) (max,v) -> if n > max then (n , a * b) else (max ,v)) (0,0) tuple_list 

與

foldl' (\(max ,v) (n,a,b) -> if n > max then (n , a * b) else (max ,v)) (0,0) tuple_list 

解決了這個問題，應該是建議我們應該總是喜歡使用foldl'而不是其他變體（foldl，foldr）？