[Haskell-cafe] Fair diagonals

[Luke Palmer]

On Tue, Nov 3, 2009 at 1:42 PM, Martijn van Steenbergen
<martijn at van.steenbergen.nl> wrote:
> 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)]

I believe you can get what you want using the diagonal function from
Control.Monad.Omega.

product xs ys = [ [ (x,y) | y <- ys ] | x <- xs ]
diag2 xs ys = diagonal (product xs ys)

I think if you separate taking the cartesian product and flattening
it, like this, you might have an easier time wrangling all the
different variants you want.

Luke