haskell infinite list of incrementing pairs

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.

****Fresh edit Thank you for the comments, Lets see if I can make some progress****

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

Something like this? I just don't know where it's going to return True in finite time.

I feel the way the question is worded elem doesn't have to be part of my answer. Just if you call (elem (m,n) pairs) it should return true. Sound right?

Answer 1

Ignoring the helper method, the list comprehension you have will list out all pairs but the order of elements is a problem. You'll have a infinitely many pairs like (0, m) which are followed by infinitely many pairs like (1, m). Of course elem will forever iterate all the (0, m) pairs never reaching (1, m) or (2, m) etc.

I'm not sure why you have the helper method -- with it, you are only building a list of pairs like [(0,0), (1,1), (2,2), ...] because you've filtered on m = n. Was that part of the requirements?

Like @hammar suggested, start with 0 = m + n and list out the pairs (m, n). Then list pairs (m, n) where 1 = m + n. Then your list will look like [(0,0), (0,1), (1,0), (0,2), (1,1), (2,0), ...].