Код Haskell для исключения чисел для решета Эратосфена не работает должным образом

Я пришел со следующей реализацией Sieve of Eratosthenes:

sieve :: (Integral a) => [a] -> [a]
sieve [] = []
sieve (p:ps) = p:[x | x <- sieve ps, (rem x p) /= 0] 

primes :: (Integral a) => [a]
primes = sieve [2..100]

Вызов primes из gchi печатает:

[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

Добавление этапа оптимизации начала маркировки чисел с p2, я получил следующий код:

sieve :: (Integral a) => [a] -> [a]
sieve [] = []
sieve (p:ps) = p:[x | x <- sieve ps, x > p ^ 2, (rem x p) /= 0] 

primes :: (Integral a) => [a]
primes = sieve [2..100]

Но он производит следующий вывод:

[2]

Я новичок в Haskell, поэтому мне трудно понять, почему добавление x > p ^ 2 приводит к такому результату.

Не могли бы вы указать на мою ошибку, объяснив, как Haskell вычисляет это выражение?


algorithm haskell sieve-of-eratosthenes
person higuaro    schedule 22.04.2015    source источник
comment
Это не решето Эратосфена. Это форма пробного разделения, и она будет медленной. Для более функционального сита см. решето О'Нила, который тесно связан с Эратосфеном.   -  person dfeuer    schedule 22.04.2015
comment
Меня беспокоила медлительность этой реализации, поэтому я хотел пропустить первые p^2 числа, но, как я узнал из ответов, это не работает. Спасибо за бумажную ссылку.   -  person higuaro    schedule 23.04.2015
comment
Фактическая реализация О'Нила немного сложнее (и намного лучше), чем в документе. Он находится в Math.Sieve.ONeill в пакете NumberSieves.   -  person dfeuer    schedule 23.04.2015

Ответы (2)


arrow_upward
2
arrow_downward

У вас есть

sieve [2..10]

Который расширяется до

2 : [x1 | x1 <- sieve [3..10], x1 > 4, rem x1 2 /= 0]
    = 2 : [x1 | x1 <- 3 : [x2 | x2 <- sieve [4..10],
                                x2 > 9,
                                x2 `rem` 3 /= 0],
                x1 > 4,
                x1 `rem` 2 /= 0]

Итак, первый x1 — это 3, а 3 > 4 — это False, поэтому мы переходим к следующему:

    = 2 : [x1 | x1 <- [x2 | x2 <- sieve [4..10],
                            x2 > 9,
                            x2 `rem` 3 /= 0],
                x1 > 4,
                x1 `rem` 2 /= 0]

    = 2 : [x1 | x1 <- [x2 | x2 <- 4 : [x3 | x3 <- sieve [5..10],
                                            x3 > 16,
                                            x3 `rem` 4 /= 0],
                            x2 > 9,
                            x2 `rem` 3 /= 0],
                x1 > 4,
                x1 `rem` 2 /= 0]

Итак, если x2 равно 4, x2 > 9 ложно, мы переходим к следующему элементу:

    = 2 : [x1 | x1 <- [x2 | x2 <- [x3 | x3 <- sieve [5..10],
                                        x3 > 16,
                                        x3 `rem` 4 /= 0],
                            x2 > 9,
                            x2 `rem` 3 /= 0],
                x1 > 4,
                x1 `rem` 2 /= 0]

Итак, мы уже можем видеть, что единственное фактическое значение, которое, как мы знаем, возвращается, это 2, 3 пропускается, потому что 3 > 4 равно False. 4 пропускается, но по неправильной причине, 5 будет пропущено, потому что 5 > 16 равно False, и так далее. Проблема здесь в том, что ваше условие x > p ^ 2 фильтрует весь список, но вы действительно хотите просто перейти вперед в своем списке. Это означает, что значения, которые вас действительно интересуют, отфильтровываются из вывода.

person bheklilr    schedule 22.04.2015
comment
Спасибо, действительно хороший ответ! Есть ли способ продвинуться вперед в списке, используя этот подход, или мне следует подумать о том, чтобы сделать это по-другому? - person higuaro; 22.04.2015
comment
@higuaro, как упоминалось в комментарии dfeuer выше, на самом деле вы не реализуете сито Эратосфена в этом стиле, было бы лучше попробовать другой способ поиска простых чисел. Генераторы списков не позволяют вам забегать вперед, они обрабатывают каждый элемент по порядку. - person bheklilr; 22.04.2015
comment
@higuaro, насколько мне известно, единственный (достаточно простой) способ продвинуться вперед — это использовать колесо , метод, который О'Нил объясняет в своей статье гораздо лучше. Проблема с колесами, похоже, в том, что они довольно быстро становятся большими. Другие подходы направлены на максимально быстрое пережевывание композитов. - person dfeuer; 23.04.2015

arrow_upward
1
arrow_downward

Эта строка кода:

p:[x | x <- sieve ps, x > p ^ 2, (rem x p) /= 0]

говорит: «Возьмите все x из sieve ps, такие что x > p^2 и x не делятся на p». Это означает, что все числа, меньшие или равные p^2, отбрасываются. Это явно неправильно (наименьший встречный пример: [2..3]).

person kraskevich    schedule 22.04.2015