I figured out an inductive approach as follows, which lets you derive stripeN from stripe(N-1). This could be TemplateHaskell'd if you have a bound on N; I'm still trying to figure out a type-magical alternative. Suppose stripe(N-1) :: x -> [b] -> [c] Then stripeN :: (a -> [b]) -> x -> [a] -> [[c]] stripeN f x [] = [] stripeN f x (a:as) = case stripe(N-1) x (f a) of [] -> stripeN f x as (b:bs) -> [b]:zipCons bs (stripeN f x as) and then diagN is obtained by applying concat an appropriate number of times. It's fair. The real-question is how to type-magically work it for arbitrarily many coordinates... Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis On Wed, Nov 4, 2009 at 4:38 AM, Martijn van Steenbergen < martijn@van.steenbergen.nl> wrote:

Louis Wasserman wrote:

...

+1 on Control.Monad.Omega. In point of fact, your diagN function is simply

diagN = runOmega . mapM Omega

You'll find it an interesting exercise to grok the source of Control.Monad.Omega, obviously, but essentially, you're replacing concatMap with a fair (diagonal) traversal order version.

Thanks for the replies!

I've looked at Omega but it's not fair enough. The sums of the indices are not non-decreasing:

map sum $ runOmega . mapM each $ [[1..], [1..], [1..]] [3,4,4,4,5,5,5,5,6,6,5,6,6,7,7,5,6,7,7,8,8,6,6,7,8,8,9,9,6,7,...

Is there another way to use Omega that meets this (very important) criterion or is Omega not the right tool here?

Thanks,

Martijn.