list - 无限制列表的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

我的错误

main>elem(9, 9801) 测试

错误 - 垃圾收集未能回收足够的空间

我如何用康托尔的对角线参数来实现这一点？

谢谢

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

通过使用对角路径遍历所有可能的值，我们保证我们在有限的时间内到达每个有限的点（尽管有些点仍然在内存的范围之外）。

然而，正如 hammar 在他的评论中指出的那样，这还不够，因为仍然需要无限的时间才能得到False答案。

但是，我们对 paar 的元素有一个顺序，即(3*a,b^2)出现在(3*c,d^2)when 之前a + b < c + d。所以要确定给定的对(x,y)是否在paar，我们只需要检查对(p,q)while 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