如何解决"堆空间溢出"在haskell
-
18-09-2019 - |
题
运行以下程序将打印的"空间溢出:目前的大小8388608字节。" 我已经阅读 此 和 此, 但还是不知道如何解决我的问题。我使用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
为了简单
解决方案
作为pierr回答说,应当使用 foldl'
.更多的细节:
foldl'
计算出它的"左边"之前给你的折叠的步骤。foldr
给你的折叠的步骤"咚"右侧的价值。这种"咚",将计算出需要的时候。
让我们做一个总和 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'
:(签略在代码,因为这样并不显示它很好)
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
其他提示
替换
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相似)?
不隶属于 StackOverflow