我最近开始学习Haskell。为了训练一点,我想尝试使用下面的代码通过自引用生成素数列表:
main = do
print (smaller_than_sqrt 4 2)
print (smaller_than_sqrt_list 5 [2..])
print ("5")
print (is_prime 5 [2..])
print ("7")
print (is_prime 7 [2..])
print ("9")
print (is_prime 9 [2..])
print ("test")
print (take 5 primes) -- Hangs
-- Integer square root
isqrt :: Int -> Int
isqrt = ceiling . sqrt . fromIntegral
-- Checks if x is smaller than sqrt(p)
smaller_than_sqrt :: Int -> Int -> Bool
smaller_than_sqrt p x = x <= isqrt p
-- Checks if x doesn't divide p
not_divides :: Int -> Int -> Bool
not_divides p x = p `mod` x /= 0
-- Takes in a number and an ordered list of numbers and only keeps the one smaller than sqrt(p)
smaller_than_sqrt_list :: Int -> [Int] -> [Int]
smaller_than_sqrt_list p xs = takeWhile (smaller_than_sqrt p) xs
-- Checks if p is prime by looking at the provided list of numbers and checking that none divides p
is_prime :: Int -> [Int] -> Bool
is_prime p xs = all (not_divides p) (smaller_than_sqrt_list p xs)
-- Works fine: primes = 2 : [ p | p <- [3..], is_prime p [2..]]
-- Doesn't work:
primes = 2 : 3 : [ p | p <- [5..], is_prime p primes]
但由于某种原因,在primes
内引用primes
会在运行runhaskell
时挂起,并且在使用ghc
运行已编译的二进制文件时被检测为循环错误。
然而我真的不明白为什么。
2条答案
按热度按时间7z5jn7bk1#
很明显,
primes
的前两个元素是2和3。接下来是什么?primes
的下一个元素是它可能是5,如果是
is_prime 5 primes
,也可能是更大的数。要找出是哪个,我们需要计算这需要
这需要
很简单,它是从
2:3:...
开始的,对吗?好的,下一个元素是什么?我们需要看primes
的第三个元素,看看它是小于还是等于3。但是primes
的第三个元素是我们要开始计算的!62lalag42#
问题是
smaller_than_sqrt 5 3
仍然是True
。为了计算5
是否是素数,is_prime 5 primes
扩展为all (not_divides 5) (takeWhile (smaller_than_sqrt 5) primes)
,并且takeWhile
将尝试迭代primes
,直到 predicate 不再成立。它对第一个元素成立(2
),它仍然适用于第二个元素(3
),它是否适用于下一个元素--等等,下一个元素是什么?我们还在计算哪一个是!在
isqrt
中使用floor
而不是ceiling
就足够了,或者更简单,只需