level-monad 0.2.2.1 → 0.3

raw patch · 3 files changed

+52/−26 lines, 3 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Control/Monad/Levels.hs +46/−17
• README +3/−6
• level-monad.cabal +3/−3

@@ -21,8 +21,12 @@  module Control.Monad.Levels (  -  Levels, levels, breadthFirstSearch, levelDiagonalisation+  Levels, levels, breadthFirstSearch,  +  DepthBound, iterLevels, iterativeDeepening,++  diagonals+   ) where  import Control.Monad@@ -45,22 +49,6 @@ breadthFirstSearch :: Levels a -> [a] breadthFirstSearch = concat . levels --- |--- The function @levelDiagonalisation@ enumerates the results of a--- non-deterministic computation by diagonally interleaving the--- results of all levels.-levelDiagonalisation :: Levels a -> [a]-levelDiagonalisation = concat . diagonals . levels--diagonals :: [[a]] -> [[a]]-diagonals []       = []-diagonals (xs:xss) = zipConc [[x] | x <- xs] ([] : diagonals xss)--zipConc :: [[a]] -> [[a]] -> [[a]]-zipConc []       yss      = yss-zipConc xss      []       = xss-zipConc (xs:xss) (ys:yss) = (xs++ys) : zipConc xss yss- instance Monad Levels  where   return x = Levels [[x]]@@ -78,3 +66,44 @@    Levels xs `mplus` Levels ys = Levels ([] : zipConc xs ys) +-- |+-- The type @DepthBound@ represents computations with a bounded+-- depth. It's monad instances implements iterative deepening.+newtype DepthBound a = DepthBound { (!) :: Int -> [(a,Int)] }++instance Monad DepthBound+ where+  return x = DepthBound (\d -> [(x,d)])+  a >>= f  = DepthBound (\d -> [ y | (x,d') <- a!d, y <- f x!d' ])++instance MonadPlus DepthBound+ where+  mzero       = DepthBound (const [])+  a `mplus` b = DepthBound (\d -> do guard (d>0)+                                     let d' = d-1+                                     (a!d') `mplus` (b!d'))++-- |+-- The function @iterLevels@ computes the levels of a depth bound+-- computation using iterative deepening.+iterLevels :: DepthBound a -> Levels a+iterLevels a = Levels [[ x | (x,0) <- a!d ] | d <- [0..]]++-- |+-- The function @iterativeDeepening@ enumerates the results of a+-- non-deterministic computations using iterative deepening.+iterativeDeepening :: DepthBound a -> [a]+iterativeDeepening = concat . levels . iterLevels++-- | +-- The function @diagonals@ enumarates the entries of a matrix+-- diagonally. The matrix may contain an infinite number of infinite+-- rows.+diagonals :: [[a]] -> [[a]]+diagonals []       = []+diagonals (xs:xss) = zipConc [[x] | x <- xs] ([] : diagonals xss)++zipConc :: [[a]] -> [[a]] -> [[a]]+zipConc []       yss      = yss+zipConc xss      []       = xss+zipConc (xs:xss) (ys:yss) = (xs++ys) : zipConc xss yss

@@ -2,8 +2,8 @@ ===========================================  This Haskell library provides an implementation of the MonadPlus type-class that enumerates the levels of the search space and allows to-implement breadth-first search.+class that enumerates the levels of the search space using+breadth-first search or iterativ deepening.  A search space is formed by calls to `return` and `mplus` yielding a search tree with solutions in its leaves. For example, in the monadic@@ -29,7 +29,4 @@ The library provides an operation to get the list of levels from a non-deterministic computation. The nth element in this list contains the results of the computation that are found on the nth level of the-computation. Hence, using `concat` to merge the levels, yields-breadth-first search, but different combination functions-(e.g. diagonalisation) can be applied too.-+computation.

@@ -1,11 +1,11 @@ Name:          level-monad-Version:       0.2.2.1+Version:       0.3 Cabal-Version: >= 1.6 Synopsis:      Non-Determinism Monad for Level-Wise Search Description:   This Haskell library provides an implementation of the                MonadPlus type class that enumerates the levels of the-               search space and allows to implement breadth-first-               search.+               search space using breadth-first search or iterativ+               deepening. Category:      Control, Monads License:       PublicDomain License-File:  LICENSE