Hanging self referencing list in Haskell to compute primes list-CodePudding

I recently started learning Haskell. To train a bit I wanted to try generating the list of prime numbers via self reference using the following code:

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]

But for some reason referencing primes inside of primes hangs when running runhaskell and is detected as a loop error when running the compiled binary with ghc.

However I don't really understand why.

CodePudding user response：

Clearly, the first two elements of primes are 2 and 3. What comes after that? The next element of primes is the first element of

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

What's that? It could be 5, if is_prime 5 primes, or it could be some larger number. To find out which, we need to evaluate

smaller_than_sqrt_list 5 primes

Which requires

takeWhile (<= isqrt 5) primes

Which requires

takeWhile (<= 3) primes

Well, that's easy enough, it starts with 2:3:..., right? Okay, but what's the next element? We need to look at the third element of primes and see whether it's less or equal to 3. But the third element of primes is what we were trying to calculate to begin with!

CodePudding user response：

The problem is that smaller_than_sqrt 5 3 is still True. To compute whether 5 is a prime, the is_prime 5 primes expands to all (not_divides 5) (takeWhile (smaller_than_sqrt 5) primes), and takeWhile will attempt to iterate primes until the predicate no longer holds. It does hold for the first element (2), it still does hold for the second element (3), will it hold for the next element - wait what's the next element? We're still computing which one that is!

It should be sufficient to use floor instead of ceiling in isqrt, or simpler just

smaller_than_sqrt p x = x * x <= p