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


-- | A list monad transformer and related functions.
--   
--   A list monad transformer and a generic List class. Consumer and
--   Generator monad transformers to create and iterate <a>ListT</a>s in a
--   manner similar to Python generators. A Tree module for searching and
--   pruning trees expressed as <a>List</a>s whose underlying monad is also
--   a List.
@package generator
@version 0.5


-- | A list monad transformer / a monadic list.
--   
--   Monadic list example: A program which reads numbers from the user and
--   accumulates them.
--   
--   <pre>
--   import Control.Monad.ListT (ListT)
--   import Data.List.Class (joinL, repeat, scanl, sequence, sequence_, takeWhile)
--   import Prelude hiding (repeat, scanl, sequence, sequence_, takeWhile)
--   
--   main =
--     sequence_ .
--     fmap print .
--     scanl (+) 0 .
--     fmap (fst . head) .
--     takeWhile (not . null) .
--     fmap reads .
--     joinL . sequence $
--     (repeat getLine :: ListT IO (IO String))
--   </pre>
module Control.Monad.ListT
data ListItem l a
Nil :: ListItem l a
Cons :: a -> l a -> ListItem l a
headL :: ListItem l a -> a
tailL :: ListItem l a -> l a
data ListT m a
ListT :: m (ListItem (ListT m) a) -> ListT m a
runListT :: ListT m a -> m (ListItem (ListT m) a)

-- | foldr for ListT
foldrListT :: (Monad m) => (a -> m b -> m b) -> m b -> ListT m a -> m b
instance (MonadState s m) => MonadState s (ListT m)
instance (MonadReader s m) => MonadReader s (ListT m)
instance (MonadError e m) => MonadError e (ListT m)
instance (MonadIO m) => MonadIO (ListT m)
instance MonadTrans ListT
instance (Monad m) => MonadPlus (ListT m)
instance (Monad m) => Applicative (ListT m)
instance (Monad m) => Monad (ListT m)
instance (Monad m) => Functor (ListT m)
instance (Monad m) => Monoid (ListT m a)


-- | The <a>List</a> class and actions for lists
module Data.List.Class

-- | A class for list types. Every list has an underlying monad.
class (MonadPlus l, Monad m) => List l m | l -> m
joinL :: (List l m) => m (l b) -> l b
foldrL :: (List l m) => (a -> m b -> m b) -> m b -> l a -> m b
toListT :: (List l m) => l a -> ListT m a
fromListT :: (List l m) => ListT m a -> l a

-- | Prepend an item to a <a>MonadPlus</a>
cons :: (MonadPlus m) => a -> m a -> m a

-- | Convert a list to a <a>MonadPlus</a>
--   
--   <pre>
--   &gt; fromList [] :: Maybe Int
--   Nothing
--   &gt; fromList [5] :: Maybe Int
--   Just 5
--   </pre>
fromList :: (MonadPlus m) => [a] -> m a

-- | filter for any MonadPlus
--   
--   <pre>
--   &gt; filter (&gt; 5) (Just 3)
--   Nothing
--   </pre>
filter :: (MonadPlus m) => (a -> Bool) -> m a -> m a
repeat :: (MonadPlus m) => a -> m a
takeWhile :: (List l m) => (a -> Bool) -> l a -> l a
genericTake :: (Integral i, List l m) => i -> l a -> l a
scanl :: (List l m) => (a -> b -> a) -> a -> l b -> l a
sequence :: (List l m) => l (m a) -> m (l a)
sequence_ :: (List l m) => l (m a) -> m ()
transpose :: (List l m) => l (l a) -> l (l a)
zip :: (List l m) => l a -> l b -> l (a, b)
zipWith :: (List l m) => (a -> b -> c) -> l a -> l b -> l c

-- | An action to do foldl for <a>List</a>s
foldlL :: (List l m) => (a -> b -> a) -> a -> l b -> m a

-- | An action to transform a <a>List</a> to a list
--   
--   <pre>
--   &gt; runIdentity $ toList "hello!"
--   "hello!"
--   </pre>
toList :: (List l m) => l a -> m [a]

