Хаскелл, понимая решение для эйлера № 3

Недавно я научился изучать хакелл и очень хорошо провел время. Я работал над некоторыми проблемами Project Euler, чтобы получить синтаксис и рассмотрел решения, размещенные здесь http://www.haskell.org/haskellwiki/Euler_problems/1_to_10 в качестве инструмент обучения. Хотя я обнаружил, что не могу окунуться в решение, отправленное для проблема № 3:

-- Find the largest prime factor of 317584931803. 

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, кажется, звонят друг другу, чтобы создавать свои собственные списки, и попытка следовать за ним разжигает мой мозг. Кто-нибудь знает хорошее сообщение в блоге об этом решении или хочет написать здесь объяснение?

Ответ 1

Это действительно озадачивает с первого взгляда. Но это не волшебство, если вы не думаете "императивно". Определения Haskell - это просто: расскажите, что что-то есть, а не какие операции нижнего уровня, которые должен выполнить компьютер.

Следовательно, список простых чисел - это список, содержащий 2 и все нечетные натуральные числа, большие 2, которые имеют только один простой множитель (а именно сам).

Список простых коэффициентов для некоторого целого числа n, с другой стороны, представляет собой список простых чисел, которые делят n.

Убедитесь, что вы поняли эти определения, прежде чем читать.

В качестве абстрактного Haskell может быть, он по-прежнему является языком программирования, поэтому нам нужно время от времени давать советы, как вычислить что-то. В частности, в приведенном выше примере мы не тестируем все простые числа, чтобы найти простые множители n, так как достаточно проверить 2..k где k*k <= n. Это также гарантирует, что мы будем использовать только ту часть расчёта, которая уже вычислена.

В начале primes выглядит следующим образом:

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

Если мы требуем следующий элемент после 2, мы вынуждаем оценку выражения right двоеточия. Это, в свою очередь, заставляет фильтр оценивать предикат для 3. Затем он идет:

primeFactors 3
  factor 3 (2 : ...)
    2*2 > 3
  [3]
[3]

Следовательно, primeFactors 3 есть [3], и нам не нужно было смотреть за пределы 2 в простых числах. (Это ключевой момент, почему это работает!) Ясно, что длина [3] равна 1 и

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

оценивается как

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

Теперь вы можете уменьшить primeFactors 5 для себя.

Ответ 2

Это лень в действии:) Список простых чисел начинается непустым,

primes = 2 : don't_know_yet_let's_see

и primeFactors вычисляет простые множители числа, используя список простых чисел. Но чтобы найти простые множители любого числа "n", нам нужно знать только числа до sqrt(n). Итак, хвост primes,

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

может использовать то, что уже известно из primes. Чтобы проверить 3, мы

factor 3 (2:don't_kow_yet_let's_see)
    | 2*2 > 3 = [3]
    | don't_care_above_was_true

И если мы начнем с любого n, скажем n = 35, чтобы он был коротким,

factor 35 (2:??)
    | 2*2 > 35  -- False, next clause
    | 35 `mod` 2 == 0 -- False, next clause
    | otherwise = factor 35 ??

Теперь нам нужно выяснить, что такое ??. Мы видели выше, что filter ing позволяет 3 пройти, поэтому 3:???, следовательно,

factor 35 (3:???)
    | -- first two guards are False
    | otherwise = factor 35 ???

Теперь, что ???? Ну, filter ((== 1) . length . primeFactors) [5, 7 .. ], так что посмотрим, проходит ли 5 фильтр

factor 5 (2:3:???)  -- note, we already know the first two elements of primes
    | 2*2 > 5 -- False
    | 5 `mod` 2 == 0 -- False
    | otherwise = factor 5 (3:???)
                     | 3*3 > 5 = [5]

Итак, 5 проходит, и мы знаем первые три элемента из primes. При факторизации 35 продолжаем

factor 35 (5:????)
    | 5*5 > 35 -- False
    | 35 `mod` 5 == 0 = 5 : factor (35 `div` 5) (5:????)
                            factor 7 (5:????)
                               | 5*5 > 7 = [7]

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