haskell - 在Haskell-质数序列中表示递归

我需要表达质数的序列。 （在Euler项目中与前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中不起作用？

最佳答案

罪魁祸首是这个定义：

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的head元素（main要打印的20个元素中的第一个）会导致takeWhile需要检查prime_sequence的head元素。这导致takeWhile调用需要检查prime_sequence的head元素。这样，一次又一次。

那是黑洞，马上。 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`)

现在应该可以了。