2

リスト内包表記haskell

 paar = [(a,b) | a<-[a | a<-[1..], mod a 3 == 0], b<-[b*b | b<-[1..]]]

a=除数3b=正方形

要素は、公平な順序で構築する必要があります。

テスト>elem（9、9801）はTrueである必要があります

私のエラー

メイン>elem（9、9801）テスト

エラー-ガベージコレクションが十分なスペースを再利用できません

カントールの対角論でこれをどのように実装できますか？

どうも

4

2 に答える 2

7

ここでの目標はよくわかりませんが、コードが爆発する理由は次のとおりです。

Prelude> let paar = [(a,b) | a<-[a | a<-[1..], mod a 3 == 0], b<-[b*b | b<-[1..]]]
Prelude> take 10 paar
[(3,1),(3,4),(3,9),(3,16),(3,25),(3,36),(3,49),(3,64),(3,81),(3,100)]

(3, ?)他のどのペアよりも先にすべてのペアを生成していることに注意してください。このelem関数は、このリストを最初から直線的に検索することで機能します。ペアの数は無限であるため、(3, ?)ペアに到達することはありません(9, ?)。

さらに、コードはおそらくpaarどこかに保持されており、ガベージコレクションが妨げられています。その結果、elem (9, 9801) paar無限の時間だけでなく無限のスペースが必要になり、説明したクラッシュが発生します。

最終的には、問題を解決するために別のアプローチを取る必要があります。たとえば、次のようなものです。

elemPaar :: (Integer, Integer) -> Bool
elemPaar (a, b) = mod a 3 == 0 && isSquare b
    where isSquare = ...

または、無限のリストを直線的に検索する以外の検索戦略を考え出すこともできます。

于 2011-05-10T16:35:59.790 に答える
4

同じリストの別の順序は次のとおりです（hammarの提案による）：

-- the integer points along the diagonals of slope -1 on the cartesian plane,
-- organized by x-intercept
-- diagonals = [ (0,0), (1,0), (0,1), (2,0), (1,1), (0,2), ...
diagonals = [ (n-i, i)  | n <- [0..], i <- [0..n] ]

-- the multiples of three paired with the squares
paar = [ (3*x, y^2) | (x,y) <- diagonals ]

そして実際に：

ghci> take 10 diagonals
[(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0),(2,1),(1,2),(0,3)]
ghci> take 10 paar
[(0,0),(3,0),(0,1),(6,0),(3,1),(0,4),(9,0),(6,1),(3,4),(0,9)]
ghci> elem (9, 9801) paar
True

対角パスを使用してすべての可能な値を反復処理することにより、有限時間内に各有限ポイントに到達することを保証します（ただし、一部のポイントはまだメモリの境界外にあります）。

しかし、ハマーが彼のコメントで指摘しているように、False答えを得るにはまだ無限の時間がかかるので、これは十分ではありません。

ただし、paarの要素には順序があります。つまり、いつ の(3*a,b^2)前に来るかです。したがって、特定のペアがにあるかどうかを判断するには、の間にペアをチェックするだけで済みます。(3*c,d^2)a + b < c + d(x,y)paar(p,q)p/3 + sqrt q <= x/3 + sqrt y

数字の使用を避けるためFloatingに、少し緩い条件を使用できますp <= x || q <= y。確かにをp > x && q > y意味するp/3 + sqrt q > x/3 + sqrt yので、これには可能な解決策が含まれ、終了することが保証されています。

したがって、このチェックインを作成できます

-- check only a finite number of elements so we can get a False result as well
isElem (p, q) = elem (p,q) $ takeWhile (\(a,b) -> a <= p || b <= q) paar

そしてそれを使用してください：

ghci> isElem (9,9801)
True
ghci> isElem (9,9802)
False
ghci> isElem (10,9801)
False
于 2011-05-10T17:09:26.767 に答える