1

I tried:

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

and got:

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.

I think that it is confused as to what type of number it is dealing with, but I am not sure. Any tips?

4

2 回答 2

2

我认为它正在处理什么类型的数字感到困惑

非常正确！那你为什么不告诉它？在实际实现之前，在 Haskell 中编写函数签名总是一个好主意。这不仅可以防止出现错误时出现这种令人困惑的编译器消息，而且还为实际设计函数提供了一个非常好的指南。

所以在你的情况下，你可能想要1

composites, primes :: [Integer]

这当然不能解决问题，但它使错误消息更加清晰：

Prelude> letcomposites,primes::[Integer]; 复合材料=[c|c<-[4..], any (\p -> c`mod`p == 0) (takeWhile (< sqrt c) primes)]; primes=2:[p|p<-[3..], not p `elem` (takeWhile (< p) composites)]

<‌interactive>:2:128:
    无法将预期类型“整数”与实际类型匹配`Bool'
    在表达式中： p
    在 `(:)' 的第二个参数中，即
      `[p | p <- [3 .. ]，而不是 p `elem`（takeWhile (< p) 复合）]'
    在表达式中：
      2 : [p | p <- [3 .. ]，不是 p `elem`（takeWhile (< p) 复合材料）]

<‌interactive>：2:169：
    无法将类型“整数”与“布尔”匹配
    预期类型：[布尔]
      实际类型：
    在 `takeWhile' 的第二个参数中，即 `composites'
    在 `elem' 的第二个参数中，即
      `(takeWhile (< p) composites)'
    表达式中：not p `elem` (takeWhile (< p) composites)

它仍然不完全正确，但至少它现在将错误定位到它所在的位置： in primes，p被推断为Bool，这当然是错误的。bool 的原因是你not p `elem` (...)在那里。显然您认为这被解析为not (p`elem`(...))，但事实并非如此：普通前缀函数应用程序具有比任何中缀运算符更高的优先级。一件重要的事情要知道（这也是为什么你不需要括号的原因sqrt c）(< sqrt c)。

让我们解决这个问题，那么还有一个问题：

Prelude> letcomposites,primes::[Integer]; 复合=[c|c<‌-[4..], any (\p->(c`mod`p == 0)) (takeWhile (<‌ (sqrt c)) primes)]; primes=2:[p|p<‌-[3..], not $ p `elem` (takeWhile (<‌p)composites)]

<‌interactive>:3:99:
    (Floating Integer) 没有来自 a 的实例使用 `sqrt'
    可能的解决方法：为 (Floating Integer) 添加一个实例声明
    在 `(<‌)' 的第二个参数中，即 `(sqrt c)'
    在 `takeWhile' 的第一个参数中，即 `(< (sqrt c))'
    在 `any' 的第二个参数中，即
      `(takeWhile (<‌ (sqrt c)) primes)'

现在这是正确的：您正在处理整数，但sqrt显然通常会产生无理数，所以它只对类型有意义Floating。为了解决这个问题，您可以使用 (无可否认，但没关系) sqrt' = round . sqrt . fromIntegral。

1实际上，这种单态签名可能并不理想——您可能Int出于各种原因（主要是效率）更喜欢。为了安全起见，人们会选择 Integral a => [a]; 然而，多态值并没有在顶层“记忆”，这在这个例子中又是一个相当大的问题。

于 2013-11-02T02:00:43.453 回答
1

有小费吗？

好了，既然你修好了，

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

考虑是否可以让它更快。一方面，elem当第一个参数不存在时，完全消耗它的第二个参数，并且总是从头开始搜索。但是，如果我们刚刚在复合材料中搜索了16 个，那么当我们接下来搜索17 个时就无需重新开始- 我们可以从同一点继续：

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

我们融合not了,elem和,功能，takewhile在速度上具有很大的好处。

试着找出这个版本的经验增长顺序，并与原版进行比较，很好玩。

于 2013-11-03T11:20:19.220 回答