1

私はHaskell（および関数型プログラミング全般）に非常に慣れていないので、言語を理解するためにいくつかの基本的な演習を試みています。入力の下の各数値を除算して余りがあるかどうかをチェックする「ナイーブな」素数チェッカーを書いています。これまでに学んだ構成は、理解リストと再帰関数だけなので、それに制約されます。これが私が試していることです：

isprime 1 = False
isprime 2 = True
isprime n = isprimerec n (n-1)

isprimerec _ 1 = False
isprimerec n t = if (n `rem` t) == 0 then False else isprimerec n (n-1)

意図は、ユーザーがを使用することisprime nです。次に、その数が素数であるかどうかを判断するためにisprime使用します。isprimerecそれはかなり回りくどい方法ですが、Haskellについての私の限られた知識では他の方法を知りません。

これを試してみると、次のようになります。

isprimerec 10 9

永遠に実行されます。Ctrl+Cを使用して停止する必要があります。

isprimerec 10 5

Falseを返します。パーツが評価されるelseことはないため、関数がそれ自体を呼び出すことはありません。

なぜこれが起こっているのかわかりません。また、これはHaskellプログラマーがこの問題に取り組む方法に近いところにありますか？（そして、私は素数性をチェックすることを意味しません、私はこれがそれをする方法ではないことを知っています。私はそれを練習としてこのようにやっているだけです）。

4

4 に答える 4

6

あなたのバグは単純なタイプミスです。の終わりにisprimerec、2番目のパラメータがn-1の代わりになりますt-1。しかし、それはさておき、この関数はあまり慣用的ではありません。これが私がそれを書く方法の最初のパスです：

isPrime :: (Ord a, Integral a) => a -> Bool
isPrime n | abs n <= 1 = False
isPrime 2 = True
isPrime n = go $ abs n - 1
  where go 1 = False
        go t = (n `rem` t /= 0) && go (t-1)

go（私はのようなものを呼び出すかもしれませんがcheckDivisors、goループの慣用句です。）これはコードのバグを明らかにすることに注意してください：一度goローカルになると、isPrime渡す必要がないnので、それを繰り返すことが正しくないことが明らかになります。私が行った変更は、大まかに重要な順序でした。

  1. isprimerecローカル関数を作成しました。他の誰もそれを呼び出す必要はなく、余分なパラメータを失います。

  2. 関数をトータルにしました。失敗する0理由はなく、負の数で失敗する理由もありません。（技術的に言えば、-pが素数である場合に限り、pは素数です。）

  3. 型署名を追加しました。入るのは良い習慣です。Integer -> Bool、またはを使用Int -> Boolすることも合理的でした。

  4. alllowercaseではなくinterCapsに切り替えました。フォーマットするだけですが、それは慣例です。

私がおそらく物事をより簡潔にすることを除いて。Haskellでは通常手動再帰は不要であり、それを完全に取り除くと、バグは不可能になります。関数は、からのすべての数値が除算2されてn-1いないことnを確認するため、これを直接表現できます。

isPrime :: (Ord a, Integral a) => a -> Bool
isPrime n | abs n <= 1 = False
          | otherwise  = all ((/= 0) . (n `rem`)) [2 .. abs n - 1]

これを1行で次のように書くことができます

isPrime :: (Ord a, Integral a) => a -> Bool
isPrime n = abs n > 1 && all ((/= 0) . (n `rem`)) [2 .. abs n - 1]

しかし、これらの最後の2つの実装のいずれかを見ても驚かないでしょう。そして、私が言ったように、これらの実装の良いところは、タイプミスがこれらの表現で作成できないことです。これは、tの定義内に隠されているallため、誤って間違った値を指定することはできません。

于 2013-02-04T19:04:00.740 に答える
6

問題はこの行にあります

isprimerec n t = if (n `rem` t) == 0 then False else isprimerec n (n-1)

(n - 1)あるべき場所の2番目の引数として使用します(t - 1)。isprimerec _ 1さらに、ケースが欲しいと思います= True。

これが慣用的であるかどうかというあなたのより一般的な質問に関しては、あなたは正しい方向に進んでいると思います。 ghciまともなコマンドラインデバッガがあります。これは、コードをファイルに入れてロードし、コマンドを発行することで見つかりました:break isprimerec。次に、関数を呼び出して、を使用してステップスルーしました:step。

