[Haskell-cafe] Fair diagonals
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
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.)
More information about the Haskell-Cafe
mailing list