Как Haskell оценивает эту функцию простых чисел?

Question

Мне довольно трудно понять, как Haskell оценит эту primes функцию.Функция primes оценивается снова и снова, или primes в функции primeFactors будет указывать на первое значение primes?

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

main :: IO ()
main = print $ length . take 100000 $ primes

Answer 1

как Haskell оценит эту функцию простых чисел?

Поскольку ваш код показывается в вопросе, он выводит первые 100000 простых чисел, так как же primes работать?

Во-первых, для генерации первого простого числа это просто, просто первый элемент списка:

2 : filter ((==1) ...

, то есть 2, а для следующего нам нужно применить primeFactorsфункционирует как

primeFactors 3 = factor 3 primes

и теперь может сбить с толку тех, кто плохо знаком с Haskell, как оценить primes в приведенном выше выражении?Ответ в том, что это просто список с элементами как [2,...], благодаря ленивой оценке, теперь нам не нужно оценивать все простые числа списка, сгенерированного функцией primes.нам просто нужно оценить следующий и посмотреть, что получится.Итак, мы получаем 2, и приведенное выше выражение становится:

 primeFactors 3 = factor 3 [2,..]

и

factor 3 (2:ps) | 2 * 2 > 3 = [3]

Итак, primeFactors 3 retrun [3]

и,так что

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

теперь мы успешно сгенерировали 2 простых числа, но нам нужно 100000, а как насчет следующего?Очевидно, мы применяем 5 к приведенному ниже выражению:

2: filter ((==1) . length . primeFactors) 5

повторяет процедуру, как указано выше:

primeFactors 5 = factor 5 [2,3,..]

и на этот раз у нас есть 2 элемента в списке:

factor 5 [2,3..]

и

factor 5 [2,3..] | otherwise = factor 5 [3,...]

и

factor 5 [3,...] | 3 * 3 > 5 = [5]

и повторяем снова и снова до генерации 100000 простых чисел, и снова, из-за ленивых вычислений, нам не нужно100001 простое число, поэтому вычисление останавливается и выводится результат.

Answer 2

primes это просто список.Его первый элемент равен 2, а остальные элементы взяты из списка нечетных целых чисел, отфильтрованных (частично) функцией primeFactors.

primeFactors, однако, использует primes.Разве это не циркуляр?

Не совсем.Поскольку Haskell ленив, primeFactors не нужны все значения в primes сразу, только те, которые меньше или равны квадратному корню его аргумента (p:ps соответствует primes, но мынужен только ps, если p*p <= n), и все эти простые числа были найдены предыдущими вызовами primeFactors.

В качестве примера проследите первые несколько вызовов primeFactors.Для краткости, пусть b = (==1) . length . primeFactors.

primeFactors 3 == factor 3 primes
               -- only unpack as much of primes as we need for the next step
               == factor 3 (2:filter b [3,5..])
               -- because 2*2 > 3, that's only one level
               == [3]

И так, поскольку b [3] истинно, мы знаем, что 3 является следующим элементом primes.То есть primes = 2:3:filter b [5,7..]

primeFactors 5 == factor 5 primes
               == factor 5 (2:3:filter b [3,5..])
               -- 2*2 > 5 is false, as is 5 `mod` 2 == 0, so
               == factor 5 (3:filter b [3,5..])
               -- 3*3 > 5, so
               == [5]

И b [5] - это истина, поэтому 5 является следующим элементом primes.

primeFactors 7 == factor 7 primes
               == factor 7 (2:3:5:filter b [3,5..])
               == factor 7 (3:5:filter b [3,5..])
               -- 3*3 > 7
               == [7]

И b [7] - это истинапоэтому 7 является следующим элементом primes.(Похоже, что все добавляется к primes, не так ли? Еще один вызов primeFactors покажет, что это не так) *

primeFactors 9 == factor 9 primes
               == factor 9 (2:3:5:7:filter b [3,5..])
               -- 2*2 > 9 and 9 `mod` 2 == 0 are false
               == factor 9 (3:5:7:filter b [3,5..])
               -- 3*3 > 9 is false, but 9 `mod` 3 == 0 is true, so
               == 3 : factor (9 `div` 3) (3:5:7:filter b [3,5..])
               == 3 : factor 3 (3:5:7:filter b [3,5..])
               -- 3*3 > 3 is false, but 3 `mod` 3 == 0, so
               == 3 : [3] == [3,3]

Но поскольку b [3,3] ложно, 9 is not элемент primes.Так что теперь у нас есть

 primes = 2:3:5:7:filter b [3,5..])

Это долгий и утомительный процесс, чтобы отследить это, но вы должны почувствовать, что primes всегда остается "впереди" primeFactors;элементы primes, которые нужны primeFactors, всегда определялись предыдущими вызовами primeFactors.