Мне трудно понять этот кусок кода:
let
sieve (p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs)
in sieve [2 .. ]
Может кто-то сломает меня? Я понимаю, что в нем есть рекурсия, но я не понимаю, как работает рекурсия в этом примере.
Мне трудно понять этот кусок кода:
let
sieve (p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs)
in sieve [2 .. ]
Может кто-то сломает меня? Я понимаю, что в нем есть рекурсия, но я не понимаю, как работает рекурсия в этом примере.
На самом деле это довольно элегантно.
Сначала мы определяем функцию sieve
, которая принимает список элементов:
sieve (p:xs)
В теле sieve
мы берем главу списка (потому что мы передаем бесконечный список [2..]
, а 2 определяется как простой) и добавим его к результату применения sieve
к остальной части списка:
p : sieve (filter (\ x -> x 'mod' p /= 0) xs)
Итак, посмотрим на код, который выполняет работу над остальной частью списка:
sieve (filter (\ x -> x 'mod' p /= 0) xs)
Мы применяем sieve
к отфильтрованному списку. Позвольте сломать, что делает часть фильтра:
filter (\ x -> x 'mod' p /= 0) xs
filter
принимает функцию и список, на которые мы применяем эту функцию, и сохраняем элементы, соответствующие критериям, заданным функцией. В этом случае filter
принимает анонимную функцию:
\ x -> x 'mod' p /= 0
Эта анонимная функция принимает один аргумент, x
. Он проверяет модуль x
на p
(заголовок списка, каждый раз при вызове sieve
):
x 'mod' p
Если модуль не равен 0:
'mod' p /= 0
Затем элемент x
сохраняется в списке. Если он равен 0, он отфильтровывается. Это имеет смысл: если x
делится на p
, чем x
делится более чем на 1 и само по себе и, следовательно, не является простым.
В отличие от других здесь, эта функция не реализует true решето Эратосфена. Он возвращает исходную последовательность простых чисел, хотя и аналогичным образом, поэтому можно подумать об этом как о сите Эратосфена.
Я проделал разъяснение кода, когда mipadi отправил свой ответ; Я мог бы удалить его, но поскольку я потратил на это некоторое время, и потому что наши ответы не полностью идентичны, я оставлю его здесь.
Прежде всего, обратите внимание, что в коде, который вы отправили, есть некоторые синтаксические ошибки. Правильный код:
let sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs) in sieve [2..]
let x in y
определяет x
и позволяет использовать его определение в y
. Результат этого выражения является результатом y
. Поэтому в этом случае мы определяем функцию sieve
и возвращаем результат применения [2..]
к sieve
.
Теперь давайте более подробно рассмотрим часть let
этого выражения:
sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs)
sieve
, которая принимает в качестве первого аргумента список.(p:xs)
- это шаблон, который соответствует p
с заголовком указанного списка и xs
с хвостом (все, кроме головы).p : xs
- это список, первым элементом которого является p
. xs
- это список, содержащий остальные элементы. Таким образом, sieve
возвращает первый элемент списка, который он получает.Не смотрите на оставшуюся часть списка:
sieve (filter (\x -> x `mod` p /= 0) xs)
sieve
вызывается рекурсивно. Таким образом, выражение filter
вернет список.filter
принимает функцию фильтра и список. Он возвращает только те элементы в списке, для которых функция фильтра возвращает true.В этом случае xs
- это список, который фильтруется и
(\x -> x `mod` p /= 0)
- функция фильтра.
x
и возвращает true, если он не кратен p
.Теперь, когда sieve
определен, мы передаем ему [2 .. ]
, список всех натуральных чисел, начинающихся с 2. Таким образом,
Он определяет генератор - трансформатор потока, называемый "сито" ,
Sieve s =
while( True ):
p := s.head
s := s.tail
yield p -- produce this
s := Filter (notAMultipleOf p) s -- go next
primes := Sieve (Nums 2)
который использует карриную форму анонимной функции, эквивалентную
notAMultipleOf p x = (mod x p) /= 0
Оба Sieve
и Filter
являются операциями построения данных с внутренней семантикой и внутренним состоянием аргументов.
Здесь мы видим, что самая вопиющая проблема этого кода не, повторите не, что она использует пробное деление, чтобы отфильтровать кратность из рабочей последовательности, тогда как оно может найти их напрямую, подсчет с шагом p
. Если бы мы заменили первый на последний, то полученный код по-прежнему имел бы ужасную сложность во время выполнения.
Нет, его самая вопиющая проблема заключается в том, что она добавляет Filter
поверх своей рабочей последовательности слишком скоро, когда она действительно должна это делать только после того, как на вкладке будет показан первый квадрат. В результате цепочка Filter
, которую он создает, является слишком длинной, и большинство из них даже не нужны вообще.
Исправленная версия с созданием фильтра отложено до нужного момента
Sieve ps s =
while( True ):
x := s.head
s := s.tail
yield x -- produce this
p := ps.head
q := p*p
while( (s.head) < q ):
yield (s.head) -- and these
s := s.tail
ps := ps.tail -- go next
s := Filter (notAMultipleOf p) s
primes := Sieve primes (Nums 2)
или в Haskell,
primes = sieve primes [2..]
sieve ps (x:xs) = x : h ++ sieve pt [x | x <- t, rem x p /= 0]
where (p:pt) = ps
(h,t) = span (< p*p) xs
rem
используется здесь вместо mod
, поскольку в некоторых интерпретаторах он может быть намного быстрее, и все равно все цифры положительны.
Измерение локальных порядков роста алгоритма путем выполнения его времени выполнения t1,t2
в точках размера задачи n1,n2
, as logBase (n2/n1) (t2/t1)
, получим O(n^2)
для первого и чуть выше O(n^1.4)
для второго (в выражении n
).
Чтобы уточнить это, недостающие части могут быть определены на этом (мнимом) языке просто как
Nums x = -- numbers from x
while( True ):
yield x
x := x+1
Filter pred s = -- filter a stream by a predicate
while( True ):
if pred (s.head) then yield (s.head)
s := s.tail
Он реализует Сито Эратосфена
В принципе, начните с простого (2) и отфильтруйте из остальных целых чисел, все кратные два. Следующее число в этом отфильтрованном списке также должно быть простым и, следовательно, фильтровать все его кратные от остальных и т.д.
В нем говорится: "Сито некоторого списка - это первый элемент списка (который мы будем называть p) и сито остальной части списка, отфильтрованный таким образом, что только" элементы, не делящиеся на p "разрешены через". Затем он начинает работать, возвращая сито всех целых чисел от 2 до бесконечности (что равно 2, за которым следует сито всех целых чисел, не делящихся на 2 и т.д.).
Я рекомендую The Little Schemer перед атакой Haskell.