6

私は Haskell を (楽しみのために独学で) 学んでいますが、壁にぶつかりました。

私の質問：

関数を定義するにはどうすればよいですか

flrt = (floor . sqrt)

ファイルで試してコンパイルすると、GCHi は次のように不平を言います。

AKS.hs:11:9:
    No instance for (RealFrac Integer)
      arising from a use of `floor'
    Possible fix: add an instance declaration for (RealFrac Integer)
    In the first argument of `(.)', namely `floor'
    In the expression: (floor . sqrt)
    In an equation for `flrt': flrt = (floor . sqrt)

AKS.hs:11:17:
    No instance for (Floating Integer)
      arising from a use of `sqrt'
    Possible fix: add an instance declaration for (Floating Integer)
    In the second argument of `(.)', namely `sqrt'
    In the expression: (floor . sqrt)
    In an equation for `flrt': flrt = (floor . sqrt)

結果の関数が単に Int -> Int ではない理由がわかりません。

CS の 2 年目を終えたばかりで、基本的な PL コースを受講しました。聞いたことはありますが、まだタイプがわかりません。いくつかの haskell チュートリアルを読んでみましたが、それはすべて私の頭の上にあります。

PS - モナドとは何かもわかりません。（私の検索で見つかった他の多くの質問は、これらについて話しました）

PPS - 私の完全なソース

bar = \a b -> if (2^a) > b
                then (a-1)
                else bar (a+1) b
foo = bar 1

flrt :: Integer -> Integer
flrt = (floor . sqrt)

aks target = if (target < 2)
                then putStr "Not a Prime.\n\n"
                else if elem (mod target 10) [0,2,4,5,6,8]
                        then putStr "Composite\n\n"
                        else if (elem target) [a^b | a <- [3,5..(flrt target)], b <- [1.. (foo target)]]

                                then putStr "Composite\n\n"--}
                            else 
                            putStr "filler"
4

2 に答える 2

9

Integer問題は、入力として使用しようとしていることです。Haskell は厳密に型付けされています。つまり、暗黙の強制や変換は一切ありません。作成しようとしている関数のシグネチャを見てください。

sqrt  :: Floating a => a -> a
floor :: (RealFrac a, Integral b) => a -> b

そしてGHCによって推論されたあなたの関数の署名で：

> :t floor . sqrt
floor . sqrt :: (RealFrac b, Integral c, Floating b) => b -> c

したがって、 (インスタンスIntegerを持たない) から への関数を作成するには、まず引数を に変換する必要があります。これは、 を使用して実行できます。FloatingIntegerFloatingfromIntegral

> :t floor . sqrt . fromIntegral
floor . sqrt . fromIntegral :: (Integral a, Integral c) => a -> c
于 2012-06-02T15:15:00.110 に答える
5

copumpkin が指摘したように、ここで浮動小数点に変換するのは実際には悪い考えかもしれません。これは精度の低下を伴うため、丸めを行っても、十分に大きな整数入力に対して誤った結果をもたらす可能性があるためです。

あなたが扱っているすべての数値は、少なくともそれらの浮動小数点表現が存在するほど十分に小さいと思います。たとえば、すべて < 10 300です。しかし、例えば

Prelude> round(sqrt.fromInteger$10^60 :: Double) ^ 2
1000000000000000039769249677312000395398304974095154031886336
Prelude>  {-   and not   -}     10^60    {-  == (10^30)^2 == (sqrt$10^60) ^ 2  -}
1000000000000000000000000000000000000000000000000000000000000

絶対的な違いという点では、これはかなり外れています。それでも、数値自体に比べればかなり良い概算であることは確かなので、アルゴリズムが正確な結果を見つけるための迅速に決定される開始点として使用できます。Integersを使用して Newton/Raphson (この場合は AKA Heron) を実装できます。

flrt :: Integer -> Integer  -- flrt x ≈ √x,  with  flrt x^2 ≤ x < flrt(x+1)^2
flrt x = approx (round . (sqrt::Double->Double) . fromInteger $ x)
   where approx r
            | ctrl <= x, (r+1)^2 > x  = r
            | otherwise               = approx $ r - diff
          where ctrl = r^2
                diff = (ctrl - x) // (2*r)    -- ∂/∂x x² = 2x

         a//b = a`div`b + if (a>0)==(b>0) then 1 else 0   -- always away from 0

これは希望どおりに機能するようになりました。

*IntegerSqrt> (flrt $ 10^60) ^ 2
1000000000000000000000000000000000000000000000000000000000000

ここでは、ニュートン ラフソン補正で常に 0 から離れた除算が、無限再帰に陥るのを防ぐために必要です。

于 2012-06-02T20:11:35.240 に答える