Понимание списков Haskell для поиска простых чисел

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

isqrt :: Integral a => a -> a   
isqrt = floor . sqrt . fromIntegral

primes :: Integral a => a -> [a]  
primes n = [i | i <- [1,3..n], mod i k /= 0 | k <- primes (isqrt i)]

что конечно не работает. Есть ли способ иметь понимание списка внутри понимания списка?

Вот ошибка, которую я получаю:

exercise-99-1.hs:138:39: Not in scope: `k'

exercise-99-1.hs:138:46:
    Illegal parallel list comprehension: use -XParallelListComp

exercise-99-1.hs:138:68: Not in scope: `i'

НО - я действительно не ожидал, что синтаксис будет даже законным :-)

Намерение состояло в том, чтобы перевести как можно более прямо: " primes n = набор нечетных целых чисел i меньше n, таких что i не делится ни на одно k, для всех k в наборе: primes (isqrt i)" - больше или менее. (Надеюсь, я правильно понял?)

Спасибо!


syntax syntax-error list-comprehension haskell primes
person Frank    schedule 22.05.2011    source источник
comment
Не работает крайне бесполезен. Опубликуйте ошибку.   -  person Dhaivat Pandya    schedule 22.05.2011
comment
Не могли бы вы поместить эту ошибку в тело вашего сообщения? Спасибо.   -  person Jonathan Sterling    schedule 22.05.2011
comment
вот один: [n | n<-[2..545], []<-[[j | i<-[2..n-2], j<-[i*i,i*i+i..n], j==n]]] - как пробное деление, так и своего рода сито Эратосфена.   -  person Will Ness    schedule 31.07.2016

Ответы (2)


arrow_upward
0
arrow_downward

Я добился некоторого прогресса в следующем:

primes :: Integral a => a -> [a]  
primes 2 = [2]  
primes n = 2:[i | i <- [3,5..n], all (\k -> if (mod i k /= 0) then True else False) 
                                     (primes (isqrt i))]

Есть ли более короткий способ написать лямбда-предикат?

редактировать: Да, есть, благодаря замечаниям в комментариях!

primes :: Integral a => a -> [a]  
primes 2 = [2]  
primes n = 2:[i | i <- [3,5..n], all ((/= 0) . mod i) (primes (isqrt i))]
person Frank    schedule 22.05.2011
comment
Никогда не говорите if ... then True else False. Вместо этого просто произнесите часть ...: \k -> mod i k /= 0 - person Phob; 22.05.2011
comment
Вы также можете сделать это без точек, если вам это нравится: ((/= 0) . mod i) - person Phob; 22.05.2011
comment
Еще яснее определить отдельную функцию: divisible i = (== 0) . mod i, а затем вместо вашей лямбда-функции иметь (not . divisible i) - person Phob; 22.05.2011
comment
По какой причине никогда не говорят, если... то Верно, иначе Ложно? - person Frank; 22.05.2011
comment
@Frank Потому что это полностью избыточно, поэтому код становится менее понятным. - person augustss; 22.05.2011
comment
@Frank: потому что условное выражение уже оценивается как True или False. Оператор if полностью лишний и загромождает все. - person C. A. McCann; 22.05.2011
comment
@Frank, ты хотел сказать без строки primes 2 = [2]. Что действительно должно было быть primes 1 = []. :) - person Will Ness; 01.08.2016

arrow_upward
0
arrow_downward

ваш код,

primes n = [i | i <- [1,3..n], mod i k /= 0 
              | k <- primes (isqrt i)]

интерпретируется как параллельное понимание списка; т. е. вместо того, чтобы объединять два генератора обычным вложенным способом, они объединяются параллельно:

primes n = [i | (i,k) <- zip [i | i <- [1,3..n], mod i k /= 0]
                                    -- not in scope: k ^
                             [k | k <- primes (isqrt i)] ]
                                  -- not in scope: i ^

Вместо этого, чтобы выразить то, что вы намеревались, это можно записать как

primes 1 = []
primes n = 2:[i | i <- [3,5..n], and [mod i k /= 0 | k <- primes (isqrt i)]]

таким образом, имея понимание списка внутри понимания списка, но как часть защиты, а не генератора. Функция and :: [Bool] -> Bool делает это возможным.

Между прочим, рекурсивный вызов primes для каждого нового кандидата i замедляет его работу, а время выполнения увеличивается слишком быстро, эмпирически:

 > length $ primes 10000     -- => 1229    (0.50 secs)

 > length $ primes 20000     -- => 2262    (1.40 secs)

 > logBase (2262/1229) (1.4/0.5)      -- => 1.6878      ~ n^1.69

 > length $ primes 40000     -- => 4203    (4.07 secs)

 > logBase (4203/2262) (4.07/1.4)     -- => 1.7225      ~ n^1.72

Оптимальное пробное деление обычно работает при ~ n1,4..1,45, решето Эратосфена на основе списка при ~ n1,2..1,25 и, при оптимальной реализации на изменяемых массивах, при ~ n1.0..1.1 (с n числом полученных простых чисел, не верхний предел).

person Will Ness    schedule 01.08.2016