Luke Palmer wrote:

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.

Note that Control.Monad.Omega is not a monad. The law of associativity is broken, at least in a direct sense. Regards, apfelmus -- http://apfelmus.nfshost.com

Sjoerd Visscher wrote:

I believe this does what you want:

<code>

The attached code should be more efficient, since it doesn't use integer indices. Note that this is just a 'level' monad: the list is stratified into levels, when combining two levels, the level of the result is the sum of the levels of the inputs. map (map sum) . runDiags . traverse each $ [[1..], [1..], [1..]] [[3],[4,4,4],[5,5,5,5,5,5],[6,6,6,6,6,6,6,6,6,6],[7,7,7,7,7,7,7,7,7,7,7,... I looked on hackage but I was surprised that I couldn't find this simple monad. The package level-monad does look very similar, only it uses a different list type for the representation. By the way, it seems Omega intentionally doesn't use this design. To quote the documentation "... a breadth-first search of a data structure can fall short if it has an infinitely branching node. Omega addresses this problem ..." Twan

Sjoerd Visscher wrote:

diagN = bfs . mapM fromList

This is awesome guys, thanks so much. Martijn.

Henning Thielemann wrote:

On Wed, 4 Nov 2009, Sjoerd Visscher wrote:

...

On Nov 4, 2009, at 3:21 PM, Twan van Laarhoven wrote:

I looked on hackage but I was surprised that I couldn't find this simple monad. The package level-monad does look very similar, only it uses a different list type for the representation.

indeed, level-monad works as well:

import Control.Monad.Levels import Data.FMList (fromList)

diagN = bfs . mapM fromList

Can someone explain the difference between control-monad-omega and level-monad?

So from what I understand this is the difference: Omega is biased towards the lower dimensions while Levels treats all dimensions equally, or at least more equally. You can formalize the latter by saying: the sums of the indices should be non-decreasing. From Omega's documentation I understand this is on purpose: "(...) Likewise, a breadth-first search of a data structure can fall short if it has an infinitely branching node. Omega addresses this problem by using a "diagonal" traversal that gracefully dissolves such data." However, I can't verify this:

runOmega . mapM each $ map (:[]) [1..] *** Exception: stack overflow

Or maybe I misunderstood Omega's documentation. Martijn.

Luke Palmer wrote:

On Fri, Nov 6, 2009 at 3:06 AM, Martijn van Steenbergen wrote:

...

"(...) Likewise, a breadth-first search of a data structure can fall short if it has an infinitely branching node. Omega addresses this problem by using a "diagonal" traversal that gracefully dissolves such data."

However, I can't verify this:

...

runOmega . mapM each $ map (:[]) [1..] *** Exception: stack overflow Or maybe I misunderstood Omega's documentation.

You are asking for the impossible.

Oh, and I realise now that this has been mentioned two times before already in this thread. *hangs head in shame* Are there examples of infinitely branching nodes where it is possible to give some output? Otherwise I'm not sure what the documentation is saying. Martijn.

Hello, Sjoerd's intuition to reuse a nondeterminism monad in order to implement fair diagonalisation was insightful and one can implement a diagonalisation function that satisfies the property diagonal (map (:[]) xs) == xs for all (even infinite) lists `xs` using the level monad. Here is how. Start with a convoluted definition of `concat` that uses a list comprehension which does nothing: flatten :: [[a]] -> [a] flatten xss = concat [ [ x | x <- xs ] | xs <- xss ] Now, generalise this definition to an arbitrary nondeterminism monad by translating list comprehension syntax into do notation: merge :: MonadPlus m => [[a]] -> m a merge xss = join(do xs<-anyOf xss;return(do x<-anyOf xs;return x)) The `anyOf` function is a generalisation of `Data.FMList.fromList` and `Control.Monad.Omega.each` that is not specific to a specific nondeterminism monad: anyOf :: MonadPlus m => [a] -> m a anyOf = msum . map return In the list monad `merge` is equivalent to `flatten` but different monads merge the lists in different orders. It turns out that `merge` implements diagonalisation in the level monad. The pointfree program [1] knows how to simplify the body of `merge`: # pointfree -v "\xss->join(anyOf xss>>=\xs->return(anyOf xs>>=\x-

return x))" Transformed to pointfree style: join . flip ((>>=) . anyOf) (return . flip ((>>=) . anyOf) return) Optimized expression: join . flip ((>>=) . anyOf) (return . flip ((>>=) . anyOf) return) join . (>>= return . flip ((>>=) . anyOf) return) . anyOf join . (return . flip ((>>=) . anyOf) return =<<) . anyOf join . (return . (>>= return) . anyOf =<<) . anyOf join . (return . (return =<<) . anyOf =<<) . anyOf join . (return . id . anyOf =<<) . anyOf join . (return . anyOf =<<) . anyOf join . (anyOf `fmap`) . anyOf (anyOf =<<) . anyOf

Now, specialise for the level monad to get fair diagonalisation: diagonal :: [[a]] -> [a] diagonal = bfs . (>>= fromList) . fromList A quick check shows that this function really works for infinite lists: ghci> take 10 $ diagonal [[(x,y) | y <- [1..]] | x <- [1..]] [(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),(1,4),(2,3),(3,2),(4,1)] SmallCheck [2] helps to recognise that the omega monad produces a different order on some inputs: ghci> bfs (anyOf [[1,2,3],[],[],[4]] >>= anyOf) [1,2,3,4] ghci> runOmega (anyOf [[1,2,3],[],[],[4]] >>= anyOf) [1,2,4,3] In this example, each number n is on the nth diagonal of the corresponding matrix. Unlike in the omega monad, `merge` faithfully implements diagonalisation in the level monad. Cheers, Sebastian [1]: http://hackage.haskell.org/package/pointfree [2]: http://hackage.haskell.org/package/smallcheck -- Underestimating the novelty of the future is a time-honored tradition. (D.G.)

On Wed, Nov 04, 2009 at 07:01:50PM +0100, Sjoerd Visscher wrote:

To: Haskell Cafe From: Sjoerd Visscher Date: Wed, 4 Nov 2009 19:01:50 +0100 Subject: Re: [Haskell-cafe] Fair diagonals (code golf)

The code by Twan can be reduced to this:

diagN = concat . foldr f [[[]]]

f :: [a] -> [[[a]]] -> [[[a]]] f xs ys = foldr (g ys) [] xs

g :: [[[a]]] -> a -> [[[a]]] -> [[[a]]] g ys x xs = merge (map (map (x:)) ys) ([] : xs)

merge :: [[a]] -> [[a]] -> [[a]] merge [] ys = ys merge xs [] = xs merge (x:xs) (y:ys) = (x++y) : merge xs ys

But my feeling is that this can still be simplified further. Or at least refactored so it is clear what actually is going on!

i wrote another solution: diag2 xs ys = join . takeWhile (not . null) . map f $ [1..] where f i = zip xs' ys' where xs' = take i $ drop (i - length ys') xs ys' = reverse $ take i ys diag [] = [] diag [q] = [q] diag qs = foldr f (map (:[]) $ last qs) (init qs) where f q' = map (uncurry (++)) . diag2 (map (:[]) q') diag is the recursion step over the dimensions; diag2 is the base case with two dimensions. i can see that it's less efficient on (partially) finite inputs, since i keep dropping increasing prefixes of xs and ys in the local f in diag2), and there are probably other issues. but it was fun staring at this problem for a while. :) matthias