Итак, давайте посмотрим, что init делает для конечного списка:
init [1] == []
init [1,2] == [1]
init [1,2,3] == [1,2]
ОК, так что это дает нам все, кроме последнего элемента списка.
Так что же такое init primes?Ну, prime без последнего элемента.Надеемся, что если мы правильно реализовали prime, у него не должно было бы иметь последний элемент (потому что существует бесконечно много простых чисел!), Но, что более важно, нам пока не нужно заботиться, потому что у нас нетв любом случае, полный список на данный момент - мы заботимся только о первой паре элементов, так что для нас это почти то же самое, что и сам prime.
Теперь, посмотрим наall: Что это делает?Ну, он берет список и предикат и говорит нам, если все элементы списка удовлетворяют предикату:
all (<5) [1..4] == True
all even [1..4] == False
он работает даже с бесконечными списками!
all (<5) [1..] == False
так чтоздесь происходит?Ну, вот в чем дело: он работает с бесконечными списками ... но только если мы можем реально оценить список до первого элемента списка, который нарушает предикат!Давайте посмотрим, верно ли это здесь:
all (\y -> (mod 5 y) > 0) (init prime)
, поэтому, чтобы выяснить, является ли 5 простым числом, нам нужно проверить, есть ли число в простом числе минус последний элемент простого числа, который делитЭто.Давайте посмотрим, сможем ли мы сделать это.
Теперь давайте посмотрим на определение простого числа, мы получим
all (\y -> (mod 5 y) > 0) (2:3:filter (\x -> all (\y -> (mod x y) > 0) (init prime)) [5..])
Итак, чтобы определить, является ли 5 простым числом, нам нужно только проверить,это:
- делится на 2 - это не так, давайте продолжим
- делится на 3 - все еще нет
- делится на ...?Что ж, мы находимся в процессе проверки, что такое 3-е простое число, поэтому мы еще не знаем ...
и в этом суть проблемы.С помощью этой логики, чтобы определить третье простое число, нужно знать третье простое число!Конечно, логично, что мы на самом деле не хотим вообще это проверять, скорее, нам нужно только проверить, являются ли какие-либо из меньших простых чисел делителями текущего кандидата.
Так как же нам поступить так?Ну, к сожалению, нам придется изменить нашу логику.Одна вещь, которую мы можем сделать, это попытаться вспомнить, сколько простых чисел у нас уже есть, и взять для сравнения только столько, сколько нам нужно:
prime = 2 : 3 : morePrimes 2 [5..]
morePrimes n (x:xs)
| all (\y -> mod x y > 0) (take n prime) = x : morePrimes (n+1) xs
| otherwise = morePrimes n xs
Так как же это работает?Что ж, это в основном то, о чем мы только что говорили: мы помним, сколько простых чисел у нас уже есть (начиная с 2, потому что мы знаем, что у нас есть по крайней мере [2,3] в n. Затем мы проверяем, делится ли наше следующее простое числос помощью любого из n простых чисел, которые мы уже знаем с помощью take n, и, если это так, мы знаем, что это наше следующее простое число, и нам нужно увеличить n - в противном случае мы просто продолжаем.
Естьтакже более известная форма, вдохновленная (хотя и не совсем такой, как) Ситом Эратосфена:
prime = sieve [2..] where
sieve (p:xs) = p : sieve (filter (\x -> mod x p > 0) xs)
, так как это работает? Ну, опять же, с похожей идеей: мы знаем, что следующее простое числочисло должно быть не делимым на любое предыдущее простое число. Итак, что нам делать? Итак, начиная с 2, мы знаем, что первый элемент в списке является простым числом. Затем мы отбрасываем каждое число, делимое на это простое число.число с использованием filter. И после этого следующий элемент в списке снова будет простым числом (потому что мы его не выбросили), поэтому мы можем повторить процесс.
Ни один из этих лайнеров не похож на тот, на который вы надеялись.