Сито застревает в начале

Question

Я написал следующее сито:

isPrime :: Integer -> [Integer] -> Bool
isPrime n = all (\i -> n `mod` i /= 0)


sieve :: [Integer]
sieve = 2 : [i | i <- [3,5..], isPrime i sieve]

но я не понимаю, почему он застревает после первого значения. Бег take 10 sieve результаты в [2, и ничего не происходит Вероятно, это как-то связано с бесконечной рекурсией. Пусть проблема в том, что sieve растет и в то же время используется внутри isPrime? По этой причине я также попытался изменить isPrime следующим образом, но безуспешно:

isPrime :: Integer -> [Integer] -> Bool
isPrime n = all (\i -> n `mod` i /= 0) . takeWhile (<n)

РЕДАКТИРОВАТЬ: Удивительно, что модификация @Jubobs работает:

isPrime :: Integer -> [Integer] -> Bool
isPrime n = all (\i -> n `mod` i /= 0) . takeWhile (\p -> p^2 <= n)

Я не могу понять, почему эта версия takeWhile работает, а другой нет. Я вижу, что с моей предыдущей версией я тестировал много ненужных делителей, но тем не менее их было конечное число.

---

Код должен быть в основном эквивалентен следующему коду Python:

def is_prime(n, ps):
    for i in ps:
        if n % i == 0: return False
    return True


def sieve():
    yield 2
    n = 3
    ps = [2]
    while True:
        if is_prime(n, ps):
            yield n
            ps.append(n)
        n += 2

Answer 1

Вы вызываете бесконечную рекурсию, применяя all на весь sieve а не только ценности, которые вы до сих пор просеивали. Т.е. для второго элемента isPrime проверяет все значения в sieve вместо просто 2,

В своей версии Python вы написали

is_prime(n, ps)

который только тестирует n против всех чисел, просеянных до сих пор. Python-эквивалент того, что вы сделали в Haskell, в основном

is_prime(n, sieve())

Теперь, используя takeWhile (<n) не поможет, потому что это также требует расчета элементов сита. Представьте, что происходит для второго элемента sieve (должно быть 3): он проверяет все значения сита, для которых < 3 держит, но для того, чтобы проверить, что вам на самом деле нужно оценить элементы сита. Таким образом, у вас все еще есть бесконечная рекурсия.

Answer 2

Я бы сказал, что список понимания в сите не закончится, пока он не завершится, никогда. Чтобы использовать такой подход, sieve должна возвращать элементы один за другим. Например, [1..] шоу 1, 2 ,3 ,4... до бесконечности, но ваше сито показывает только [2,

Или явно не то, что я сказал