Module 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: February 2016

Summary of exported operations:

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

Returns the search tree for some expression.

someSearchTree :: a -> SearchTree a   

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   

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

showSearchTree :: SearchTree a -> String   

Shows the search tree as an intended line structure

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

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

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

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   

Depth-first search strategy.

bfsStrategy :: SearchTree a -> ValueSequence a   

Breadth-first search strategy.

idsStrategy :: SearchTree a -> ValueSequence a   

Iterative-deepening search strategy.

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

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   

Diagonalization search strategy.

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

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

allValuesDFS :: SearchTree a -> [a]   

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

allValuesBFS :: SearchTree a -> [a]   

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

allValuesIDS :: SearchTree a -> [a]   

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

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

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]   

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

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

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 :: (SearchTree a -> ValueSequence a) -> a -> IO ()   

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 :: (SearchTree a -> ValueSequence a) -> a -> IO ()   

Prints the values of an expression w.r.t. a search strategy on demand by the user. Thus, the user must type 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   

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   

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.