How to generate a list of all the pairs of natural numbers

Apr 8, 2010

The obvious, but incorrect, method: [(x,y) | x <- [1..], y <- [1..]]. Incorrect, of course, because this stream will never get even as far as (2,1); after x gets the value 1, y must run through all the natural numbers before x gets the value 2. The lesson is that the value of y has to be constrained by the value of x, so that one actual solution is [(x-y,y+1) | x <- [1..], y <- [0..x-1]], which solves the problem in that there is no particular pair the stream will never generate even though, plainly, it will never generate all of the pairs.

I find I can't shake the feeling that if one knew extremely well the original ten sonnets that form the basis of Queneau's combinatoric trick (knew them as perhaps Queneau and his translators themselves did) one would thereby also know all hundred trillion sonnets generable from them, and not just in the sense that no given generated sonnet would be a surprising.