Haskell ошибка генератора простое число

Question

Я пробовал:

composites=[c|c<-[4..], any (\p->(c`mod`p == 0)) (takeWhile (< (sqrt c)) primes)] 
primes=2:[p|p<-[3..], not p `elem` (takeWhile (<p) composites)] 

и получил:

pad.hs:1:19: 
    No instance for (Num Bool) arising from the literal `4' 
    Possible fix: add an instance declaration for (Num Bool) 
    In the expression: 4 
    In the expression: [4 .. ] 
    In a stmt of a list comprehension: c <- [4 .. ] 

pad.hs:1:30: 
    No instance for (Integral Bool) arising from a use of `divisible' 
    Possible fix: add an instance declaration for (Integral Bool) 
    In the first argument of `any', namely `(divisible c)' 
    In the expression: any (divisible c) (factors c) 
    In a stmt of a list comprehension: any (divisible c) (factors c) 

pad.hs:3:43: 
    No instance for (Floating Bool) arising from a use of `sqrt' 
    Possible fix: add an instance declaration for (Floating Bool) 
    In the second argument of `(<)', namely `sqrt c' 
    In the first argument of `takeWhile', namely `(< sqrt c)' 
    In the expression: takeWhile (< sqrt c) primes 
Failed, modules loaded: none. 

Я думаю, что он смущен, какой тип номера он имеет дело с, но я не уверен, , Какие-нибудь советы?

Answer 1

Я думаю, что он смущен, какой тип номера он имеет дело с

Совершенно верно! Так почему бы вам не сказать это? Это всегда хорошая идея написать подпись функции в Haskell, до фактической реализации. Это не только предотвращает такие запутывающие сообщения компилятора, когда что-то не так, но и является действительно хорошим руководством при фактическом проектировании функции.

Так что в вашем случае, вы, вероятно, хотите

composites, primes :: [Integer] 

, который, конечно, не решает проблему, но это делает сообщения об ошибках гораздо яснее:

Prelude> пусть композиты, воспламеняет :: [Integer]; composites = [c | c < - [4 ..], any (\ p -> c`mod`p == 0) (takeWhile (< sqrt c) простые числа)]; штрихи = 2: [р | р < - [3 ..], а не р `elem` (TakeWhile (< р) композиты)]

< интерактивный>: 2: 128:
не могло соответствовать предполагаемому типа` Integer 'с фактическим типом `Bool'
В выражении: p
Во втором аргументе` (:) ', а именно
`[p | p < - [3 ..], а не p `elem` (takeWhile (< p) composites)] '
В выражении:
2: [p | р < - [3 ..], а не р `elem` (TakeWhile (< р) композиты)]

< интерактивными>: 2: 169:
не могли соответствовать типа` Integer 'с `Bool'
Ожидаемого типа: [Bool]
Фактического типа: [Целое]
Во втором аргументе `TakeWhile 'а именно` композиты
Во втором аргументе `эля', а именно
` (TakeWhile (< р) композиты) '
In t он выражение: не р `elem` (TakeWhile (< р) композиты)

Это еще не совсем к месту, но, по крайней мере, теперь он локализует ошибку, где она находится: в primes, p выводится Bool, что, конечно, неправильно. Причина для bool заключается в том, что у вас есть not p `elem` (...). Очевидно, вы считаете, что это анализируется как not (p`elem`(...)), но это не так: простая префиксная функция имеет более высокий приоритет, чем любой инфиксный оператор.Важно знать (вот почему вам не нужны парсеры вокруг sqrt c в (< sqrt c)).

Давайте поправим, то остается еще одна проблема:

Prelude> пусть композиты, воспламеняет :: [Integer]; composites = [c | c < - [4 ..], any (\ p -> (c`mod`p == 0)) (takeWhile (< (sqrt c)) простые числа)]; штрихи = 2: [р | р < - [3 ..], а не $ р `elem` (TakeWhile (< р) композиты)]

< интерактивного>: 3: 99:
Нет экземпляр для (Плавающие Integer), возникающие из использования `SQRT '
Возможные исправления: добавить объявление экземпляра для (Floating Integer)
Во втором аргументе` (<)', а именно `(SQRT с)»
В первый аргумент `takeWhile ', а именно` (< (sqrt c))'
Во втором аргументе `any ', а именно
`(TakeWhile (< (SQRT с)) простые числа)»

Теперь это пятно на: вы имеете дело с целыми числами, но sqrt дает, очевидно, как правило, иррациональные числа, так что имеет смысл только с a Floating тип. Чтобы обойти это, вы можете использовать (по общему признанию уродливый, но хорошо) sqrt' = round . sqrt . fromIntegral.

---

На самом деле, это мономорфная подпись, вероятно, не идеально - вы можете предпочесть Int по разным причинам (в основном эффективность). Чтобы быть в безопасности, можно было бы выбрать Integral a => [a]; однако полиморфные значения не «запоминаются» на верхнем уровне, что опять-таки довольно проблематично в этом примере.

Answer 2

Любые советы?

Ну, теперь, когда вы получили это фиксированный,

composites=[c|c<-[4..], any ((==0).(c`mod`)) (takeWhile ((<= c).(^2)) primes)] 
primes=2:[p|p<-[3..], not (p `elem` takeWhile (<= p) composites)] 

рассмотреть, можно ли сделать это быстрее. Во-первых, elem полностью поглощает свой второй аргумент, когда в нем нет 1-го, и всегда ищет с самого начала. Но если мы только искали среди композитов, нет необходимости начинать сначала, когда мы ищем следующий - мы можем продолжать с той же точки:

notAmong (_, (k:ks,c:cs))    -- a candidate that is not among 
    | k == c = (Nothing, (ks,cs)) --  the composites, is a prime 
    | otherwise = (Just k, (ks,c:cs)) -- (k < c) 
primes = 2 : [p | (Just p,_) <- iterate notAmong (Just 3, ([4..],composites))] 

У нас есть fused функции not, elem и takewhile, с большим преимуществом по скорости.

Постарайтесь выяснить эту версию empirical orders of growth и сравнить ее с оригинальной версией.