Portability | portable |
---|---|
Stability | experimental |
Maintainer | Luke Palmer <lrpalmer@gmail.com> |
Control.Monad.Omega
Description
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.
Documentation
diagonal :: [[a]] -> [a]Source
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
.
Instances