无限制列表的 elem 函数

Question

列表理解 haskell

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

a = 除数 3 b = 正方形

元素必须按公平顺序构造。

测试 >elem (9, 9801) 必须为 True

我的 Error

Main> elem (9, 9801) 测试

错误 - 垃圾收集无法回收足够的空间

如何使用 Cantor 的对角线参数来实现这一点？

谢谢

Answer 1

不太确定你的目标是什么，但这就是你的代码崩溃的原因。

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 = ...

或者找出一些其他搜索策略，而不是通过无限列表进行直接线性搜索。

Answer 2

这是同一个列表的另一种排序（根据 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