|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.
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.