Defines the type of the step function that produces new states from existing ones. This is how the graph over the search space is defined. The step function takes a state and provides a list of other states that can be reached from it. Each of the listed states is paired with a Bool that when true indiciates that a state is considered to be a goal of the search.

Defines the type of a bundle of operators that need to be supplied to conduct an uninformed (non-heuristic) search.

Defines the type of a bundle of operators that need to be supplied to conduct an informed (heuristic) search.

Defines the type of a bundle of operators that need to be supplied to conduct an uninformed (non-heuristic) search. This is an extensible record so that heuristic searches can also have this type since they use the same cost and step functions. This makes it easy to switch from a heuristic to anon-heuristic search.

Defines the possible outcomes of a search. A search may produce the following results:

• Complete. The search space has been exhausted without finding a goal state.
• Goal. A goal state has been found. A function to find further results is also returned, in order that the search may be continued to find more goals.
• Ongoing. A goal state has not been found yet. The state most recently examined is returned along with a function to continue to the search.

Steps a search result, to produce the next result.

• The result of this function may be an Ongoing search. This will provide the current head search node and a continuation to run the remainder of the search.

Continues a search result, to produce the next search goal up to a limited number of iterations.

• This function will recursively apply the search until either a Goal state is found or the walk over the search space is Complete, or the iteration count is exhausted in which case an Ongoing search may be returned.

Continues a search result, to produce the next search goal.

• The result of this function will never be an Ongoing search. This function will recursively apply the search until either a Goal state is found or the walk over the search space is Complete.
• If the search is insufficiently constrained and no goal can ever be found, this function may infnite loop.

Performs an unbounded breadth first search. Breadth first searches store a lot of pending nodes in the buffer, so quickly run out of space.

Performs an unbounded depth first search. Depth first searches can easily fall into infinite loops.

Implements an uninformed search that is bounded to a specified maximum depth.

Implements a cost bounded search. This search will proceed depth first.

Performs a uniform-cost search. This always follows the search node that has the lowest path cost. It is called a uniform cost search because the boundary of the search will have a roughly uniform cost as the search space is searched by increasing cost.

Implements an iterative deepening search. This search proceed depth first but repeats at progressively larger depth limits. The iteration number is multiplied by a specified multiple to calculate the maximum depth allowed at a given iteration.

Implements an iterative cost increasing search. This search proceed depth first but repeats at progressively larger cost limits. The iteration number is multiplied by a specified multiple to calculate the maximum cost allowed at a given iteration.

Performs an A* search. This is one that always follows the search node that has the highest f value (f = heuristic + cost). The seach will only be optimal if the heuristic function is monotonic.

Performs a greedy heuristic search. This is one that always follows the search node that has the highest h value (h = heuristic).

Implements an f value (f = heuristic + cost) bounded search. This search will proceed depth first.