ListTree 0.2.0 → 0.2.1

raw patch · 2 files changed

+13/−14 lines, 2 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• ListTree.cabal +1/−1
• src/Data/List/Tree.hs +12/−13

@@ -1,5 +1,5 @@ Name:                ListTree-Version:             0.2.0+Version:             0.2.1 Category:            Algorithms Synopsis:            Trees and monadic trees expressed as monadic lists where the underlying monad is a list Description:

@@ -7,15 +7,12 @@ -- which can also be seen as a tree, except only its leafs -- are accessible and only in "dfs order". ----- > import Control.Monad.Generator--- > import Control.Monad.Trans--- > import Data.List.Class (genericTake, takeWhile, toList, lastL)+-- > import Control.Monad.Trans.List.Funcs (repeatM)+-- > import Data.List.Class (genericTake, scanl, takeWhile, toList, lastL)+-- > import Prelude hiding (scanl, takeWhile) -- >--- > bits = generate (t "")--- > t prev = do--- >   yield prev--- >   x <- lift "01"--- >   t (prev ++ [x])+-- > appendToEnd xs x = xs ++ [x]+-- > bits = scanl appendToEnd [] (repeatM "01") -- > -- > > take 3 (bfsLayers bits) -- > [[""],["0","1"],["00","01","10","11"]]@@ -41,7 +38,7 @@ -- > ["000","001","010","100","101"] -- module Data.List.Tree (-  Tree,+  Tree, TreeT, TreeItemM,   -- | Search algorithms   dfs, bfs, bfsLayers,   bestFirstSearchOn,@@ -66,15 +63,17 @@ class (List t, List (ItemM t)) => Tree t instance (List t, List (ItemM t)) => Tree t -search :: (List l, MonadPlus (ItemM l)) =>-  (ItemM l (ItemM l a) -> ItemM l a) -> l a -> ItemM l a+type TreeT m a = ListT (ListT m) a+type TreeItemM t = ItemM (ItemM t)++search :: Tree t => (ItemM t (ItemM t a) -> ItemM t a) -> t a -> ItemM t a search merge =   merge . foldrL step mzero   where     step a = return . cons a . merge  -- | Iterate a tree in DFS pre-order. (Depth First Search)-dfs :: (List l, MonadPlus (ItemM l)) => l a -> ItemM l a+dfs :: Tree t => t a -> ItemM t a dfs = search join  -- | Transform a tree into lists of the items in its different layers@@ -176,7 +175,7 @@ -- 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 -> ListT (ListT (StateT (Maybe b) (ItemM (ItemM t)))) a+  -> t a -> TreeT (StateT (Maybe b) (TreeItemM t)) a branchAndBound boundFunc =   pruneM cond . transformListMonad (transformListMonad lift)   where