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は、単一の除算であるO（1）[まあ、数が制限されていると仮定して]ではなくO（n）です。

より効率的な試行除算は、除算の素数のみを試行し、次の素数に進むときに素数のリストのどこにあったかを記憶します。例えば

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が多すぎます

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はそのようなタイプを見つけることができないので、（基本的に）1つを指定するように求めています（ただし、1つはありません）。解決策は、これを削除すること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の出力は「Floating」であり、Integralではありません。

于 2012-04-28T13:43:31.063 に答える