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 and iterative deepening depth-first search.

The implementation is inspired by Mike Spivey and Silvija Seres: see Chapter 9 of the book 'The Fun of Programming' and the paper 'Algebras for Combinatorial Search'.

The implementation of breadth-first search is similar to the inspiring implementation but uses lists with constant-time concatenation to represent levels. The implementation of iterative deepening depth-first is simpler than the inspiring implementation thanks to the use of a continuation monad.

Documentation

bfs :: FMList a -> [a]

The function bfs enumerates the results of a non-deterministic computation using breadth-first search. The implementation does not guarantee that results are returned in any specific order but it does guarantee that every result is eventually enumerated. Due to the large memory requirements of breadth-first search you should use idfs for expensive search.

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. Use idfsBy to control this. 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. It can, however, produce results lazily: calling take n . idfs terminates if the number of results is larger than n.

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.