2011-05-10 4 views
2

リスト内包ハスケルELEM機能

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

+1

アドバイス:Haskellのプラットフォームをインストールし、ここで入手可能:http://hackage.haskell.org/platform/ – Tener

+2

'' paar'の意味がどういうかははっきりしていません。このリストはどのように見えますか? elem関数は実際には(答えがTrueの間は)無限リストに作用しますが、リストを生成する方法は問題を引き起こしています。 –

答えて

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 

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

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 
+0

問題は解決しましたが、まだ問題はあります。リスト内で何かを探しているなら、あなたは永遠に続くでしょう。停止するのが安全であることを知っている 'elem'の亜種が必要です。 – hammar

+0

@ハマー:そうです。 – rampion

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

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

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

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

関連する問題