Portability | portable |
---|---|

Stability | experimental |

Maintainer | Sebastian 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 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

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.

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`

.