Learning Haskell: Seemingly Circular Program - Please help explain

По порядку:

Лень - это свойство оценивать выражения только так, как вам нужно, а не тогда, когда вы могли бы. Ленивый список может быть бесконечным. Очевидно, попытка оценить бесконечный список была бы плохой идеей, если бы оценка не была ленивой.

Я не уверен, что означает «непорочный», но я думаю, вы обнаружите, что значение «2» в качестве известного простого числа обеспечивает базовый случай для рекурсии, т. Е. предоставляет конкретный ввод, после которого программа будет завершена. Написание рекурсивной функции (или действительно набора взаимно рекурсивных функций) обычно включает уменьшение некоторого входного значения до этого базового случая на последовательных этапах приложения.

Для справки, программные фрагменты этой формы обычно называют взаимно рекурсивными . Термин «круговая ссылка» в данном случае не подходит.

Прежде всего следует отметить, что сам по себе этот код ничего не делает. Это просто набор математических выражений, и не имеет значения, насколько они круглые, пока мы не попытаемся извлечь из них какие-то значения. Как нам это сделать?

Мы могли бы сделать:

print $ take 1 primes1

Здесь нет проблем. Мы можем взять первое значение primes1, не глядя на какой-либо рекурсивный код, здесь явно указано значение 2. А как насчет:

print $ take 3 primes1

Давайте попробуем раскрыть primes1 , чтобы получить некоторые значения. Чтобы сохранить эти управляемые выражения, теперь я игнорирую print и берут части, но помните, что мы делаем эту работу только из-за них. primes1 is:

primes1 = 2 : filter prime [3..]

У нас есть первое значение, и первым шагом к нашему второму является расширяющийся фильтр. Если бы это был строгий язык, мы бы попытались сначала расширить [3 ..] и получить застрявший. Возможное определение фильтра:

filter f (x:xs) = if f x then x : filter f xs else filter f xs

, что дает:

primes1 = 2 : if prime 3 then 3 : filter prime [4..] else filter prime [4..]

Наш следующий шаг должен выяснить, является ли простое число 3 истинным или ложным, поэтому давайте расширьте его, используя наши определения prime , ldp и ldpf .

primes1 = 2 : if ldp 3 == 3 then 3 : filter prime [4..] else filter prime [4..]
primes1 = 2 : if ldpf primes1 3 == 3 then 3 : filter prime [4..] else filter prime [4..]

Теперь все становится интересно: primes1 ссылается на себя, а ldpf требуется первое значение сделать его расчет. К счастью, мы можем легко получить первое значение.

primes1 = 2 : if ldpf (2 : tail primes) 3 == 3 then 3 : filter prime [4..] else filter prime [4..]

Теперь мы применяем защитные предложения в ldpf и находим 2 ^ 2> 3 , поэтому ldpf (2: хвостовые простые числа) 3 = 3 .

primes1 = 2 : if 3 == 3 then 3 : filter prime [4..] else filter prime [4..]
primes1 = 2 : 3 : filter prime [4..] 

Теперь у нас есть второе значение. Обратите внимание, что правая часть нашей оценки никогда не становилась особенно большой. и что нам никогда не нужно было слишком далеко следовать за рекурсивным циклом.

primes1 = 2 : 3 : if prime 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : if ldp 4 == 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : if ldpf primes1 4 == 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : if ldpf (2 : tail primes1) 4 == 4 then 4 : filter prime [5..] else filter prime [5..]

Мы используем защитное предложение rem 4 2 == 0 , поэтому здесь мы получаем 2.

primes1 = 2 : 3 : if 2 == 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : filter prime [5..]
primes1 = 2 : 3 : if prime 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldp 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldpf primes1 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldpf (2 : tail primes) 5 == 5 then 5 : filter prime [6..] else filter prime [6..]

Нет защитных совпадений, поэтому мы выполняем рекурсию:

primes1 = 2 : 3 : if ldpf (tail primes) 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldpf (3 : tail (tail primes)) 5 == 5 then 5 : filter prime [6..] else filter prime [6..]

Теперь 3 ^ 2> 5 , так что выражение равно 5.

primes1 = 2 : 3 : if 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : 5 : filter prime [6..]

Нам нужны только три значения, поэтому вычисление можно остановить.

Итак, теперь отвечу на ваши вопросы. Ленивый список требует от нас только оценки того, что нам нужно, и 2 помогает, потому что это гарантирует, что, когда мы достигнем рекурсивного шага, у нас всегда будет достаточно значений рассчитано. (Представьте, что расширение этого выражения, если бы мы не знали 2, мы бы застряли в цикле. быстро.)

Одной из определяющих особенностей Haskell является его лень. Списки - это только часть этой истории. По сути, Haskell никогда не выполняет ни одного вычисления, пока:

1. значение вычисления не потребуется для вычисления чего-то другого, что потребуется для...
2. Вы сказали Хаскелю вычислить что-то раньше, чем он мог бы в противном случае.

Так функция primes1 выдает список значений Integer, но она выдает не больше, чем необходимо для общего вычисления. Даже в этом случае, если бы вы определили ее таким образом:

primes1 :: [Integer]
primes1 = filter prime [2..]

у вас возникла бы проблема. primes1 попытается выдать первое значение в своей последовательности, (косвенно) оценивая prime 2, который оценит ldp 2, который запросит первое значение, полученное primes1... престо бесконечный цикл!

Непосредственно возвращая 2 как первое значение последовательности, порожденной primes1, вы избегаете бесконечного цикла. Для каждого последующего значения в последовательности, primes1 уже сгенерировал предыдущее значение, которое будет оценено ldp как часть вычисления последующего значения.