Module Control.SearchTree

This library defines a representation of a search space as a tree and various search strategies on this tree. This module implements strong encapsulation as discussed in the JFLP'04 paper.

Author: Michael Hanus, Bjoern Peemoeller, Fabian Reck

Version: December 2018

Summary of exported operations:

getSearchTree :: a -> IO (SearchTree a)  Deterministic 
Returns the search tree for some expression.
someSearchTree :: a -> SearchTree a  Deterministic 
Internal operation to return the search tree for some expression.
isDefined :: a -> Bool  Deterministic 
Returns True iff the argument is defined, i.e., has a value.
showSearchTree :: Show a => SearchTree a -> String  Deterministic 
Shows the search tree as an intended line structure
searchTreeSize :: SearchTree a -> (Int,Int,Int)  Deterministic 
Returns the size (number of Value/Fail/Or nodes) of the search tree.
limitSearchTree :: Int -> SearchTree a -> SearchTree a  Deterministic 
Limit the depth of a search tree.
dfsStrategy :: SearchTree a -> ValueSequence a  Deterministic 
Depth-first search strategy.
bfsStrategy :: SearchTree a -> ValueSequence a  Deterministic 
Breadth-first search strategy.
idsStrategy :: SearchTree a -> ValueSequence a  Deterministic 
Iterative-deepening search strategy.
idsStrategyWith :: Int -> (Int -> Int) -> SearchTree a -> ValueSequence a  Deterministic 
Parameterized iterative-deepening search strategy.
diagStrategy :: SearchTree a -> ValueSequence a  Deterministic 
Diagonalization search strategy.
allValuesWith :: (SearchTree a -> ValueSequence a) -> SearchTree a -> [a]  Deterministic 
Return all values in a search tree via some given search strategy.
allValuesDFS :: SearchTree a -> [a]  Deterministic 
Return all values in a search tree via depth-first search.
allValuesBFS :: SearchTree a -> [a]  Deterministic 
Return all values in a search tree via breadth-first search.
allValuesIDS :: SearchTree a -> [a]  Deterministic 
Return all values in a search tree via iterative-deepening search.
allValuesIDSwith :: Int -> (Int -> Int) -> SearchTree a -> [a]  Deterministic 
Return all values in a search tree via iterative-deepening search.
allValuesDiag :: SearchTree a -> [a]  Deterministic 
Return all values in a search tree via diagonalization search strategy.
getAllValuesWith :: (SearchTree a -> ValueSequence a) -> a -> IO [a]  Deterministic 
Gets all values of an expression w.r.t.
printAllValuesWith :: Show a => (SearchTree a -> ValueSequence a) -> a -> IO ()  Deterministic 
Prints all values of an expression w.r.t.
printValuesWith :: Show a => (SearchTree a -> ValueSequence a) -> a -> IO ()  Deterministic 
Prints the values of an expression w.r.t.
someValue :: a -> a  Deterministic 
Returns some value for an expression.
someValueWith :: (SearchTree a -> ValueSequence a) -> a -> a  Deterministic 
Returns some value for an expression w.r.t.

Exported datatypes:


SearchTree

A search tree is a value, a failure, or a choice between two search trees.

Constructors:

  • Value :: a -> SearchTree a
  • Fail :: Int -> SearchTree a
  • Or :: (SearchTree a) -> (SearchTree a) -> SearchTree a

Strategy

A search strategy maps a search tree into some sequence of values. Using the abtract type of sequence of values (rather than list of values) enables the use of search strategies for encapsulated search with search trees (strong encapsulation) as well as with set functions (weak encapsulation).

Type synonym: Strategy a = SearchTree a -> ValueSequence a


Exported operations:

getSearchTree :: a -> IO (SearchTree a)  Deterministic 

Returns the search tree for some expression.

someSearchTree :: a -> SearchTree a  Deterministic 

Internal operation to return the search tree for some expression. Note that this operation is not purely declarative since the ordering in the resulting search tree depends on the ordering of the program rules.

Note that in PAKCS the search tree is just a degenerated tree representing all values of the argument expression and it is computed at once (i.e., not lazily!).

