haskell - 在 Haskell 中表达递归 - 素数序列

Question

我需要表达素数序列。 (在欧拉项目中与 ex 3 作斗争)。

我碰巧遇到了这个递归定义:

is_not_dividable_by :: (Integral a) => a -> a -> Bool
is_not_dividable_by x y = x `rem` y /= 0

accumulate_and :: (Integral a) => [a] -> (a -> Bool) -> Bool
accumulate_and (x:xs) (f) = (accumulate_and xs (f)) && f(x)
accumulate_and [] f = True

integers = [2,3..]

prime_sequence = [n | n <- integers, is_prime n]
                where is_prime n = accumulate_and 
                                        (takeWhile (<n) (prime_sequence)) 
                                        ( n `is_not_dividable_by`)

result = take 20 prime_sequence
str_result = show result
main = putStrLn str_result

虽然编译得很好，但是执行时却陷入了循环，只返回 <<loop>>

我的问题是我认为我可以在 Haskell 中自由表达递归定义。但显然这个定义根本不符合该语言。

但是，当我在心里尝试解决prime_sequence时，我认为我成功了并增长了序列，但当然是使用命令式编程先验。

我的递归定义中有什么明显的错误，导致这段代码在 Haskell 中无法工作？

Answer 1

罪魁祸首是这个定义:

prime_sequence = [n | n <- [2,3..], is_prime n]  where 
  is_prime n = accumulate_and 
                 (takeWhile (< n) (prime_sequence)) 
                 ( n `is_not_dividable_by`)

尝试查找 prime_sequence 的头元素(main 打印的 20 个元素中的第一个)会导致 takeWhile 需要检查 prime_sequence 的 head 元素。这导致 takeWhile 调用需要检查 prime_sequence 的头元素。如此，一次又一次。

这就是黑洞，马上。 takeWhile 甚至无法开始沿着它的输入行走，因为那里什么也没有。

通过启动序列可以很容易地解决这个问题:

prime_sequence = 2 : [n | n <- [3,4..], is_prime n]  where 
  is_prime n = accumulate_and 
                 (takeWhile (< n) (prime_sequence)) 
                 ( n `is_not_dividable_by`)

现在它开始工作，并遇到了第二个问题，如 Rufflewind's answer 中所述。 : takeWhile 无法停止沿着其输入行走。最简单的修复方法是停在 n/2 处。但最好停在 sqrt 处:

prime_sequence = 2 : [n | n <- [3,4..], is_prime n]  where 
  is_prime n = accumulate_and 
                 (takeWhile ((<= n).(^ 2)) (prime_sequence)) 
                 ( n `is_not_dividable_by`)

现在应该可以工作了。