level-monad: Non-Determinism Monad for Level-Wise Search

[ control, library, monads, public-domain ] [ Propose Tags ]

This Haskell library provides an implementation of the MonadPlus type class that enumerates the levels of the search space using breadth-first search or iterativ deepening depth-first search.


[Skip to Readme]

Modules

[Index]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.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
Dependencies base (>=3 && <5), fmlist [details]
License LicenseRef-PublicDomain
Author Sebastian Fischer
Maintainer sebf@informatik.uni-kiel.de
Category Control, Monads
Home page http://github.com/sebfisch/level-monad
Bug tracker http://github.com/sebfisch/level-monad/issues
Source repo head: git clone git://github.com/sebfisch/level-monad.git
Uploaded by SebastianFischer at 2009-06-22T09:08:07Z
Distributions
Reverse Dependencies 2 direct, 0 indirect [details]
Downloads 7393 total (27 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]

Readme for level-monad-0.4.1

[back to package description]
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 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
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.