2

そこで、単純な試行除算を使用して Haskell を学習するのに役立つ素数のリストを作成しています (この言語に慣れるまで、手の込んだものは必要ありません)。次のコードを使用しようとしています。

primes = 2 : [ x | x <- [3..], all (\p -> (mod x p) /= 0) primes]

これはエラーなしでロードされます。でも：

>take 2 primes
[2ERROR - C stack overflow

ネストされたリスト内包表記で同じことを試しました。うまくいきません。再帰呼び出しが多すぎると思いますが、素数を 1 つしか計算していない場合はそうではありません。私の考えでは、遅延評価はそれを次のようにする必要がtake 2 primesあります。

primes = 2 : [ 3 | all (\p -> (mod 3 p) /= 0) [2] ]

mod 3 2 == Trueそれほど多くの計算を必要としないのはどれall (\p -> (mod 3 p) /= 0) == Trueですかtake 2 primes == [2, 3]? これが機能しない理由がわかりません。関数型プログラミングの黒魔術に精通した誰かが私を助けてくれることを願っています...

それが違いを生むなら、これはHUGSにあります。

編集-私はこの解決策を思いつくことができました(きれいではありません):

primes = 2 : [ x | x <- [3..], all (\p -> (mod x p) /= 0) (takeWhile (<= (ceiling (sqrt (fromIntegral x)))) primes)]

EDIT2- HUGS または GHCi を介して解釈すると、プログラムは正常に動作しますが、GHC でコンパイルしようとすると、出力されますtest: <<loop>>。誰が問題が何であるか知っていますか？

4

3 に答える 3

7

ハグはこれを行うべきではありませんが、とにかくコードが壊れているので問題ありません。検討：

primes = 2 : [ x | x <- [3..], all (\p -> (mod x p) /= 0) primes]

3が素数であるかどうかをどのように判断しますか. そうですねmod 3 2 == 0？いいえmod 3 ??? == 0。おっとっと！素数の 2 の次の要素は? わかりませんが、計算しようとしています。未満xのすべての p素数がテストされたら、3 (またはその他の ) を追加する順序制約を追加する必要があります。elemsqrt x

于 2011-03-04T21:31:12.293 に答える
3

すべてのドキュメントには、「結果が真になるには、リストが有限でなければならない」と書かれています http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:all

于 2011-03-04T22:08:06.720 に答える
0

以前の回答では、元の理解が機能しなかった理由は説明されていましたが、機能するものを作成する方法は説明されていませんでした。

以下は、すべての素数を再帰的に、遅延して (効率的ではありませんが) 計算するリスト内包表記です。

let primes = [x | x <- 2:[3,5..], x == 2 || not (contains (\p -> 0 == (mod x p)) (takeWhile (\b -> (b * b) < x) primes))]

明らかに、すべての素数に対して mod xp をチェックする必要はありません。潜在的な素数の sqrt よりも小さい素数に対してのみ行う必要があります。それが takeWhile の目的です。this(\b -> (b * b) < x)は同等である必要があります(< sqrt x)が、Haskell 型システムはそれを好みませんでした。

これx == 2により、要素をリストに追加する前に takeWhile がまったく実行されなくなります。

于 2011-07-11T02:14:47.617 に答える