Генератор простых чисел с рекурсией и пониманием списка

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

primes = sieve [2..] 
sieve (p:xs) = p : sieve [x | x <-xs, x `mod` p /= 0]

Может ли кто-нибудь исправить меня, как sieve работы по расширению:

  • Как мы сопоставляем шаблон в sieve, p будет ассоциироваться с 2 а также xс из [3..],
  • Далее в списке понимания x<-3, но тогда как мы можем назвать сито просто 3 когда нет короткого замыкания.

Другая вещь, которую я не понимаю, это то, как здесь работает рекурсия.

Я думаю, что было бы ясно, если бы можно было расширить вышеуказанный шаг за раз для первых нескольких чисел, скажем, до 5,

Источник

3 ответа

Решение

Давайте сделаем некоторые рациональные рассуждения.

primes = sieve [2..]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

[2..] является синтаксическим сахаром для [2, 3, 4, 5, ...] так

primes = sieve [2, 3, 4, 5, 6, ...]

В соответствии sieve один раз:

primes = 2 : sieve [x | x <- [3, 4, 5, 6, 7, ...], x `mod` 2 /= 0]

Первый, x получает значение 3 который проходит mod 2 фильтр

primes = 2 : sieve (3 : [x | x <- [4, 5, 6, 7, ...], x `mod` 2 /= 0])

В соответствии sieve снова (я переименовал x в y чтобы не было путаницы)

primes = 2 : 3 : sieve [y | y <- [x | x <- [4, 5, 6, 7, ...], x `mod` 2 /= 0], 
                            y `mod` 3 /= 0]

Сейчас x = 4 не удается mod 2 но фильтр x = 5 проходит это. Так

primes = 2 : 3 : sieve [y | y <- 5 : [x | x <- [6, 7, 8, ...], x `mod` 2 /= 0], 
                            y `mod` 3 /= 0]

это y = 5 также проходит mod 3 фильтр, так что теперь у нас есть

primes = 2 : 3 : sieve (5 : [y | y <- [x | x <- [6, 7, 8, ...], x `mod` 2 /= 0], 
                                 y `mod` 3 /= 0])

расширяющийся sieve еще раз (z вместо y) заставляет нас

primes = 2 : 3 : 5 : sieve [z | z <- [y | y <- [x | x <- [6, 7, 8, ...], 
                                                    x `mod` 2 /= 0], 
                                          y `mod` 3 /= 0], 
                                z `mod` 5 /= 0]

И расширение продолжается по тому же пути.

Источник

Вот оперативное описание того, что sieve делает.

Вычислить sieve (x:xs):

  1. Испускать ведущий элемент x,
  2. Из хвоста xs, позволять ys быть в списке xs со всеми кратными x удален.
  3. Чтобы сгенерировать следующий элемент, рекурсивно вызовите sieve на ys определено в шаге 2.

Вот как вычисляются первые пару терминов:

sieve [2..]
  = sieve (2:[3..])              -- x = 2, xs = [3..]
  = 2 : sieve ys
      where ys = [3..] with all of the multiples of 2 removed
               = [3,5,7,9,...]
  = 2 : sieve [3,5,7,9,...]

а потом:

sieve [3,5,7,9,...]              -- x = 3, xs = [5,7,9,11,...]
  = 3 : sieve ys
      where ys = [5,7,9,11,13,15,17,...] with all of the multiples of 3 removed
               = [5,7,  11,13,   17,...]
  = 3 : sieve [5,7,11,13,17,...]

а потом:

sieve [5,7,11,13,17,...]         -- x = 5, xs = [7,11,13,17..]
  = 5 : sieve ys
      where ys = [7, 11,13, 17,19,...]  with all of the multiples of 5 removed
               = [7, 11,13, 17,19,...]  (the first one will be 25, then 35,...)
  = 5 : sieve [7,11,13,17,19,...]

и т.п.

Источник

Использование вспомогательной функции

transform (p:xs) = [x | x <- xs, mod x p /= 0]
                 = filter (\x-> mod x p /= 0) xs  -- remove all multiples of p
                 = xs >>= noMult p                -- feed xs through a tester
-- where
noMult p x = [x | rem x p > 0]      -- keep x if not multiple of p

мы можем переписать sieve функционировать как

     ._________________________________________________
     |                                                 | 
     |  sieve input =                                  | 
     |                  .___________________________   |
     |                  |                           |  |
<--------- head input : | sieve (transform input )  |  |
     |                  |                           |  |
     |                  \===========================+  |  
     |                                                 |
     \=================================================+

В императивном псевдокоде мы могли бы написать это как

sieve input =
    while (True) :
        emit (head input)
        input := transform input

Этот шаблон повторных приложений известен как итерация:

iterate f x = loop x
  where
    loop x = x : loop (f x)   -- [x, f x, f (f x), f (f (f x)), ...]

Чтобы

sieve xs = map head ( iterate transform xs )

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

Haskell ленив, поэтому преобразования не будут выполняться полностью на каждом шаге, далеко не так - только столько, сколько потребуется. Это означает, что нужно создать только первый элемент и "сделать уведомление" для дальнейшего преобразования, когда его спросят:

<---- 2 ---     [2..]
<---- 3 ---     [3..] >>= noMult 2 
<---- 5 ---     ([4..] >>= noMult 2) >>= noMult 3 
<---- 7 ---     (([6..] >>= noMult 2) >>= noMult 3) >>= noMult 5
                ((([8..] >>= noMult 2) >>= noMult 3) >>= noMult 5) >>= noMult 7
.......

Между прочим, это должно дать нам представление: 3 не обязательно должно быть проверено 2; 4..8 действительно не нужно проверять 3, не говоря уже о 5 или 7; 9..24 не должно быть проверено 5; и т.д. То, что мы хотим, это следующее:

<---- 2,3       ---     [2..]
<---- 5,7       ---     [4..] >>= noMult 2 
<---- 11,...,23 ---     ([9..] >>= noMult 2) >>= noMult 3 
<---- 29,...,47 ---     (([25..] >>= noMult 2) >>= noMult 3) >>= noMult 5
                        ((([49..] >>= noMult 2) >>= noMult 3) >>= noMult 5)
.......                                                         >>= noMult 7

т.е. мы хотим создание каждого >>= noMult p фильтр отложен до p*p достигается на входе.

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