1

我正在尝试创建primes一个素数列表的函数，但不知何故我失败了。编译器抛出一个我不知道如何解决的错误：

错误：

Ambiguous type variable 'a0'

代码：

candidates :: [Integer]
candidates = [2]++[3,5..]

primes :: [Integer]
primes = filter is_prime candidates

is_prime :: Integer -> Bool
is_prime candidate
    | candidate == 1 = False
    | candidate == 2 = True
    | candidate == 3 = True
    | otherwise = r_is_prime candidate 0

-- r as recursive
r_is_prime :: Integer -> Integer -> Bool
r_is_prime candidate order
    | n_th_prime >= max_compared_prime = True
    | candidate `mod` n_th_prime  == 0 = False
    | otherwise = if (r_is_prime candidate (order+1) ) then True else False
    where 
        n_th_prime = candidates !! fromIntegral(order)
        -- this is the line that throws an error...
        max_compared_prime = fromIntegral ( ceiling ( fromIntegral ( sqrt ( fromIntegral candidate))))
4

3 回答 3

3

在

max_compared_prime = fromIntegral ( ceiling ( fromIntegral ( sqrt ( fromIntegral candidate))))

你有fromIntegral太多了。sqrt有类型

sqrt :: Floating a => a -> a

所以结果sqrt不是Integral类型的成员。并且结果ceiling是一个Integral类型，所以最后一个fromIntegral是多余的（但不会有害）。

max_compared_prime = ceiling ( sqrt ( fromIntegral candidate))

是您在该行中所需要的。

但是请注意，

n_th_prime = candidates !! fromIntegral(order)

意味着要针对第n-个候选素数进行测试，必须遍历候选列表，直到n达到第-个素数。因此，n这里对第 -th 个候选者的测试是 O(n) 而不是 O(1) [好吧，假设数字是有界的]，这是一个单一的除法。

更有效的试除法只尝试除法的素数，并记住当它进入下一个素数时它在素数列表中的位置。例如

is_prime :: Integer -> Bool
is_prime n
    | n < 2     = False
    | n < 4     = True
    | otherwise = trialDivision primes
      where
        r = floor (sqrt $ fromIntegral n)
        trialDivision (p:ps)
            | r < p     = True
            | otherwise = n `rem` p /= 0 && trialDivision ps

只需遍历素数列表以进行试验除法，因此从一个素数到下一个素数是列表中的一个简单步骤。

于 2012-04-28T13:42:23.260 回答
3

fromIntegral你的 s太多了

max_compared_prime = fromIntegral ( ceiling ( fromIntegral ( sqrt ( fromIntegral candidate))))

fromIntegral应用于结果导致sqrt错误。如果我们查看类型签名，我们有：

fromIntegral :: (Num b, Integral a) => a -> b
sqrt :: Floating a => a -> a

因此，要正确推断fromIntegral (sqrt x)Haskell 的类型，需要找到同时具有Floating和Integral实例的类型（以便 的结果sqrt与 的参数匹配fromIntegral）。Haskell 找不到这样的类型，因此（基本上）要求您指定一个（但没有一个）。解决方案是忽略这个fromIntegral：

max_compared_prime = fromIntegral ( ceiling ( sqrt ( fromIntegral candidate)))

其他注意事项

括号并不是特别惯用的 Haskell，因此该行可以/应该写成：

max_compared_prime = fromIntegral . ceiling . sqrt . fromIntegral $ candidate

此外，结果ceiling不需要转换，因此它甚至可以是：

max_compared_prime = ceiling . sqrt . fromIntegral $ candidate
于 2012-04-28T13:45:55.753 回答
1

从“sqrt”之前删除“fromIntegral”，如下：

max_compared_prime = fromIntegral ( ceiling ( sqrt ( fromIntegral candidate)))

类型有：

sqrt :: Floating a => a -> a
fromIntegral :: (Integral a, Num b) => a -> b

sqrt 的输出是“浮动的”，而不是积分的。

于 2012-04-28T13:43:31.063 回答