| Maintainer | bastiaan.heeren@ou.nl |
|---|---|
| Stability | provisional |
| Portability | portable (depends on ghc) |
| Safe Haskell | Safe-Inferred |
| Language | Haskell98 |
Ideas.Common.DerivationTree
Contents
Description
Datatype for representing derivations as a tree. The datatype stores all intermediate results as well as annotations for the steps.
- data DerivationTree s a
- singleNode :: a -> Bool -> DerivationTree s a
- addBranches :: [(s, DerivationTree s a)] -> DerivationTree s a -> DerivationTree s a
- makeTree :: (a -> (Bool, [(s, a)])) -> a -> DerivationTree s a
- root :: DerivationTree s a -> a
- endpoint :: DerivationTree s a -> Bool
- branches :: DerivationTree s a -> [(s, DerivationTree s a)]
- subtrees :: DerivationTree s a -> [DerivationTree s a]
- leafs :: DerivationTree s a -> [a]
- lengthMax :: Int -> DerivationTree s a -> Maybe Int
- restrictHeight :: Int -> DerivationTree s a -> DerivationTree s a
- restrictWidth :: Int -> DerivationTree s a -> DerivationTree s a
- updateAnnotations :: (a -> s -> a -> t) -> DerivationTree s a -> DerivationTree t a
- cutOnStep :: (s -> Bool) -> DerivationTree s a -> DerivationTree s a
- mergeMaybeSteps :: DerivationTree (Maybe s) a -> DerivationTree s a
- sortTree :: (l -> l -> Ordering) -> DerivationTree l a -> DerivationTree l a
- cutOnTerm :: (a -> Bool) -> DerivationTree s a -> DerivationTree s a
- derivation :: DerivationTree s a -> Maybe (Derivation s a)
- randomDerivation :: RandomGen g => g -> DerivationTree s a -> Maybe (Derivation s a)
- derivations :: DerivationTree s a -> [Derivation s a]
Data types
data DerivationTree s a Source
Instances
| BiFunctor DerivationTree | |
| Functor (DerivationTree s) | |
| (Show s, Show a) => Show (DerivationTree s a) |
Constructors
singleNode :: a -> Bool -> DerivationTree s a Source
Constructs a node without branches; the boolean indicates whether the node is an endpoint or not
addBranches :: [(s, DerivationTree s a)] -> DerivationTree s a -> DerivationTree s a Source
Branches are attached after the existing ones (order matters)
makeTree :: (a -> (Bool, [(s, a)])) -> a -> DerivationTree s a Source
Query
root :: DerivationTree s a -> a Source
The root of the tree
endpoint :: DerivationTree s a -> Bool Source
Is this node an endpoint?
branches :: DerivationTree s a -> [(s, DerivationTree s a)] Source
All branches
subtrees :: DerivationTree s a -> [DerivationTree s a] Source
Returns all subtrees at a given node
leafs :: DerivationTree s a -> [a] Source
Returns all leafs, i.e., final results in derivation. Be careful: the returned list may be very long
lengthMax :: Int -> DerivationTree s a -> Maybe Int Source
The argument supplied is the maximum number of steps; if more steps are needed, Nothing is returned
Adapters
restrictHeight :: Int -> DerivationTree s a -> DerivationTree s a Source
Restrict the height of the tree (by cutting off branches at a certain depth). Nodes at this particular depth are turned into endpoints
restrictWidth :: Int -> DerivationTree s a -> DerivationTree s a Source
Restrict the width of the tree (by cutting off branches).
updateAnnotations :: (a -> s -> a -> t) -> DerivationTree s a -> DerivationTree t a Source
cutOnStep :: (s -> Bool) -> DerivationTree s a -> DerivationTree s a Source
mergeMaybeSteps :: DerivationTree (Maybe s) a -> DerivationTree s a Source
sortTree :: (l -> l -> Ordering) -> DerivationTree l a -> DerivationTree l a Source
cutOnTerm :: (a -> Bool) -> DerivationTree s a -> DerivationTree s a Source
Conversions
derivation :: DerivationTree s a -> Maybe (Derivation s a) Source
The first derivation (if any)
randomDerivation :: RandomGen g => g -> DerivationTree s a -> Maybe (Derivation s a) Source
Return a random derivation (if any exists at all)
derivations :: DerivationTree s a -> [Derivation s a] Source
All possible derivations (returned in a list)