哈斯克尔素数构造列表;歧义类型变量

Question

我正在尝试使函数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))))

Answer 1

in

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 个候选者的测试在这里是 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

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

Answer 2

你有太多的fromIntegral

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

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

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

Answer 3

从"sqrt"之前删除"fromIntegral"，作为：

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

类型是：

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

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