When we work with infinite lists in Haskell, one important problem is:

Problem. Construct a list which generates all the distinct ordered pairs of natural numbers.

So, we want a method to generate the set: {(0,0), (0,1),(0,2),…, (1,0), (1,1),(1,2),…} etc. Or, alternatively, the cartesian product NxN, where N stands for the set of natural numbers {0,1,2,3,…} .

One approach would be to define the list L = [(x,y) | xwithout ever enumerating the pairs (1,0),(1,1),…. In this way, we would only produce the list L=[(0,y) | y<-[0..]].

The second diagonal principle.

Let’s write the ordered pairs we want to obtain as in the image:

We observe that, by cutting the enumerated pairs of natural numbers with the diagonals d0,d1,d2,d3,d4,d5,.. we obtain all the distinct pairs (x,y), with x and y natural numbers.

At a closer look, lets see the properties of the pairs on the diagonal d3 = {(0,3),(1,2),(2,1),(3,0)}. We observe that this pairs have the sum of elements 3. If we note (x,y) as a pair of d3, we have in consequence x+y = 3. But is sufficient to know x in order to obtain y=3-x. So our (x,y) is, actually, the pair (x,3-x).

As far as this observation goes, we obtained d3 = {(x,3-x) | x In the same way, d4 = {(x,4-x) | x<-[0..4]}.
The obvious generalization is: dm = {(x,m-x) | x<-[0..m]}.
If m is made to go through all the natural numbers [0..], we obtain all the distinct pairs (x,y) of natural numbers.

Thus, our list of all distinct pairs of natural numbers will be constructed like this:
L = [(x,m-x) | m<-[0..], x<-[0..m]], where [0..] is the infinite list of natural numbers [0,1,2,3,4,5,6,…].

Remark. You can apply the same diagonal technique to pairs constructed from elements which can be enumerated in a total order. So, you can extend the principle to obtain all the distinct triples of natural numbers (x,y,z). Also, the list of ordered tuples of natural numbers can be used to obtain solutions to diofantic equations with certain boundary conditions.

I hope that you understood by now how important are general applicable techniques in programming as in mathematics. Without such techniques, solutions to the problems like finding all pairs of natural numbers would be much harder to find empirically.

Constantin Liculescu


Share Button