haskell - 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

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

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