|Maintainer||Luke Palmer <firstname.lastname@example.org>|
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. If you are using this as a monad,
I recommendIded that you use the newer weighted-search package instead
(it's also faster).
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.