Control.Monad.Omega

A monad for enumerating sets: like the list monad, but impervious to infinite descent.

A depth-first search of a data structure can fail to give a full traversal if it has an infinitely deep path. 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.

So while liftM2 (,) [0..] [0..] gets "stuck" generating tuples whose first element is zero, runOmega $ liftM2 (,) (each [0..]) (each [0..]) generates all pairs of naturals.

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.

This monad gets its name because it is a monad over sets of order type omega.

Warning: Omega is only a monad when the results of runOmega are interpreted as a set; that is, a valid transformation according to the monad laws may change the order of the results. However, the same set of results will always be reachable.

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 i j there is an n such that xs !! i !! j == diagonal xs !! n. In particular, n <= (i+j)*(i+j+1)/2 + j.

data Omega a

Instances

Monad Omega

Functor Omega

MonadPlus Omega

Applicative Omega

Foldable Omega

Traversable Omega

runOmega :: Omega a -> [a]

each :: [a] -> Omega a