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.