我需要表达素数序列。 (在欧拉项目中与 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 中无法工作?
最佳答案
罪魁祸首是这个定义:
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`)
现在应该可以工作了。
关于haskell - 在 Haskell 中表达递归 - 素数序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25819312/