[Haskell-cafe] Fair diagonals

[Martijn van Steenbergen]

Dear café,

I am looking for a function that does an N-dimensional diagonal 
traversal. I want the traversal to be fair: the sum of the indices of 
the produced combinations should be non-decreasing. Let me illustrate 
with an example.

The type of a 2-dimensional traversal would look like this:
> diag2 :: [a] -> [b] -> [(a, b)]

The first two arguments are the two half-axes of the grid and the result 
is a fair diagonal traversal of all the points. For example:
>> diag2 [1,2,3] [4,5,6,7]
> [(1,4),(2,4),(1,5),(3,4),(1,6),(2,5),(1,7),(3,5),(2,6),(2,7),(3,6),(3,7)]

Of course the function should work on infinite lists:
>> diag2 [1..] [1..]
> [(1,1),(2,1),(1,2),(3,1),...

Or a combination of finite and infinite lists:
>> diag2 [1,2] [1..]
> [(1,1),(2,1),(1,2),(1,3),(2,2),(1,4),...

Notice that in each case the sum of the pairs (which can seen as indices 
in these particular examples) are non-decreasing:
>> let sums = map (uncurry (+))
>> sums $ diag2 [1,2,3] [4,5,6,7]
> [5,6,6,7,7,7,8,8,8,9,9,10]
>> sums $ diag2 [1..] [1..]
> [2,3,3,4,4,4,5,5,5,5,6,...
>> sums $ diag2 [1,2] [1..]
> [2,3,3,4,4,5,5,6,6,7,7,...

Similarly for 3 dimensions the type would be:
> diag3 :: [a] -> [b] -> [c] -> [(a, b, c)]

For N dimensions we have to sacrifice some generality and ask all axes 
to be of the same type and produce lists instead of tuples, but I'm 
perfectly happy with that:
> diagN :: [[a]] -> [[a]]

I have implemented diag2 and diag3 [1] but noticed that the function 
bodies increase in size exponentially following Pascal's triangle and 
have no clue how to generialize to N dimensions. Can you help me write 
diagN?

Bonus points for the following:
* An infinite number of singleton axes produces [origin] (and finishes 
computing), e.g. forall (infinite) xs. diagN (map (:[]) xs) == map (:[]) xs
* For equal indices, the traversal biases to axes that are occur early 
in the input (but I don't know how to formalize this).
* The implementation shows regularity and elegance.

Many thanks,

Martijn.

[1] http://hpaste.org/fastcgi/hpaste.fcgi/view?id=11515