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