1

インターネットでこのソリューションを見つけましたが、それを理解するための助けが必要です:

isPrime' :: Integer -> Bool
isPrime' n = foldr (\x acc -> (n `rem` x) /= 0 && acc) True primes
    where primes = 2 : filter isPrime' [3,5..]

いくつかのこと：

私の理解では、フォールド関数のアキュムレータが a の場合Boolean、ラムダ関数自体に設定する必要があります。何かのようなもの：

(\x acc -> if (n `rem` x /= 0) then False else acc) True primes

しかし、ここではそうではありません。

また、使用されている範囲にprimesは終了番号がありません。これが機能する理由は Haskell の遅延評価によるものであることはわかっていますが、ここではどのように機能しているのでしょうか?

最後に、この関数は適切なブール値を返すようには見えません。素数とは、自身と 1 以外に約数がないものです。

(\x acc -> if (n `rem` x) == 0 then False else acc) True primes

私は完全に混乱しています。私を助けてください。

4

3 に答える 3

1

持つ

primes = [p1, p2, p3, ..., pn, ...]

計算する

isPrime' n = foldr (\x acc -> (n `rem` x) /= 0 && acc) True primes

計算しているかのように

isPrime' n = rem n p1 /= 0 && (
             rem n p2 /= 0 && (
             rem n p3 /= 0 && (
             ..........
             rem n pk /= 0 && (
             ..........          ..... ))))

複合ns の場合、これは機能しremます。式の 1 つが 0 になり、不等式が false になり、式全体も false になり&&ます。

素数ns の場合、これは問題を引き起こします:素数の中の素数自体remに到達するまで、素数の定義により、どの式も 0 になりません。p_i == nしかし、まだ素数であることが検出されていないため、まだそこにはありません。ちょうど今それを行っているところです。それが素数かどうかをテストするには、それが素数であることを知る必要があります。これは明らかに悪い状況です。

primesまだ存在しない値が要求されます。これは「ブラックホール」として知られています。エラーが発生し、計算が中止されます (またはスタックします)。

別の言い方をすれば、あたかも定義のように

primes = 2 : filter isPrime' [3,5..]

として定義されました

primes = 2 : [ n | n <- [3,5..]
                 , and [rem n p /= 0 | p <- takeWhile (< n) primes]]

n問題は、が素数のときに停止するには、 in以上takeWhile (< n)の素数に到達する必要があることですが、まだ到達していません。「ブラックホール」。pnprimes

有名な「ふるい」コードは、ワークフローを「転置」することでこの問題を回避します。

primes = map head . iterate (\(x:xs)-> filter ((/=0).(`rem`x)) xs) $ [2..]

したがって、計算の非効率性（コードのより小さな問題）を保持しながら機能させ、不必要に多くの素数で候補をテストします（各素数は、その平方根を超えていないものだけではなく、先行するすべての素数によってテストされます）。不必要に遅い。

これは、テストを適切に早期に停止することで軽減されます。

primes = 2 : [ n | n <- [3,5..]
                 , and [rem n p /= 0 | p <- takeWhile ((<= n).(^2)) primes]]

これは、あなたの定義の観点から言えば、

isPrime' n = p1*p1 > n || rem n p1 /= 0 && (
             p2*p2 > n || rem n p2 /= 0 && (
             p3*p3 > n || rem n p3 /= 0 && (
             ..........
             pk*pk > n || rem n pk /= 0 && (
             ..........          ..... ))))

これをベースの定義として書き留めることができますfoldr（これは別の回答で見ることができます ここ ）。

于 2015-08-04T23:10:35.910 に答える
0

表現

(n `rem` x) /= 0

明らかに Bool の結果を生成します。パラメータaccはすでにブール値です。そう

(n `rem` x) /= 0 && acc

は、2 つの Bool 値の論理 AND であり、明らかに Bool の結果を生成します。混乱はどこにありますか？

入力リストは無限で、奇数のみで構成されています。有限数の値のみを調べて結果を生成できる限り、怠惰はすべてをうまくします。

于 2015-08-04T16:16:05.840 に答える