在Haskell中悬挂自引用列表以计算素数列表

mwg9r5ms  于 2022-11-14  发布在  其他
关注(0)|答案(2)|浏览(154)

我最近开始学习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运行已编译的二进制文件时被检测为循环错误。
然而我真的不明白为什么。

7z5jn7bk

7z5jn7bk1#

很明显,primes的前两个元素是2和3。接下来是什么?primes的下一个元素是

[p | p <- [5..], is_prime p primes]

它可能是5,如果是is_prime 5 primes,也可能是更大的数。要找出是哪个,我们需要计算

smaller_than_sqrt_list 5 primes

这需要

takeWhile (<= isqrt 5) primes

这需要

takeWhile (<= 3) primes

很简单,它是从2:3:...开始的,对吗?好的,下一个元素是什么?我们需要看primes的第三个元素,看看它是小于还是等于3。但是primes的第三个元素是我们要开始计算的!

62lalag4

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就足够了,或者更简单,只需

smaller_than_sqrt p x = x * x <= p

相关问题