isDefined :: a -> Bool  Deterministic 

Returns True iff the argument is defined, i.e., has a value.

showSearchTree :: Show a => SearchTree a -> String  Deterministic 

Shows the search tree as an intended line structure

searchTreeSize :: SearchTree a -> (Int,Int,Int)  Deterministic 

Returns the size (number of Value/Fail/Or nodes) of the search tree.

limitSearchTree :: Int -> SearchTree a -> SearchTree a  Deterministic 

Limit the depth of a search tree. Branches which a depth larger than the first argument are replace by Fail (-1).

dfsStrategy :: SearchTree a -> ValueSequence a  Deterministic 

Depth-first search strategy.

bfsStrategy :: SearchTree a -> ValueSequence a  Deterministic 

Breadth-first search strategy.

idsStrategy :: SearchTree a -> ValueSequence a  Deterministic 

Iterative-deepening search strategy.

idsStrategyWith :: Int -> (Int -> Int) -> SearchTree a -> ValueSequence a  Deterministic 

Parameterized iterative-deepening search strategy. The first argument is the initial depth bound and the second argument is a function to increase the depth in each iteration.

diagStrategy :: SearchTree a -> ValueSequence a  Deterministic 

Diagonalization search strategy.

allValuesWith :: (SearchTree a -> ValueSequence a) -> SearchTree a -> [a]  Deterministic 

Return all values in a search tree via some given search strategy.

allValuesDFS :: SearchTree a -> [a]  Deterministic 

Return all values in a search tree via depth-first search.

allValuesBFS :: SearchTree a -> [a]  Deterministic 

Return all values in a search tree via breadth-first search.

allValuesIDS :: SearchTree a -> [a]  Deterministic 

Return all values in a search tree via iterative-deepening search.

allValuesIDSwith :: Int -> (Int -> Int) -> SearchTree a -> [a]  Deterministic 

Return all values in a search tree via iterative-deepening search. The first argument is the initial depth bound and the second argument is a function to increase the depth in each iteration.

allValuesDiag :: SearchTree a -> [a]  Deterministic 

Return all values in a search tree via diagonalization search strategy.

getAllValuesWith :: (SearchTree a -> ValueSequence a) -> a -> IO [a]  Deterministic 

Gets all values of an expression w.r.t. a search strategy. A search strategy is an operation to traverse a search tree and collect all values, e.g., dfsStrategy or bfsStrategy. Conceptually, all values are computed on a copy of the expression, i.e., the evaluation of the expression does not share any results.

printAllValuesWith :: Show a => (SearchTree a -> ValueSequence a) -> a -> IO ()  Deterministic 

Prints all values of an expression w.r.t. a search strategy. A search strategy is an operation to traverse a search tree and collect all values, e.g., dfsStrategy or bfsStrategy. Conceptually, all printed values are computed on a copy of the expression, i.e., the evaluation of the expression does not share any results.

printValuesWith :: Show a => (SearchTree a -> ValueSequence a) -> a -> IO ()  Deterministic 

Prints the values of an expression w.r.t. a search strategy on demand by the user. Thus, the user must type ENTER before another value is computed and printed. A search strategy is an operation to traverse a search tree and collect all values, e.g., dfsStrategy or bfsStrategy. Conceptually, all printed values are computed on a copy of the expression, i.e., the evaluation of the expression does not share any results.

someValue :: a -> a  Deterministic 

Returns some value for an expression.

Note that this operation is not purely declarative since the computed value depends on the ordering of the program rules. Thus, this operation should be used only if the expression has a single value. It fails if the expression has no value.

someValueWith :: (SearchTree a -> ValueSequence a) -> a -> a  Deterministic 

Returns some value for an expression w.r.t. a search strategy. A search strategy is an operation to traverse a search tree and collect all values, e.g., dfsStrategy or bfsStrategy.

Note that this operation is not purely declarative since the computed value depends on the ordering of the program rules. Thus, this operation should be used only if the expression has a single value. It fails if the expression has no value.