Понимание рекурсивного списка в Haskell приводит к переполнению стека C - PullRequest
Новая
       53

Понимание рекурсивного списка в Haskell приводит к переполнению стека C

2 голосов
/ 05 марта 2011

Итак, я составляю список простых чисел, чтобы помочь мне изучить haskell, используя простое пробное деление (нет ничего сложного, пока я не стану лучше с языком). Я пытаюсь использовать следующий код: 

primes = 2 : [ x | x <- [3..], all (\p -> (mod x p) /= 0) primes]

Загружается без ошибок. Тем не менее: 

>take 2 primes
[2ERROR - C stack overflow

Я пробовал то же самое с вложенными списками. Не работает Я предполагаю, что я делаю слишком много рекурсивных вызовов, но этого не должно быть, если я вычисляю только одно простое число. На мой взгляд, ленивая оценка должна сделать так, чтобы take 2 primes делал что-то вроде: 

primes = 2 : [ 3 | all (\p -> (mod 3 p) /= 0) [2] ]

Что не требует таких больших вычислений - mod 3 2 == True, поэтому all (\p -> (mod 3 p) /= 0) == True, что означает take 2 primes == [2, 3], верно? Я не понимаю, почему это не работает. Надеюсь, кто-то, кто намного лучше разбирается в черной магии функционального программирования, может мне помочь ...

Это на объятиях, если это что-то меняет.

РЕДАКТИРОВАТЬ - я смог придумать это решение (не очень): 

primes = 2 : [ x | x <- [3..], all (\p -> (mod x p) /= 0) (takeWhile (<= (ceiling (sqrt (fromIntegral x)))) primes)]

EDIT2 - программа отлично работает при интерпретации через HUGS или GHCi, но когда я пытаюсь скомпилировать ее с GHC, выдает test: <<loop>>. Кто-нибудь знает в чем проблема?

Ответы [ 3 ]

7 голосов
/ 05 марта 2011

Объятия не должны этого делать, но код все равно не работает, так что это не имеет значения.Подумайте: 

primes = 2 : [ x | x <- [3..], all (\p -> (mod x p) /= 0) primes]

Как вы определяете, простое ли 3?хорошо, mod 3 2 == 0?Нет. mod 3 ??? == 0?OOPS!Каков следующий элемент простых чисел после двух?мы не знаем, мы пытаемся вычислить это.Вам необходимо добавить ограничение порядка, которое добавляет 3 (или любые другие x) после того, как все p elem простых чисел меньше sqrt x были протестированы.

3 голосов
/ 05 марта 2011

В документации для всех написано "Чтобы результат был True, список должен быть конечным" http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:all

0 голосов
/ 11 июля 2011

Предыдущие ответы объяснили, почему первоначальное понимание не сработало, а не то, как написать то, что сработало бы.

Вот понимание списка, которое рекурсивно, лениво (хотя и не эффективно) вычисляет все простые числа: 

let primes = [x | x <- 2:[3,5..], x == 2 || not (contains (\p -> 0 == (mod x p)) (takeWhile (\b -> (b * b) < x) primes))]

Очевидно, что нам не нужно проверять mod x p для всех простых чисел, нам нужно делать это только для простых чисел, меньших, чем sqrt потенциального простого числа. Вот для чего нужен TakeWhile. Простите (\b -> (b * b) < x), это должно быть эквивалентно (< sqrt x), но системе типов Хаскелла это не понравилось.

x == 2 вообще запрещает выполнение takeWhile до того, как мы добавили какие-либо элементы в список.

...