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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
