ELEM機能

Question

リスト内包ハスケル

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

=除数3 B =平方

要素は衡平な順序によって構築されなければなりません。

テスト> elemは（9、9801）は

私のエラー

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

ERROR真でなければならない - ガベージコレクションは、十分なスペース

を取り戻すために失敗しました

これをCantorの対角引数でどのように実装できますか？

あなたの目標はここですが、ここにコードが吹く理由何THX

Answer 1

ここで（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 

すべての可能な値を反復処理する斜めのパスを使用することにより、我々は有限時間内に各有限地点に到達することを保証します（ただし、いくつかの点はまだメモリの範囲外です）。

hammarは彼のコメントで指摘しているとおり、 にはまだFalseの回答を得るのに十分な時間がかかるため、これでは不十分です。

ただし、(3*c,d^2)の前には(3*a,b^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 

Answer 2

かなりわかりません。

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という結果をもたらし、あなたが説明したクラッシュにつながります。

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

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

または、無限リストを使用した直線上の線形検索以外の検索戦略を見つけます。