于 2013-02-04T18:45:04.873 に答える
3

毎回else呼び出すため、ブランチは壊れていますisprimerec n (n-1)。isprimerec n (t-1)カウントダウンするには、代わりに書く必要があります。

高階関数allを使用して、これを非常に簡単にすることもできます。

isprime 1 = False
isprime n = all (\t -> n `rem` t /= 0) [2..(n-1)]
于 2013-02-04T18:43:53.543 に答える
1

さて、あなたは2つのバグを持っています：あなたの

isprimerec _ 1 = False
isprimerec n t = if (n `rem` t) == 0 then False else isprimerec n (n-1)

になるはずだった

isprimerec _ 1 = True
isprimerec n t = if (n `rem` t) == 0 then False else isprimerec n (t-1)

または、リスト内包表記を使用して、

isprime n = n>1 && and [ rem n t /= 0 | t <- [n-1,n-2..2] ]

（その余分なパラメーターを内部t化してください、それはとにかく技術的でした！-A-ha、しかしそれは何andですか、あなたは尋ねますか？それはちょうどこの再帰関数のようです、foldr (&&) True :: [Bool] -> Bool。）

しかし、今ではアルゴリズムの大きな欠点が視覚的に明らかになります。間違った順序でテストします。昇順でテストすると、より高速になります。

isprime n = n>1 && and [ rem n t /= 0 | t <- [2..n-1] ]

または、で停止すると、さらに高速になりますsqrt。

isprime n = n>1 && and [ rem n t /= 0 | t <- [2..q] ]
   where  q = floor (sqrt (fromIntegral n))

または、 2の後にオッズのみでテストします（すでに2でテストしているのに、なぜ6でテストするのですか？）：

isprime n = n>1 && and [ rem n t /= 0 | t <- 2:[3,5..q] ]
   where  q = floor (sqrt (fromIntegral n))

または素数だけで（すでに3でテストしたのに、なぜ9でテストするのですか？）：

isprime n = n>1 && and [ rem n t /= 0 | t <- takeWhile ((<= n).(^2)) primes ]
primes = 2 : filter isprime [3..]

そして、なぜ素数をフィルタリングするときに偶数をテストするのですか？そもそも素数を生成しない方が良いのではないでしょうか？

primes = 2 : filter isprime [3,5..]

ただし、常に2isprimeで除算をテストしますが、奇数のみをフィードします。それで、

primes = 2 : 3 : filter (noDivs (drop 1 primes)) [5,7..]
noDivs factors n = and [ rem n t /= 0 | t <- takeWhile ((<= n).(^2)) factors ]

そして、なぜそれらを後でテストして削除するためだけに、3の倍数（つまり）を生成するのですか？[9,15 ..] == map (3*) [3,5..] - 

{-       [5,7..]
    ==   [j+i | i<-[0,2..], j<-[5]]                 -- loop unrolling, 3x:
    ==   [j+i | i<-[0,6..], j<-[5,7,9]]
    == 5:[j+i | i<-[0,6..], j<-[7,9,11]]            
    == 5:[7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43, ...
    \\   [  9,      15,      21,      27,      33,      39,       ...
    ==   [j+i | i<-[0,6..], j<-[  9   ]]
-}
primes = 2:3:5: filter (noDivs (drop 2 primes)) 
         [j+i | i<-[0,6..], j<-[7,  11]]

事前に5の倍数をスキップすることもできます（オイラーのふるいの別のステップとして）：euler (x:xs) = x : euler (xs `minus` map (x*) (x:xs))

--       [j+i | i<-[0, 6..], j<-[7, 11]]            -- loop unrolling, 5x:
--  == 7:[j+i | i<-[0,30..], j<-[11,13,17,19,23,25,29,31,35,37]]
--  \\   [j+i | i<-[0,30..], j<-[               25,      35   ]]

primes = 2:3:5:7: filter (noDivs (drop 3 primes)) 
         [j+i | i<-[0,30..], j<-[11,13,17,19,23,   29,31,   37]]

...しかし、今のところ、それはすでに十分に進んでいます。

于 2013-02-07T19:37:40.323 に答える