4

运行以下程序将打印“空间溢出：当前大小 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编辑：为简单起见删除定义

4

2 回答 2

11

正如 pierr 回答的那样，您应该使用foldl'. 更多细节：

  • foldl'在将其提供给您的折叠步骤之前计算其“左侧”。
  • foldr为您的折叠步骤提供右侧值的“重击”。这个“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-18T09:31:08.907 回答
4

代替

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-18T07:27:31.947 回答