Copyright	(c) Luke Palmer 2008
License	Public Domain
Maintainer	Luke Palmer <lrpalmer@gmail.com>
Stability	experimental
Portability	portable
Safe Haskell	Safe
Language	Haskell98

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.

Warning: Omega is only a monad when the results of runOmega 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).

Synopsis

Documentation

diagonal :: [[a]] -> [a] #

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.

data Omega a #

Instances

Monad Omega #
Methods (>>=) :: Omega a -> (a -> Omega b) -> Omega b # (>>) :: Omega a -> Omega b -> Omega b # return :: a -> Omega a # fail :: String -> Omega a #
Functor Omega #
Methods fmap :: (a -> b) -> Omega a -> Omega b # (<$) :: a -> Omega b -> Omega a #
Applicative Omega #
Methods pure :: a -> Omega a # (<>) :: Omega (a -> b) -> Omega a -> Omega b # (>) :: Omega a -> Omega b -> Omega b # (<*) :: Omega a -> Omega b -> Omega a #
Foldable Omega #
Methods fold :: Monoid m => Omega m -> m # foldMap :: Monoid m => (a -> m) -> Omega a -> m # foldr :: (a -> b -> b) -> b -> Omega a -> b # foldr' :: (a -> b -> b) -> b -> Omega a -> b # foldl :: (b -> a -> b) -> b -> Omega a -> b # foldl' :: (b -> a -> b) -> b -> Omega a -> b # foldr1 :: (a -> a -> a) -> Omega a -> a # foldl1 :: (a -> a -> a) -> Omega a -> a # toList :: Omega a -> [a] # null :: Omega a -> Bool # length :: Omega a -> Int # elem :: Eq a => a -> Omega a -> Bool # maximum :: Ord a => Omega a -> a # minimum :: Ord a => Omega a -> a # sum :: Num a => Omega a -> a # product :: Num a => Omega a -> a #
Traversable Omega #
Methods traverse :: Applicative f => (a -> f b) -> Omega a -> f (Omega b) # sequenceA :: Applicative f => Omega (f a) -> f (Omega a) # mapM :: Monad m => (a -> m b) -> Omega a -> m (Omega b) # sequence :: Monad m => Omega (m a) -> m (Omega a) #
Alternative Omega #
Methods empty :: Omega a # (<\|>) :: Omega a -> Omega a -> Omega a # some :: Omega a -> Omega [a] # many :: Omega a -> Omega [a] #
MonadPlus Omega #
Methods mzero :: Omega a # mplus :: Omega a -> Omega a -> Omega a #

runOmega :: Omega a -> [a] #

each :: [a] -> Omega a #