Control.Monad.Omega

A monad for enumerating sets: like the list monad, but "breadth-first".

It addresses the problem seen when trying to generate the list of all pairs of naturals with [ (x,y) | x <- [0..], y <- [0..] ], which is broken since the first element of every reachable pair will be 0.

Using Omega this can be written

 pairs = runOmega $ do
     x <- each [0..]
     y <- each [0..]
     return (x,y)

More precisely, if x appears at a finite index in xs, and y appears at a finite index in f x, then y will appear at a finite index in each xs >>= f.

Documentation

diagonal :: [[a]] -> [a]

This is the hinge algorithm of the Omega monad, exposed because it can be useful on its own. Joins a list of lists with the property that for every x y there is an n such that xs !! x !! y == diagonal xs !! n.

data Omega a

Instances

Monad Omega

Functor Omega

Applicative Omega

Foldable Omega

Traversable Omega

runOmega :: Omega a -> [a]

each :: [a] -> Omega a