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
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
:: Show a => 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
:: Show a => (SearchTree a -> ValueSequence a) -> a -> IO ()
Prints all values of an expression w.r.t. |
printValuesWith
:: Show a => (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. |
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
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
Returns the search tree for some expression. |
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!). |
Returns True iff the argument is defined, i.e., has a value. |
Shows the search tree as an intended line structure |
Returns the size (number of Value/Fail/Or nodes) of the search tree. |
Limit the depth of a search tree. Branches which a depth larger
than the first argument are replace by |
Depth-first search strategy. |
Breadth-first search strategy. |
Iterative-deepening search strategy. |
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. |
Diagonalization search strategy. |
Return all values in a search tree via some given search strategy. |
Return all values in a search tree via depth-first search. |
Return all values in a search tree via breadth-first search. |
Return all values in a search tree via iterative-deepening search. |
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. |
Return all values in a search tree via diagonalization search strategy. |
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., |
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., |
Prints the values of an expression w.r.t. a search strategy
on demand by the user. Thus, the user must type |
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. |
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., 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. |