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

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

直到我知道我應該在使用強大的遞歸時應該防止「空間溢出」時，我對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爲簡單起見

來源

2009-08-18 pierrotlefou

這是很難用任何功能的語言。作爲一個聰明的傢伙，我知道曾經說每個抽象都是漏洞。函數式語言非常適合表達自己，並展示算法將正確完成，但他們都必須假設它們具有無限的記憶。歡迎來到適合你的美麗程序到真正的電腦世界... – Spence 2009-08-18 07:32:37

由於皮爾答覆，你應該使用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

來源

2009-08-18 09:31:08 yairchu

更換

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）？

來源

2009-08-18 07:27:31 pierrotlefou

看到這篇文章：http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 – fishlips 2009-08-18 07:32:36

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

回答

相關問題