-
Exported names:
-
Imported modules:
Module Control.Search.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) 
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. |
vsToList
:: ValueSequence a -> [a]
Transforms a sequence of values into a list of values. |
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
ValueSequence
The subsequent part defines a data structure for sequence of values which is used in the implementation of search trees. Using sequence of values (rather than standard lists of values) is necessary to get the behavior of set functions w.r.t. finite failures right, as described in the paper
J. Christiansen, M. Hanus, F. Reck, D. Seidel: A Semantics for Weakly Encapsulated Search in Functional Logic Programs Proc. 15th International Conference on Principles and Practice of Declarative Programming (PPDP'13), pp. 49-60, ACM Press, 2013
Note that the implementation for PAKCS is simplified in order to provide some functionality used by other modules. In particular, the intended semantics of failures is not provided in the PAKCS implementation. A value sequence is an abstract sequence of values. It also contains failure elements in order to implement the semantics of set functions w.r.t. failures in the intended manner (only in KiCS2).
Constructors:
Exported operations:
|
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., 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. |
|
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. |
|
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., 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. |
|
Transforms a sequence of values into a list of values.
|