-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A breadth-first list monad.
--   
--   A monad for enumerating sets: like the list monad but breadth-first.
@package control-monad-omega
@version 0.3.1


-- | 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 <tt>liftM2 (,) [0..] [0..]</tt> gets "stuck" generating
--   tuples whose first element is zero, <tt>"runOmega" $ liftM2 (,)
--   ("each" [0..]) ("each" [0..])</tt> generates all pairs of naturals.
--   
--   More precisely, if <tt>x</tt> appears at a finite index in
--   <tt>xs</tt>, and <tt>y</tt> appears at a finite index in <tt>f x</tt>,
--   then <tt>y</tt> will appear at a finite index in <tt>each xs &gt;&gt;=
--   f</tt>.
--   
--   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 <tt>runOmega</tt>
--   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. If you are using this as a
--   monad, I recommendIded that you use the newer weighted-search package
--   instead (it's also faster).
module Control.Monad.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 <tt>xs !! i !! j == diagonal xs !!
--   n</tt>. In particular, <tt>n &lt;= (i+j)*(i+j+1)/2 + j</tt>.
diagonal :: [[a]] -> [a]
data Omega a
runOmega :: Omega a -> [a]
each :: [a] -> Omega a
instance GHC.Base.Functor Control.Monad.Omega.Omega
instance GHC.Base.Monad Control.Monad.Omega.Omega
instance GHC.Base.MonadPlus Control.Monad.Omega.Omega
instance GHC.Base.Applicative Control.Monad.Omega.Omega
instance GHC.Base.Alternative Control.Monad.Omega.Omega
instance Data.Foldable.Foldable Control.Monad.Omega.Omega
instance Data.Traversable.Traversable Control.Monad.Omega.Omega
