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

Я новичок в программировании 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.

Ответы

Ответ 1

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

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, ...]

Inline 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])

Inline 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]

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

Ответ 2

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

Чтобы вычислить sieve (x:xs):

  • Вывести ведущий элемент x.
  • Из хвоста xs пусть ys будет список xs со всеми кратными x удаленными.
  • Чтобы сгенерировать следующий элемент, рекурсивно вызовите 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,...]

и др.

Ответ 3

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

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 фильтр postponed, пока на вход не будет достигнуто p*p.