Почему этот фрагмент кода на Haskell не является бесконечно рекурсивным?

Question

Чтобы помочь мне изучить Haskell, я работаю над проблемами в Project Euler.После решения каждой проблемы я проверяю свое решение на вики Haskell в попытке изучить лучшие практики кодирования.Вот решение до проблемы 3 :

primes = 2 : filter ((==1) . length . primeFactors) [3,5..]

primeFactors n = factor n primes
  where
    factor n (p:ps) 
        | p*p > n        = [n]
        | n `mod` p == 0 = p : factor (n `div` p) (p:ps)
        | otherwise      = factor n ps

problem_3 = last (primeFactors 317584931803)

Наивно это звучит так: primes определяется в терминах primeFactors, чтоопределяется в терминах primes.Таким образом, оценка primeFactors 9 будет следовать этому процессу:

1. Оценить factor 9 primes.
2. Запросить primes для его первого элемента, который равен 2.
3. Запроситьprimes для его следующего элемента.
4. В рамках этого процесса оцените primeFactors 3.
5. Запросите primes для его первого элемента, который равен 2.
6. Попросите у primes следующий элемент.
7. В рамках этого процесса оцените primeFactors 3.
8. ...

Другими словами, шаги 2-4 повторяется бесконечно.Ясно, что я ошибаюсь, поскольку алгоритм заканчивается.Какую ошибку я здесь делаю?

Answer 1

primeFactors только когда-либо читает до квадратного корня числа, которое он оценивает. Он никогда не смотрит дальше в списке, что означает, что он никогда не «догоняет» число, которое он тестирует для включения в список. Поскольку Haskell ленив, это означает, что тест primeFactors завершается.

Другая вещь, которую следует помнить, это то, что primes - это не функция, которая оценивает список при каждом обращении к нему, а список, который создается лениво. Таким образом, после того, как к 15-му элементу был получен доступ один раз, второй доступ к нему становится «бесплатным» (например, он не требует каких-либо дополнительных вычислений).

Answer 2

Ответ Кевина удовлетворительный, но позвольте мне указать на ошибку в вашей логике.Это # 6, что не так.Итак, мы оцениваем primeFactors 3:

primeFactors 3          ==>
factor 3 primes         ==>
factor 3 (2 : THUNK)    ==>
2*2 > 3 == True         ==>
[3]

Значение THUNK никогда не нужно оценивать, чтобы определить, что primeFactor 3 равно [3].

Answer 3

primeFactors 3 не запрашивает primes его следующий элемент, только первый, потому что 2*2 больше 3 уже