-- | Execute the monadic actions in a <a>List</a>
execute :: (List l m) => l a -> m ()

-- | Consume a list (execute its actions) and return its length
--   
--   <pre>
--   &gt; runIdentity $ lengthL [1,2,3]
--   3
--   </pre>
lengthL :: (Integral i, List l m) => l a -> m i

-- | Consume all items and return the last one
--   
--   <pre>
--   &gt; runIdentity $ lastL "hello"
--   'o'
--   </pre>
lastL :: (List l m) => l a -> m a

-- | Convert between lists with the same underlying monad
convList :: (List l m, List k m) => l a -> k a

-- | Transform the underlying monad of a list given a way to transform the
--   monad
--   
--   <pre>
--   &gt; import Data.List.Tree (bfs)
--   &gt; bfs (transformListMonad (\(Identity x) -&gt; [x, x]) "hey" :: ListT [] Char)
--   "hheeeeyyyyyyyy"
--   </pre>
transformListMonad :: (List l m, List k s) => (forall x. m x -> s x) -> l a -> k a

-- | Lift the underlying monad of a list and transform it to a ListT.
--   
--   Doing plain 'transformListMonad lift' instead doesn't give the
--   compiler the same knowledge about the types.
liftListMonad :: (MonadTrans t, Monad (t m), List l m) => l a -> ListT (t m) a
instance (Monad m) => List (ListT m) m
instance List [] Identity


-- | A difference-list monad transformer / a monadic difference-list.
--   
--   Difference lists are lists with <i>O(1)</i> append (instead of
--   <i>O(N)</i>).
--   
--   Transforming a difference list to a list is <i>O(1)</i>, a must be
--   done to access a difference list. The transformation from a list to a
--   difference list is <i>O(N)</i>.
module Control.Monad.DList

-- | A monadic difference-list
newtype DListT m a
DListT :: (ListT m a -> ListT m a) -> DListT m a
runDListT :: DListT m a -> ListT m a -> ListT m a
instance MonadTrans DListT
instance (Monad m) => List (DListT m) m
instance (Monad m) => MonadPlus (DListT m)
instance (Monad m) => Applicative (DListT m)
instance (Monad m) => Monad (DListT m)
instance (Monad m) => Functor (DListT m)
instance Monoid (DListT l a)


-- | A monad transformer for the creation of Lists. Similar to Python's
--   generators.
--   
--   <pre>
--   import Data.List.Class (convList)
--   
--   hanoi 0 _ _ _ = mempty
--   hanoi n from to other =
--     generate $ do
--       yields $ hanoi (n-1) from other to
--       yield (from, to)
--       yields $ hanoi (n-1) other to from
--   
--   &gt; convList (hanoi 3 'A' 'B' 'C') :: [(Char, Char)]
--   [('A','B'),('A','C'),('B','C'),('A','B'),('C','A'),('C','B'),('A','B')]
--   </pre>
module Control.Monad.Generator

-- | A monad transformer to create <tt>List</tt>s. <a>generate</a>
--   transforms a <a>GeneratorT v m a</a> to a <a>DListT m a</a>.
data GeneratorT v m a

-- | <i>O(1)</i>, Transform a GeneratorT to a <a>DListT</a>
generate :: (Monad m) => GeneratorT v m () -> DListT m v

-- | <i>O(1)</i>, Output a result value
yield :: (Monad m) => v -> GeneratorT v m ()

-- | <i>O(1)</i>, Output all the values of a <a>DListT</a>.
yields :: (Monad m) => DListT m v -> GeneratorT v m ()
instance (MonadIO m) => MonadIO (GeneratorT v m)
instance MonadTrans (GeneratorT v)
instance (Monad m) => Applicative (GeneratorT v m)
instance (Monad m) => Monad (GeneratorT v m)
instance (Monad m) => Functor (GeneratorT v m)


-- | A monad transformer for the [partial] consumption of <a>List</a>s. The
--   interface closely mimics iterators in languages such as Python.
--   
--   It is often nicer to avoid using Consumer and to use folds and
--   higher-order functions instead.
module Control.Monad.Consumer

