Module Control.SearchTree.Unsafe

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 this paper

Warning: In contrast to the SearchTree Module, free variables that are not bound in the encapsulated expression remain free! This may lead to non-determinism if such an escaped variable is bound later via pattern matching.

Author: Michael Hanus, Bjoern Peemoeller, Fabian Reck

Version: December 2018

Summary of exported operations:

isVar :: a -> Bool   
Tests whether the argument is a free variable This function is only meaningful when applied to a part of a result of an encapsulated expression if the argument stems from a Value node of a SearchTree
identicalVars :: a -> a -> Bool   
Tests whether both arguments are identical free variables.
varId :: a -> Int   
Returns the unique identifier of a free variable, if the argument was not a free variable, otherwise an error is raised.
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 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)   
Return the size (number of Value/Fail/Or nodes) of the search tree
allValuesDFS :: SearchTree a -> [a]   
Return all values in a search tree via depth-first search
dfsStrategy :: SearchTree a -> ValueSequence a   
allValuesBFS :: SearchTree a -> [a]   
Return all values in a search tree via breadth-first search
bfsStrategy :: SearchTree a -> ValueSequence a   
allValuesIDS :: SearchTree a -> [a]   
Return all values in a search tree via iterative-deepening search.
idsStrategy :: SearchTree a -> ValueSequence a   
allValuesIDSwith :: Int -> (Int -> Int) -> SearchTree a -> [a]   
Return the list of all values in a search tree via iterative-deepening search.
idsStrategyWith :: Int -> (Int -> Int) -> SearchTree a -> ValueSequence a   
Return all values in a search tree via iterative-deepening search.
getAllValuesWith :: (SearchTree a -> ValueSequence a) -> a -> IO [a]   
Gets all 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

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


Exported operations:

isVar :: a -> Bool   

Tests whether the argument is a free variable This function is only meaningful when applied to a part of a result of an encapsulated expression if the argument stems from a Value node of a SearchTree

identicalVars :: a -> a -> Bool   

Tests whether both arguments are identical free variables. This function is only meaningful when applied to parts of a result of an encapsulated expression if the argument stems from a Value node of a SearchTree

varId :: a -> Int   

Returns the unique identifier of a free variable, if the argument was not a free variable, otherwise an error is raised. This function is only meaningful when applied to a part of a result of an encapsulated expression if the argument stems from a Value node of a SearchTree

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.

Further infos:
  • externally defined

isDefined :: a -> Bool   

Returns True iff the argument is 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)   

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

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 the list of 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.

idsStrategyWith :: Int -> (Int -> Int) -> SearchTree a -> ValueSequence 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.

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. Moreover, the evaluation suspends as long as the expression contains unbound variables.

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.