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