Control.Monad.Levels

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'. The implementation of iterative deepening depth-first is, however, significantly simpler thanks to the use of a continuation monad.

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.

Documentation

bfs :: FMList a -> [a]

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

idfs :: FMList a -> [a]

The function idfs computes the levels of a depth bound computation using iterative deepening depth-first search. Unlike breadth-first search it runs in constant space but usually takes a bit longer, depending on how the depth limit is increased. Don't use this algorithm if you know that there is only a finite number of results because it will continue trying larger depth limits without recognizing that there are no more solutions.

idfsBy :: Int -> FMList a -> [a]

The function idfsBy computes the levels of a depth bound computation using iterative deepening depth-first search incrementing the depth limit between searches using the given number of steps.