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?
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 courseelem
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 onm = 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) where1 = m + n
. Then your list will look like[(0,0), (0,1), (1,0), (0,2), (1,1), (2,0), ...]
.I first posted
Which, I believed answered the three conditions set by the professor. But hammar pointed out that if I chose this list as an answer, that is, the list of pairs of the form (t, t+1), then I might as well choose the list
Well, both of these do seem to answer the professor's question, considering there seems to be no mention of the list having to contain all combinations of [0..] and [0..].
That aside, hammer helped me see how you can list all combinations, facilitating the evaluation of elem in finite time by building the infinite list from finite lists. Here are two other finite lists - less succinct than Hammar's suggestion of the diagonals - that seem to build all combinations of [0..] and [0..]:
which construct the edges (t, 0..t) (0..t, t), and
which build clockwise spirals of length 'size' squared, superimposed on hammar's diagonals algorithm.
The helper function ensures that pairs is a list of the form
[ (0,0) , (1,1) , (2,2) ... ]
.So
elem ( m , n )
pairs can be implemented as:This is a constant time implementation.