list - haskell 递增对的无限列表

Question

Create an infinite list pairs :: [(Integer, Integer)] containing pairs of the form (m,n), where each of m and n is a member of [0 ..]. An additional requirement is that if (m,n) is a legit member of the list, then (elem (m,n) pairs) should return True in finite time. An implementation of pairs that violates this requirement is considered a non- solution.

****新鲜编辑感谢您的意见，让我们看看我是否可以取得一些进展****

    pairs :: [(Integer, Integer)]
    pairs = [(m,n) | t <- [0..], m <- [0..], n <-[0..], m+n == t]

像这样的东西？我只是不知道它会在有限的时间内返回 True 。

我觉得这个问题的措辞 elem 不一定是我回答的一部分。只要您调用 (elem (m,n) pairs)它应该返回 true。听起来对吗？

Answer 1

忽略 helper方法，您拥有的列表理解将列出所有对，但元素的顺序是一个问题。你会有无数对像 (0, m)后面是无限多对，如 (1, m) .当然 elem将永远迭代所有 (0, m)对永远不会到达(1, m)或 (2, m)等等

我不知道你为什么有 helper方法——有了它，你只需要建立一个像 [(0,0), (1,1), (2,2), ...] 这样的对列表。因为你已经过滤了m = n .那是要求的一部分吗？

就像@hammar 建议的那样，从 0 = m + n 开始并列出对 (m, n)。然后列出对 (m, n) 其中1 = m + n .然后您的列表将类似于 [(0,0), (0,1), (1,0), (0,2), (1,1), (2,0), ...] .