|Maintainer||Luke Palmer <email@example.com>|
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.
More precisely, if
x appears at a finite index in
y appears at a finite index in
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
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.
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.
n <= (i+j)*(i+j+1)/2 + j.