为什么这个在 Haskell 中生成素数的想法似乎不起作用？

Question

我正在尝试使用 Haskell 中的 Eratosthenes 筛法来生成素数流，但代码似乎不起作用。这就是主要思想。

主要思想源自我们的函数式编程讲座，该讲座又参考了 Melissa O’Neil 的论文“The Genuine Sieve of Eratosthenes”，JFC，2009，该论文讨论了 Haskell 中的埃拉托斯特尼筛到底是什么。

union :: Ord a => [a] -> [a] -> [a]
union xs@(x:txs) ys@(y:tys)
    | x < y = x:union txs ys
    | x > y = y:union xs tys
    -- se sono uguali, ne scrivo uno solo
    | otherwise = x:union txs tys

minus :: Ord a => [a] -> [a] -> [a]
minus xs@(x:txs) ys@(y:tys)
    | x < y = x : minus txs ys
    | x > y = y : minus xs tys
    | otherwise = x : minus xs ys    

unionP :: Ord a => [a] -> [a] -> [a]
unionP (x:xs) ys = x:union xs ys -- poi si va con union

unionAll :: [[Integer]] -> [Integer]
unionAll = foldr1 unionP

primes :: [Integer]
primes = 2:[3..] `minus` composites 
    where composites = unionAll [map (p*) [p..] | p <-primes]

-- Test
firstPrimes = take 15 primes    

这就是实际发生的事情，并没有超出这个范围：

ghci> firstPrimes [2

所以我不得不中断这个过程：

ghci> firstPrimes [2^CInterrupted. 
ghci>

Answer 1

首先，您对

minus

的实现是错误的。奥尼尔的论文用途：

(x:xs) `minus` (y:ys) | x < y = x:(xs `minus` (y:ys))
                      | x == y = xs `minus` ys
                      | x > y = (x:xs) `minus` ys

转换为您的符号，它应该如下所示：

minus :: Ord a => [a] -> [a] -> [a]
minus xs@(x:txs) ys@(y:tys)
    | x < y = x : minus txs ys
    | x > y = minus xs tys
    | otherwise = minus txs ys

其次，奥尼尔论文中

union

的定义使用的是

foldr

而不是

foldr1

，所以相当于：

unionAll = foldr unionP []

而不是：

unionAll = foldr1 unionP

这可能看起来没什么大不了的，但这些函数的简单定义如下所示：

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

foldr1 f [x]    = [x]
foldr1 f (x:xs) = f x (foldr1 f xs)

看看，对于

foldr1

，

[x]

的情况如何出现在

(x:xs)

的情况之前？对于无限输入列表，情况

[x]

永远不会发生，但 Haskell 在处理情况 [x] 之前仍然

检查

情况

(x:xs)

。这使得

foldr1

比

foldr

稍微不那么懒惰。

例如：

λ> head $ foldr unionP [] ([1]:undefined)
1
λ> head $ foldr1 unionP ([1]:undefined)
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  undefined, called at <interactive>:86:27 in interactive:Ghci4

在您的

composites

调用中，在无限列表列表上调用

unionAll

：

bigList = [map (p*) [p..] | p <- primes]

由于

foldr1

的定义方式，Haskell实际上无法从

unionAll bigList

返回第一个元素，直到它检查到

bigList

有多个元素，但这需要确保列表中有第二个元素:

primes = 2 : ([3..] `minus` composites)

这需要检查以下列表是否非空：

[3..] `minus` composites

这需要确保

composites

以大于

3

的数字开头，但是 that 需要评估：

unionAll bigList

这就是整个计算的开始，你会得到一个无限循环。

无论如何，解决此问题所需要做的就是更换：

unionAll = foldr1 unionP

稍微懒一点的：

unionAll = foldr unionP []

它应该可以工作。

这是代码的完整工作版本，其中包含对

minus

和

unionAll

的更正，可以生成素数而不会卡住：

union :: Ord a => [a] -> [a] -> [a]
union xs@(x:txs) ys@(y:tys)
    | x < y = x:union txs ys
    | x > y = y:union xs tys
    | otherwise = x:union txs tys

minus :: Ord a => [a] -> [a] -> [a]
minus xs@(x:txs) ys@(y:tys)
    | x < y = x : minus txs ys
    | x > y = minus xs tys
    | otherwise = minus txs ys

unionP :: Ord a => [a] -> [a] -> [a]
unionP (x:xs) ys = x:union xs ys -- poi si va con union

unionAll :: [[Integer]] -> [Integer]
unionAll = foldr unionP []

primes :: [Integer]
primes = 2:[3..] `minus` composites
    where composites = unionAll [map (p*) [p..] | p <- primes]

-- Test
firstPrimes = take 15 primes