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

MaintainerSebastian Fischer (sebf@informatik.uni-kiel.de)



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.



data Levels a Source

Non-Deterministic computations of type Levels a can be searched level-wise.

levels :: Levels a -> [[a]]Source

The function levels yields the results of a non-deterministic computation grouped in levels.

breadthFirstSearch :: Levels a -> [a]Source

The function breadthFirstSearch enumerates the results of a non-deterministic computation in breadth-first order.

data DepthBound a Source

The type DepthBound represents computations with a bounded depth. It's monad instances implements iterative deepening.

iterLevels :: DepthBound a -> Levels aSource

The function iterLevels computes the levels of a depth bound computation using iterative deepening.

iterativeDeepening :: DepthBound a -> [a]Source

The function iterativeDeepening enumerates the results of a non-deterministic computations using iterative deepening.

diagonals :: [[a]] -> [[a]]Source

The function diagonals enumarates the entries of a matrix diagonally. The matrix may contain an infinite number of infinite rows.