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

Question

Мне довольно сложно понять, как Хаскелл оценит это 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

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

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

Не совсем. Потому что Хаскелл ленив, 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 не является элементом primes, Итак, теперь у нас есть

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

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

Answer 2

как 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, поэтому вычисление останавливается и выводится результат.