ELEM功能

Question

列表理解的Haskell

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

一個除數= 3 B =平方

元件必須由公平順序來構建。

測試> ELEM（9，9801）必須爲True

我的錯誤

首頁> ELEM（9，9801）測試

錯誤 - 垃圾收集不能回收足夠的空間

我怎樣才能用Cantor的對角參數來實現？

THX

Answer 1

下面是同一列表的替代排序（由哈馬爾的建議）：

-- 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答案。

但是，我們有一個關於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 

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不僅會佔用無限的時間，而且會造成無限的空間，導致您描述的崩潰。

最終，您可能需要採取另一種方法來解決您的問題。例如，像這樣：

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

或可選擇地通過無限的列表搞清楚比直線上升線性搜索一些其他搜索戰略。