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

У меня проблемы с пониманием этого куска кода:

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

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

Источник

5 ответов

Решение

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

Сначала мы определим функцию 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. Теперь давайте подробнее рассмотрим let часть этого выражения:

    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 и возвращает истину, если он не кратен p,

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

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

Он определяет генератор - трансформатор потока, называемый "сито",

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 p x = (mod x p) /= 0

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

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

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

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

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)

или в Хаскеле,

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, как 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

см. также

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

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

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

    multsof p n = rem n p == 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 и т. Д.).

Я рекомендую Маленький Схемер, прежде чем атаковать Хаскелл.

Источник
Другие вопросы по тегам