-- | A monad tranformer for consuming <a>List</a>s.
data ConsumerT v m a

-- | Consume a <a>ListT</a>
evalConsumerT :: (List l m) => ConsumerT v m a -> l v -> m a

-- | Consume/get the next value
next :: (Monad m) => ConsumerT v m (Maybe v)

-- | Return an instance of the underlying monad that will use the given
--   <a>ConsumerT</a> to consume the remaining values. After this action
--   there are no more items to consume (they belong to the given ConsumerT
--   now)
consumeRestM :: (Monad m) => ConsumerT a m b -> ConsumerT a m (m b)
instance (MonadIO m) => MonadIO (ConsumerT v m)
instance MonadTrans (ConsumerT v)
instance (Monad m) => Applicative (ConsumerT v m)
instance (Monad m) => Monad (ConsumerT v m)
instance (Monad m) => Functor (ConsumerT v m)


-- | Functions for iterating trees. A <a>List</a> whose underlying monad is
--   also a <a>List</a> is a tree.
--   
--   It's nodes are accessible, in contrast to the list monad, which can
--   also be seen as a tree, except only its leafs are accessible and only
--   in <a>dfs order</a>.
--   
--   <pre>
--   import Control.Monad.Generator
--   import Data.List.Class (genericTake, takeWhile, toList, lastL)
--   
--   bits = t ""
--   t prev =
--     generate $ do
--       yield prev
--       x &lt;- lift "01"
--       yields $ t (prev ++ [x])
--   
--   &gt; take 3 (bfsLayers bits)
--   [[""],["0","1"],["00","01","10","11"]]
--   
--   &gt; take 10 (bfs bits)
--   ["","0","1","00","01","10","11","000","001","010"]
--   
--   &gt; dfs (genericTake 4 bits)
--   ["","0","00","000","001","01","010","011","1","10","100","101","11","110","111"]
--   
--   &gt; toList $ genericTake 3 bits
--   [["","0","00"],["","0","01"],["","1","10"],["","1","11"]]
--   </pre>
--   
--   Examples of pruning with <a>prune</a> and <a>takeWhile</a>:
--   
--   <pre>
--   &gt; dfs . takeWhile (not . isSuffixOf "11") $ genericTake 4 bits
--   ["","0","00","000","001","01","010","1","10","100","101"]
--   
--   &gt; lastL . takeWhile (not . isSuffixOf "11") $ genericTake 4 bits
--   ["000","001","010","01","100","101","1"]
--   
--   &gt; lastL . prune (not . isSuffixOf "11") $ genericTake 4 bits
--   ["000","001","010","100","101"]
--   </pre>
module Data.List.Tree

-- | A 'type-class synonym' for Trees.
class (List l k, List k m) => Tree l k m

-- | Iterate a tree in DFS pre-order. (Depth First Search)
dfs :: (List l m, MonadPlus m) => l a -> m a

-- | Iterate a tree in BFS order. (Breadth First Search)
bfs :: (Tree l k m) => l a -> k a

-- | Transform a tree into lists of the items in its different layers
bfsLayers :: (Tree l k m) => l a -> k (k a)

-- | Best First Search given a scoring function.
bestFirstSearchOn :: (Ord b, Tree l k m) => (a -> b) -> l a -> k a

-- | Prune a tree or list given a predicate. Unlike <a>takeWhile</a> which
--   stops a branch where the condition doesn't hold, prune <a>cuts</a> the
--   whole branch (the underlying MonadPlus's mzero).
prune :: (List l m, MonadPlus m) => (a -> Bool) -> l a -> l a

-- | Best-First-Search given that a node's children are in sorted order
--   (best first) and given a scoring function. Especially useful for trees
--   where nodes have an infinite amount of children, where
--   <a>bestFirstSearchOn</a> will get stuck.
bestFirstSearchSortedChildrenOn :: (Ord b, Tree l k m) => (a -> b) -> l a -> k a
instance (List l k, List k m) => Tree l k m