foldr 导致堆栈溢出

Question

我正在尝试在无限列表上使用埃拉托色尼筛算法生成素数。我听说 foldr 会懒惰地检查列表，但每次我尝试使用以下算法时，我都会遇到堆栈溢出异常：

getPrimes :: [Int]
getPrimes = foldr getNextPrime [2] [3,5..]
    where
        getNextPrime n primes
            | not $ isAnyDivisibleBy primes n = primes ++ [n]
            | otherwise = primes
        isAnyDivisibleBy primes n = any (\x -> isDivisibleBy n x) primes
        isDivisibleBy x y = x `mod` y == 0

示例：

takeWhile (\x -> x < 10) getPrimes
*** Exception: stack overflow

某个地方正在评估列表，但我不知道在哪里。

Answer 1

我认为 foldr 让你感到困惑，所以让我们用显式递归写出来：

getPrimes :: [Int]
getPrimes = getPrimesUsing [3,5..]

getPrimesUsing :: [Int]->[Int]
getPrimesUsing [] = [2]
getPrimesUsing (n:primes)
  | not $ isAnyDivisibleBy primes n = primes ++ [n]
  | otherwise = primes
  where
    primes = getPrimesUsing primes
    isAnyDivisibleBy primes n = any (\x -> isDivisibleBy n x) primes
    isDivisibleBy x y = x `mod` y == 0

你现在能看出问题所在吗？

一个不相关的点：您似乎要在此处实现的算法是不是埃拉托色尼筛法，而是一种效率低得多的算法，称为试验除法。

Answer 2

foldr getNextPrime [2] [3, 5 .. ] 扩展为：

(getNextPrime 3 (getNextPrime 5 (getNextPrime 7 ...

因为 getNextPrime 总是需要检查它的第二个参数，我们只得到一个不终止的 getNextPrime 调用链，并且从未使用初始的 [2] 列表。

Answer 3

foldr 定义为

foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

所以当你插入参数时你会得到

foldr getNextPrime [2] [3,5..]
    = getNextPrime 3 (foldr getNextPrime [2] [5,7..])
    = getNextPrime 3 (getNextPrime 5 (foldr getNextPrime [2] [7,9..])
    etc...

为了延迟生成值（处理无限列表时你想要的）然后 getNextPrime 需要延迟生成值。查看 getNextPrime、primes ++ [n] 的定义，这意味着您要将一个值附加到 primes 列表的末尾，但是 getNextPrime 3 的 primes 是 getNextPrime 5 (foldr getNextPrime [2] [7,9..])。但是 getNextPrime 5 的 primes 是 getNextPrime 7 (foldr getNextPrime [2] [9,11..])，等等。你实际上永远无法为 primes 生成一个正常形式的值，它总是一连串的计算，永远不会return.

另一种看待这个的方法是用运算符替换 getNextPrime，我们称它为 .:

foldr (.:) [2] [3,5..9]
    = 3 .: (5 .: (7 .: (9 .: [2])))

（这就是为什么它被称为右折叠，括号嵌套在右边）

这非常适合在 foldr 中使用 ::

foldr (:) [2] [3,5..9]
    = 3 : (5 : (7 : (9 : [2])

因为:只是构建了一个新的数据结构，可以检查这个数据结构的第一个元素而不用计算结构的其余部分。但是.:就不太好了，它需要先计算x1 = 9 .: [2]，然后是x2 = 7 .: x1，然后是x3 = 5 .: x2，最后是3 .: x3。相反，对于 [3,5..]，您永远无法计算 something .: [2] 的最后一次调用，但 haskell 一直尝试计算它，这会破坏堆栈。

foldr 导致堆栈溢出

foldr resulting in stack overflow

haskell

functional-programming