[Haskell-cafe] Re: Fair diagonals

Louis Wasserman wasserman.louis at gmail.com
Thu Nov 5 16:04:35 EST 2009


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 at gmail.com
http://profiles.google.com/wasserman.louis


On Wed, Nov 4, 2009 at 4:38 AM, Martijn van Steenbergen <
martijn at 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.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20091105/33771970/attachment-0001.html


More information about the Haskell-Cafe mailing list