Ideas.Common.DerivationTree

Datatype for representing derivations as a tree. The datatype stores all intermediate results as well as annotations for the steps.

Data types

data DerivationTree s a

Instances

BiFunctor DerivationTree

Methods

biMap :: (a -> c) -> (b -> d) -> DerivationTree a b -> DerivationTree c d

mapFirst :: (a -> b) -> DerivationTree a c -> DerivationTree b c

mapSecond :: (b -> c) -> DerivationTree a b -> DerivationTree a c

Functor (DerivationTree s)

Methods

fmap :: (a -> b) -> DerivationTree s a -> DerivationTree s b

(<$) :: a -> DerivationTree s b -> DerivationTree s a

(Show s, Show a) => Show (DerivationTree s a)

Methods

showsPrec :: Int -> DerivationTree s a -> ShowS

show :: DerivationTree s a -> String

showList :: [DerivationTree s a] -> ShowS

Constructors

singleNode :: a -> Bool -> DerivationTree s a

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

Branches are attached after the existing ones (order matters)

makeTree :: (a -> (Bool, [(s, a)])) -> a -> DerivationTree s a

Query

root :: DerivationTree s a -> a

The root of the tree

endpoint :: DerivationTree s a -> Bool

Is this node an endpoint?

branches :: DerivationTree s a -> [(s, DerivationTree s a)]

All branches

subtrees :: DerivationTree s a -> [DerivationTree s a]

Returns all subtrees at a given node

leafs :: DerivationTree s a -> [a]

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

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

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

Restrict the width of the tree (by cutting off branches).

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

Conversions

derivation :: DerivationTree s a -> Maybe (Derivation s a)

The first derivation (if any)

randomDerivation :: RandomGen g => g -> DerivationTree s a -> Maybe (Derivation s a)

Return a random derivation (if any exists at all)

derivations :: DerivationTree s a -> [Derivation s a]

All possible derivations (returned in a list)