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

17

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

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

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

    
задан nubela 19.11.2009 в 16:38
источник

5 ответов

12

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

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

    
ответ дан mipadi 19.11.2009 в 16:49
источник
19

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

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

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

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 и возвращает true, если он не кратен p .
  3. Теперь, когда sieve определено, мы передаем ему [2 .. ] , список всех натуральных чисел, начинающихся с 2. Таким образом,

    1. Будет возвращено число 2. Все остальные натуральные числа, кратные двум, будут отброшены.
    2. Второе число равно 3. Оно будет возвращено. Все остальные кратные 3 будут отброшены.
    3. Таким образом, следующее число будет равно 5. Etc.
ответ дан Stephan202 19.11.2009 в 16:50
источник
8

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

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 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 (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 , 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

см. также .

    
ответ дан Will Ness 15.01.2012 в 18:51
источник
1

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

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

    
ответ дан sykora 19.11.2009 в 16:42
источник
1

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

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

    
ответ дан Jonathan Feinberg 19.11.2009 в 16:47
источник