[Haskell-cafe] Fair diagonals
Martijn van Steenbergen
martijn at van.steenbergen.nl
Tue Nov 3 15:42:56 EST 2009
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
More information about the Haskell-Cafe
mailing list