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


-- | Trees and monadic trees expressed as monadic lists where the underlying monad is a list
--   
@package ListTree
@version 0.2.2


-- | 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 "dfs order".
--   
--   <pre>
--   import Control.Monad.Trans.List.Funcs (repeatM)
--   import Data.List.Class (genericTake, scanl, takeWhile, toList, lastL)
--   import Prelude hiding (scanl, takeWhile)
--   
--   appendToEnd xs x = xs ++ [x]
--   bits = scanl appendToEnd [] (repeatM "01")
--   
--   &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 t, List (ItemM t)) => Tree t
type TreeT m a = ListT (ListT m) a
type TreeItemM t = ItemM (ItemM t)

-- | Iterate a tree in DFS pre-order. (Depth First Search)
dfs :: Tree t => t a -> ItemM t a

-- | Iterate a tree in BFS order. (Breadth First Search)
bfs :: Tree t => t a -> ItemM t a

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

-- | Best First Search given a scoring function.
bestFirstSearchOn :: (Ord b, Tree t) => (a -> b) -> t a -> ItemM t 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.
--   
--   Example: Find smallest Pythagorian Triplets
--   
--   <pre>
--   import Control.Monad
--   import Control.Monad.Generator
--   import Control.Monad.Trans.Class
--   import Data.List.Tree
--   import Data.Maybe
--   
--   pythagorianTriplets =
--     catMaybes .
--     fmap fst .
--     bestFirstSearchSortedChildrenOn snd .
--     generate $ do
--       x &lt;- lift [1..]
--       yield (Nothing, x)
--       y &lt;- lift [1..]
--       yield (Nothing, x + y)
--       z &lt;- lift [1..]
--       yield (Nothing, x + y + z)
--       lift . guard $ x^2 + y^2 == z^2
--       yield (Just (x, y, z), 0)
--   
--   &gt; print $ take 10 pythagorianTriplets
--   [(3,4,5),(4,3,5),(6,8,10),(8,6,10),(5,12,13),(12,5,13),(9,12,15),(12,9,15),(15,8,17),(8,15,17)]
--   </pre>
bestFirstSearchSortedChildrenOn :: (Ord b, Tree t) => (a -> b) -> t a -> ItemM t a
sortChildrenOn :: (Ord b, Tree t) => (a -> b) -> t a -> ListT (ItemM t) a

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

-- | Generalized "Branch and Bound". A method for pruning.
--   
--   The result of this function would usually be given to another search
--   algorithm, such as <a>dfs</a>, in order to find the node with lowest
--   value.
--   
--   This augments the regular search by pruning the tree. Given a function
--   to calculate a lower and upper bound for a subtree, we keep the lowest
--   upper bound (hence the State monad) encountered so far, and we prune
--   any subtree whose lower bound is over the known upper bound.
branchAndBound :: (Ord b, Tree t) => (a -> (Maybe b, Maybe b)) -> t a -> TreeT (StateT (Maybe b) (TreeItemM t)) a
instance (List t, List (ItemM t)) => Tree t


-- | Monadic directory tree.
--   
--   <pre>
--   -- List of files under "." or subfolders with ".markdown" extension,
--   -- except for those with a name starting with "_" somewhere in their path. (like "_cache/index.markdown")
--   markdownFiles :: ListT IO FilePath
--   markdownFiles
--       = filter ((== ".markdown") . takeExtension) -- only take files with a ".markdown" extension
--       . lastL                                     -- get the leaves of the tree (files, not directories)
--       . scanl1 appendPath                         -- transform tree nodes to filenames including path
--       . prune (not . isPrefixOf "_")              -- ignore directories or files whose name starts with "_"
--       $ directoryTree "."                         -- directory tree starting at "."
--   </pre>
--   
--   Module name System.Directory.Tree is a better fit but it is taken by
--   "directory-tree", a read-directory-tree-in-bulk module.
module System.Directory.ListTree
directoryTree :: MonadIO m => FilePath -> ListT (ListT m) FilePath

-- | When used with <tt>scanl</tt> or <tt>scanl1</tt>, transforms tree of
--   filenames to tree of filenames with the paths
appendPath :: FilePath -> FilePath -> FilePath