8

私はHaskellを初めて使用し、少し試しています。

isPrime :: Integer->Bool
isPrime x = ([] == [y | y<-[2..floor (sqrt x)], mod x y == 0])

少し質問があります。

  1. .hsを読み込もうとすると、WinHugsは次のように言います。(Floating Integer, RealFrac Integer)の定義に必要なインスタンスisPrime？
  2. インタプリタが正しいセットで1つの要素を見つけると、すぐに停止しますか、それともすべてのセットを計算しますか？あなたは私が何を意味するか知っていると思います。

私の英語について申し訳ありません。

4

5 に答える 5

17

1）問題はsqrt、タイプ(Floating a) => a -> aが であるが、整数を引数として使用しようとすることです。したがって、最初に Integer を Floating に変換する必要があります。たとえば、次のように記述します。sqrt (fromIntegral x)

2) == が遅延してはならない理由はわかりませんが、空のコレクションをテストするには、null関数を使用できます (無限リストで機能するため、これは間違いなく遅延です)。

isPrime :: Integer->Bool
isPrime x = null [y | y<-[2..floor (sqrt (fromIntegral x))], x `mod` y == 0]

しかし、より慣用的な解決策を得るには、問題をより小さなサブ問題に分割します。まず、y*y <= x であるすべての要素 y のリストが必要です。

takeWhile (\y ->  y*y <= x) [2..]

次に、x を分割する要素のみが必要です。

filter (\y ->  x `mod`y == 0) (takeWhile (\y ->  y*y <= x) [2..])

次に、そのリストが空かどうかを確認する必要があります。

isPrime x = null (filter (\y ->  x `mod`y == 0) (takeWhile (\y ->  y*y <= x) [2..]))

そして、これがあなたにぎこちないように見える場合は、括弧の一部を $ に置き換えてください

isPrime x = null $ filter (\y ->  x `mod` y == 0) $ takeWhile (\y ->  y*y <= x) [2..]

さらに明確にするために、ラムダを「アウトソーシング」できます。

isPrime x = null $ filter divisible $ takeWhile notTooBig [2..] where
     divisible y = x `mod`y == 0
     notTooBig y = y*y <= x

null $ フィルターを not $ any に置き換えることで、ほとんど「人間が読める」ものにすることができます。

isPrime x = not $ any divisible $ takeWhile notTooBig [2..] where
     divisible y = x `mod`y == 0
     notTooBig y = y*y <= x
于 2010-12-27T20:15:34.210 に答える
7

  1. sqrtタイプがあるからですFloating a => a -> a。これは、入力がFloating型である必要があり、出力が同じ型になることを意味します。つまりx、型である必要がありますFloating。ただし、タイプではないxtype であると宣言しました。さらに、タイプが必要なので、それも必要です。IntegerFloatingfloorRealFracx

    Integerエラーメッセージは、Floating型を作成することによって（インスタンスを定義することによって）それを修正することを示唆していますFloating Integer（および についても同じですRealFrac）。

    もちろん、これはこの場合の正しいアプローチではありません。むしろ、 を使用して ( andのインスタンスである)fromIntegralに変換xし、それを に渡す必要があります。RealFloatingRealFracsqrt

  2. はい。==右側のオペランドに少なくとも 1 つの要素があることがわかるとすぐに、それが と等しくないことを認識し[]、 を返しますFalse。

    そうは言ってnullも、リストが空かどうかを確認する方法は、より慣用的な方法です[] ==。

于 2010-12-27T20:12:01.427 に答える
1

Landei のソリューションは優れていますが、より効率的な¹ 実装が必要な場合は (BMeph に感謝):

-- list of all primes
primes :: [Integer]
primes = sieve (2 : 3 : possible [1..]) where
     sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]
     possible (x:xs) = 6*x-1 : 6*x+1 : possible xs

isPrime :: Integer -> Bool
isPrime n = shortCircuit || (not $ any divisible $ takeWhile inRangeOf primes) where
    shortCircuit = elem n [2,3] || (n < 25 && ((n-1) `mod` 6 == 0 || (n+1) `mod` 6 == 0))
    divisible y = n `mod` y == 0
    inRangeOf y = y * y <= n

「効率」は、一定の素数の使用に由来します。これにより、次の 2 つの方法で検索が改善されます。

  1. Haskell ランタイムは結果をキャッシュできるため、後続の呼び出しは評価されません。
  2. sieve値は単純な再帰テーブルであり、リストの先頭が素数であることに注意して、論理的に数値の範囲を削除し、それに追加します。リストの残りの部分については、その数を構成するリストに他の値が既に存在しない場合、その素数も possible可能なすべての素数のリストになります。これは、可能なすべての素数が 6*k-1 または 6*k-1 の形式であるためです。 2 と 3 を除いて 同じルールがshortCircuitあまりにも適用されて、計算をすばやく回避します

DF による脚注
¹ 素数を見つける方法は、依然として非常に非効率的です。数千を超える素数が必要な場合は、試行分割を使用しないでください。代わりにふるいを使用してください。hackageには、はるかに 効率的な実装がいくつかあります。

于 2010-12-31T22:09:20.440 に答える
1

2 番目の点については、次のように停止します。

[] == [x | x <- [1..]]

戻り値False

于 2010-12-27T20:12:14.367 に答える
-2
  1. WinHugs は Integer などのモジュールをインポートする必要があると思います... Int を試してください
  2. インタープリターは、あなたが呼び出すまで何も計算しません。たとえばisPrime 32、式を遅延して計算します。

PS あなたの isPrime 実装は最適な実装ではありません!

于 2010-12-27T20:12:36.933 に答える