The level-monad package

[Tags: library, public-domain]

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.


[Skip to ReadMe]

Properties

Versions0.1, 0.2, 0.2.1, 0.2.2, 0.2.2.0, 0.2.2.1, 0.3, 0.3.1, 0.4, 0.4.1
Change logNone available
Dependenciesbase [details]
LicenseBSD3
AuthorSebastian Fischer
Maintainersebf@informatik.uni-kiel.de
Stabilityexperimental
CategoryControl
Home pagehttp://github.com/sebfisch/level-monad
Bug trackermailto:sebf@informatik.uni-kiel.de
Source repositoryhead: git clone git://github.com/sebfisch/level-monad.git
UploadedMon Jan 26 21:57:10 UTC 2009 by SebastianFischer
Downloads1465 total (82 in last 30 days)
Votes
0 []
StatusDocs uploaded by user
Build status unknown [no reports yet]

Modules

[Index]

Downloads

Maintainers' corner

For package maintainers and hackage trustees

Readme for level-monad-0.1

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.