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

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

2 голосов
/ 22 мая 2011

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

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) " - более или менее.(Надеюсь, я правильно понял?)

Спасибо!

Ответы [ 2 ]

0 голосов
/ 01 августа 2016

ваш код, 

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

Оптимальное пробное деление обычно выполняется при ~ n 1.4..1.45 , на основе списка сито Эратосфена в ~ n 1.2..1.25 и, если это оптимально реализовано на изменяемых массивах, при ~ n 1.0..1.1 (с n количество произведенных простых чисел, не верхний предел).

0 голосов
/ 22 мая 2011

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

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

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

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

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