level-monad (empty) → 0.1
raw patch · 5 files changed
+177/−0 lines, 5 filesdep +basesetup-changed
Dependencies added: base
Files
- Control/Monad/Levels.hs +78/−0
- LICENSE +32/−0
- README +35/−0
- Setup.hs +4/−0
- level-monad.cabal +28/−0
+ Control/Monad/Levels.hs view
@@ -0,0 +1,78 @@+-- |+-- Module : Control.Monad.Levels+-- Copyright : Sebastian Fischer 2009+-- License : BSD3+-- +-- Maintainer : Sebastian Fischer (sebf@informatik.uni-kiel.de)+-- Stability : experimental+-- Portability : portable+-- +-- This library provides an implementation of the MonadPlus type+-- class that enumerates the levels of the search space and allows to+-- implement breadth-first search.+-- +-- The implementation is inspired by Mike Spivey and Silvija Seres:+-- cf. Chapter 9 of the book 'The Fun of Programming'.+-- +-- Warning: @Levels@ is only a monad when the results of the+-- enumeration functions are interpreted as a multiset, i.e., a valid+-- transformation according to the monad laws may change the order of+-- the results.++module Control.Monad.Levels ( ++ Levels, levels, breadthFirstSearch, levelDiagonalisation++ ) where++import Control.Monad++-- | +-- Non-Deterministic computations of type @Levels a@ can be searched+-- level-wise.+newtype Levels a = Levels { ++ -- |+ -- The function @levels@ yields the results of a non-deterministic+ -- computation grouped in levels.+ levels :: [[a]]++ }++-- |+-- The function @breadthFirstSearch@ enumerates the results of a+-- non-deterministic computation in breadth-first order.+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]]++ Levels x >>= f = Levels (x `bind` (levels . f))++bind :: [[a]] -> (a -> [[b]]) -> [[b]]+bind x f = map concat (diagonals (map (foldr zipConc [] . map f) x))++instance MonadPlus Levels+ where+ mzero = Levels []++ Levels xs `mplus` Levels ys = Levels ([] : zipConc xs ys)+
+ LICENSE view
@@ -0,0 +1,32 @@+Copyright (c) 2009, Sebastian Fischer++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are+met:++ 1. Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer.++ 2. Redistributions in binary form must reproduce the above copyright+ notice, this list of conditions and the following disclaimer in+ the documentation and/or other materials provided with the+ distribution.++ 3. Neither the name of the author nor the names of his contributors+ may be used to endorse or promote products derived from this+ software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR+CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,+PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.+
+ README view
@@ -0,0 +1,35 @@+Non-Determinism Monad for Level-Wise Search+===========================================++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.++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+action++ return 1 `mplus` ((return 2 `mplus` return 3) `mplus` return 4)++the result 1 is in the second level, 4 in the third, and the results 2+and 3 are in the forth level. This is apparent from the following+representation of this monadic action:++ `mplus`+ / \+ return 1 `mplus`+ / \+ `mplus` return 4+ / \+ return 2 return 3++However, the implementation does not build this tree structure as a+data term but constructs its levels directly.++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 function+(e.g. diagonalisation) can be applied too.+
+ Setup.hs view
@@ -0,0 +1,4 @@+import Distribution.Simple++main = defaultMain+
+ level-monad.cabal view
@@ -0,0 +1,28 @@+Name: level-monad+Version: 0.1+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.+Category: Control+License: BSD3+License-File: LICENSE+Author: Sebastian Fischer+Maintainer: sebf@informatik.uni-kiel.de+Bug-Reports: mailto:sebf@informatik.uni-kiel.de+Homepage: http://github.com/sebfisch/level-monad+Build-Type: Simple+Stability: experimental++Extra-Source-Files: README++Library+ Build-Depends: base+ Exposed-Modules: Control.Monad.Levels+ Ghc-Options: -Wall++Source-Repository head+ type: git+ location: git://github.com/sebfisch/level-monad.git