Sebastian Fischer sebf at informatik.uni-kiel.de
Fri Nov 6 17:21:00 EST 2009

```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

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  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  helps to recognise that the omega monad produces a
different order on some inputs:

ghci> bfs (anyOf [[1,2,3],[],[],] >>= anyOf)
[1,2,3,4]
ghci> runOmega (anyOf [[1,2,3],[],[],] >>= 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