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

Чтобы помочь мне изучить 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 будет следовать этому процессу:

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

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

Ответы

Ответ 1

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

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

Ответ 2

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

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

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

Ответ 3

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