Объясните этот fragment кода Хеккеля, который выводит stream простых чисел

Мне трудно понять этот кусок кода:

let sieve (p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs) in sieve [2 .. ] 

Может кто-то сломает это для меня? Я понимаю, что в нем есть recursion, но я не понимаю, как работает recursion в этом примере.

Это на самом деле довольно элегантно.

Во-первых, мы определяем 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:

  x 'mod' p /= 0 

Затем элемент x сохраняется в списке. Если он равен 0, он отфильтровывается. Это имеет смысл: если x делится на p , то x делится на более чем на 1 и на себя и, следовательно, не является простым.

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

Я был о том, чтобы объяснить код, когда Мипади отправил свой ответ; Я мог бы удалить его, но поскольку я потратил на это некоторое время, и потому что наши ответы не полностью идентичны, я оставлю его здесь.


Прежде всего, обратите внимание, что в коде, который вы опубликовали, есть некоторые синтаксические ошибки. Правильный код,

 let sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs) in sieve [2..] 
  1. let x in y определяет x и позволяет использовать его определение в y . Результат этого выражения является результатом y . Таким образом, в этом случае мы определяем sieve функции и возвращаем результат применения [2..] для sieve .

  2. Теперь давайте более подробно рассмотрим часть этого выражения:

     sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs) 
    1. Это определяет sieve функции, которое принимает список в качестве первого аргумента.
    2. (p:xs) – это шаблон, который соответствует p с головой указанного списка и xs с хвостом (все, кроме головы).
    3. В общем случае p : xs – это список, первым элементом которого является p . xs – список, содержащий остальные элементы. Таким образом, sieve возвращает первый элемент списка, который он получает.
    4. Не смотрите на оставшуюся часть списка:

       sieve (filter (\x -> x `mod` p /= 0) xs) 
      1. Мы можем видеть, что sieve называется рекурсивно. Таким образом, выражение filter вернет список.
      2. filter выполняет функцию фильтра и список. Он возвращает только те элементы в списке, для которых функция фильтра возвращает true.
      3. В этом случае xs – это список, который фильтруется и

         (\x -> x `mod` p /= 0) 

        является функцией фильтра.

      4. Функция фильтра принимает один аргумент, x и возвращает true, если он не кратен p .
  3. Теперь, когда определено sieve , мы передаем его [2 .. ] , список всех натуральных чисел, начинающихся с 2. Таким образом,

    1. Номер 2 будет возвращен. Все остальные натуральные числа, кратные 2, будут отброшены.
    2. Таким образом, второе число равно 3. Оно будет возвращено. Все остальные кратные 3 будут отброшены.
    3. Таким образом, следующее число будет равно 5. И т.д.

Он определяет генератор – трансформатор streamа, называемый «сито» ,

 Sieve s = while( True ): p := s.head s := s.tail yield p -- produce this s := Filter (nomultsof p) s -- go next primes := Sieve (Nums 2) 

который использует карнидную форму анонимной функции, эквивалентную

 nomultsof px = (mod xp) /= 0 

И Sieve и Filter являются операциями построения данных с семантикой передачи состояния и переменной аргумента.


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

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

Исправленная версия с созданием фильтра, отложенным до нужного момента,

 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 (nomultsof p) s primes := Sieve primes (Nums 2) 

или в Haskell ,

 primes = sieve primes [2..] sieve ps (x:xs) = x : h ++ sieve pt [x | x <- t, rem xp /= 0] where (p:pt) = ps (h,t) = span (< p*p) xs 

rem используется здесь вместо mod поскольку в некоторых интерпретаторах он может быть намного быстрее, и все равно все цифры положительны.

Измеряя локальные порядки роста алгоритма, беря его время выполнения t1,t2 в точках размера задачи n1,n2 , как 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 

см. также .


обновление: Любопытно, что первый экземпляр этого кода в пособии Дэвида Тернера 1976 года SASL в соответствии с AJT Davie's 1992 Haskell,

  primes = sieve [2..] sieve (p:nos) = p : sieve (remove (multsof p) nos) 

фактически допускает две пары реализаций для remove и multsof собирающихся вместе - одна пара для сита пробного деления, как в этом вопросе, а другая для упорядоченного удаления кратных штрихов, непосредственно генерируемых подсчетом, ака подлинное сито Эратосфена (оба было бы, конечно, не отложено). В Haskell,

  multsof pn = rem np == 0 remove m xs = filter (not . m) xs multsof p = [p*p, p*p+p..] remove m xs = diff xs m 

Если бы он отложил сбор фактической реализации ...

Что касается отложенного кода, то в псевдокоде с «шаблонами списков» это может быть

  primes = 2 : sieve primes [3..] sieve (p:ps) [h ... [p*p] ... nos] = [h ... sieve ps (remove (multsof p) nos)] 

Он реализует сито эратосфена

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

В нем говорится: «Решетка какого-то списка – это первый элемент списка (который мы будем называть p) и сито остальной части списка, отфильтрованный таким образом, что разрешены только элементы, не делящиеся на p». Затем он начинает вещание, возвращая сито всех целых чисел от 2 до бесконечности (что равно 2, за которым следует сито всех целых чисел, не делящихся на 2 и т. Д.).

Я рекомендую The Little Schemer перед атакой на Haskell.

  • Передача имени переменной в функцию из R
  • Давайте будем гением компьютера.