Portability | ghc |
---|---|
Stability | beta |
Maintainer | Neil Sculthorpe <neil@ittc.ku.edu> |
Safe Haskell | Safe-Inferred |
This module provides combinators that traverse a tree.
Note that all traversals take place on the node, its children, or its descendents. Deliberately, there is no mechanism for "ascending" the tree.
- class Walker c g where
- allR :: MonadCatch m => Rewrite c m g -> Rewrite c m g
- allT :: (MonadCatch m, Monoid b) => Translate c m g b -> Translate c m g b
- oneT :: MonadCatch m => Translate c m g b -> Translate c m g b
- anyR :: MonadCatch m => Rewrite c m g -> Rewrite c m g
- oneR :: MonadCatch m => Rewrite c m g -> Rewrite c m g
- childL :: MonadCatch m => Int -> Lens c m g g
- childR :: (Walker c g, MonadCatch m) => Int -> Rewrite c m g -> Rewrite c m g
- childT :: (Walker c g, MonadCatch m) => Int -> Translate c m g b -> Translate c m g b
- alltdR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m g
- allbuR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m g
- allduR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m g
- anytdR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m g
- anybuR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m g
- anyduR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m g
- onetdR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m g
- onebuR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m g
- prunetdR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m g
- innermostR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m g
- allLargestR :: (Walker c g, MonadCatch m) => Translate c m g Bool -> Rewrite c m g -> Rewrite c m g
- anyLargestR :: (Walker c g, MonadCatch m) => Translate c m g Bool -> Rewrite c m g -> Rewrite c m g
- oneLargestR :: (Walker c g, MonadCatch m) => Translate c m g Bool -> Rewrite c m g -> Rewrite c m g
- foldtdT :: (Walker c g, MonadCatch m, Monoid b) => Translate c m g b -> Translate c m g b
- foldbuT :: (Walker c g, MonadCatch m, Monoid b) => Translate c m g b -> Translate c m g b
- onetdT :: (Walker c g, MonadCatch m) => Translate c m g b -> Translate c m g b
- onebuT :: (Walker c g, MonadCatch m) => Translate c m g b -> Translate c m g b
- prunetdT :: (Walker c g, MonadCatch m, Monoid b) => Translate c m g b -> Translate c m g b
- crushtdT :: (Walker c g, MonadCatch m, Monoid b) => Translate c m g b -> Translate c m g b
- crushbuT :: (Walker c g, MonadCatch m, Monoid b) => Translate c m g b -> Translate c m g b
- collectT :: (Walker c g, MonadCatch m) => Translate c m g b -> Translate c m g [b]
- collectPruneT :: (Walker c g, MonadCatch m) => Translate c m g b -> Translate c m g [b]
- allLargestT :: (Walker c g, MonadCatch m, Monoid b) => Translate c m g Bool -> Translate c m g b -> Translate c m g b
- oneLargestT :: (Walker c g, MonadCatch m) => Translate c m g Bool -> Translate c m g b -> Translate c m g b
- numChildrenT :: (Walker c g, MonadCatch m) => Translate c m g Int
- hasChildT :: (Walker c g, MonadCatch m) => Int -> Translate c m g Bool
- summandIsTypeT :: forall c m a g. (MonadCatch m, Injection a g) => a -> Translate c m g Bool
- data AbsolutePath
- rootAbsPath :: AbsolutePath
- class PathContext c where
- absPath :: c -> AbsolutePath
- (@@) :: c -> Int -> c
- absPathT :: (PathContext c, Monad m) => Translate c m a AbsolutePath
- type Path = [Int]
- rootPath :: PathContext c => c -> Path
- rootPathT :: (PathContext c, Monad m) => Translate c m a Path
- pathsToT :: (PathContext c, Walker c g, MonadCatch m) => (g -> Bool) -> Translate c m g [Path]
- onePathToT :: (PathContext c, Walker c g, MonadCatch m) => (g -> Bool) -> Translate c m g Path
- oneNonEmptyPathToT :: (PathContext c, Walker c g, MonadCatch m) => (g -> Bool) -> Translate c m g Path
- prunePathsToT :: (PathContext c, Walker c g, MonadCatch m) => (g -> Bool) -> Translate c m g [Path]
- uniquePathToT :: (PathContext c, Walker c g, MonadCatch m) => (g -> Bool) -> Translate c m g Path
- uniquePrunePathToT :: (PathContext c, Walker c g, MonadCatch m) => (g -> Bool) -> Translate c m g Path
- pathL :: (Walker c g, MonadCatch m) => Path -> Lens c m g g
- exhaustPathL :: (Walker c g, MonadCatch m) => Path -> Lens c m g g
- repeatPathL :: (Walker c g, MonadCatch m) => Path -> Lens c m g g
- rootL :: (Walker c g, MonadCatch m) => AbsolutePath -> Lens c m g g
- pathR :: (Walker c g, MonadCatch m) => Path -> Rewrite c m g -> Rewrite c m g
- pathT :: (Walker c g, MonadCatch m) => Path -> Translate c m g b -> Translate c m g b
- testPathT :: (Walker c g, MonadCatch m) => Path -> Translate c m g Bool
Shallow Traversals
Tree Walkers
Walker
captures the ability to walk over a tree containing nodes of type g
,
using a specific context c
.
Minimal complete definition: allR
.
Default definitions are provided for anyR
, oneR
, allT
, oneT
, and childL
,
but they may be overridden for efficiency.
allR :: MonadCatch m => Rewrite c m g -> Rewrite c m gSource
Apply a Rewrite
to all immediate children, succeeding if they all succeed.
allT :: (MonadCatch m, Monoid b) => Translate c m g b -> Translate c m g bSource
Apply a Translate
to all immediate children, succeeding if they all succeed.
The results are combined in a Monoid
.
oneT :: MonadCatch m => Translate c m g b -> Translate c m g bSource
Apply a Translate
to the first immediate child for which it can succeed.
anyR :: MonadCatch m => Rewrite c m g -> Rewrite c m gSource
Apply a Rewrite
to all immediate children, suceeding if any succeed.
oneR :: MonadCatch m => Rewrite c m g -> Rewrite c m gSource
Apply a Rewrite
to the first immediate child for which it can succeed.
childL :: MonadCatch m => Int -> Lens c m g gSource
Construct a Lens
to the n-th child node.
Child Transformations
childR :: (Walker c g, MonadCatch m) => Int -> Rewrite c m g -> Rewrite c m gSource
Apply a Rewrite
to a specified child.
childT :: (Walker c g, MonadCatch m) => Int -> Translate c m g b -> Translate c m g bSource
Apply a Translate
to a specified child.
Deep Traversals
Rewrite Traversals
alltdR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m gSource
Apply a Rewrite
in a top-down manner, succeeding if they all succeed.
allbuR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m gSource
Apply a Rewrite
in a bottom-up manner, succeeding if they all succeed.
allduR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m gSource
Apply a Rewrite
twice, in a top-down and bottom-up way, using one single tree traversal,
succeeding if they all succeed.
anytdR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m gSource
Apply a Rewrite
in a top-down manner, succeeding if any succeed.
anybuR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m gSource
Apply a Rewrite
in a bottom-up manner, succeeding if any succeed.
anyduR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m gSource
Apply a Rewrite
twice, in a top-down and bottom-up way, using one single tree traversal,
succeeding if any succeed.
onetdR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m gSource
Apply a Rewrite
to the first node for which it can succeed, in a top-down traversal.
onebuR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m gSource
Apply a Rewrite
to the first node for which it can succeed, in a bottom-up traversal.
prunetdR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m gSource
Attempt to apply a Rewrite
in a top-down manner, pruning at successful rewrites.
innermostR :: (Walker c g, MonadCatch m) => Rewrite c m g -> Rewrite c m gSource
A fixed-point traveral, starting with the innermost term.
allLargestR :: (Walker c g, MonadCatch m) => Translate c m g Bool -> Rewrite c m g -> Rewrite c m gSource
Apply a Rewrite
to the largest node(s) that satisfy the predicate, requiring all to succeed.
anyLargestR :: (Walker c g, MonadCatch m) => Translate c m g Bool -> Rewrite c m g -> Rewrite c m gSource
Apply a Rewrite
to the largest node(s) that satisfy the predicate, succeeding if any succeed.
oneLargestR :: (Walker c g, MonadCatch m) => Translate c m g Bool -> Rewrite c m g -> Rewrite c m gSource
Apply a Rewrite
to the first node for which it can succeed among the largest node(s) that satisfy the predicate.
Translate Traversals
foldtdT :: (Walker c g, MonadCatch m, Monoid b) => Translate c m g b -> Translate c m g bSource
Fold a tree in a top-down manner, using a single Translate
for each node.
foldbuT :: (Walker c g, MonadCatch m, Monoid b) => Translate c m g b -> Translate c m g bSource
Fold a tree in a bottom-up manner, using a single Translate
for each node.
onetdT :: (Walker c g, MonadCatch m) => Translate c m g b -> Translate c m g bSource
Apply a Translate
to the first node for which it can succeed, in a top-down traversal.
onebuT :: (Walker c g, MonadCatch m) => Translate c m g b -> Translate c m g bSource
Apply a Translate
to the first node for which it can succeed, in a bottom-up traversal.
prunetdT :: (Walker c g, MonadCatch m, Monoid b) => Translate c m g b -> Translate c m g bSource
Attempt to apply a Translate
in a top-down manner, pruning at successes.
crushtdT :: (Walker c g, MonadCatch m, Monoid b) => Translate c m g b -> Translate c m g bSource
An always successful top-down fold, replacing failures with mempty
.
crushbuT :: (Walker c g, MonadCatch m, Monoid b) => Translate c m g b -> Translate c m g bSource
An always successful bottom-up fold, replacing failures with mempty
.
collectT :: (Walker c g, MonadCatch m) => Translate c m g b -> Translate c m g [b]Source
An always successful traversal that collects the results of all successful applications of a Translate
in a list.
collectPruneT :: (Walker c g, MonadCatch m) => Translate c m g b -> Translate c m g [b]Source
Like collectT
, but does not traverse below successes.
allLargestT :: (Walker c g, MonadCatch m, Monoid b) => Translate c m g Bool -> Translate c m g b -> Translate c m g bSource
Apply a Translate
to the largest node(s) that satisfy the predicate, combining the results in a monoid.
oneLargestT :: (Walker c g, MonadCatch m) => Translate c m g Bool -> Translate c m g b -> Translate c m g bSource
Apply a Translate
to the first node for which it can succeed among the largest node(s) that satisfy the predicate.
Utilitity Translations
numChildrenT :: (Walker c g, MonadCatch m) => Translate c m g IntSource
Count the number of children of the current node.
hasChildT :: (Walker c g, MonadCatch m) => Int -> Translate c m g BoolSource
Determine if the current node has a child of the specified number.
Useful when defining custom versions of childL
.
summandIsTypeT :: forall c m a g. (MonadCatch m, Injection a g) => a -> Translate c m g BoolSource
Test if the type of the current node summand matches the type of the argument. Note that the argument value is never inspected, it is merely a proxy for a type argument.
Paths
Absolute Paths
data AbsolutePath Source
A path from the root.
Eq AbsolutePath | |
Show AbsolutePath | |
PathContext AbsolutePath | The simplest instance of |
rootAbsPath :: AbsolutePathSource
The (empty) AbsolutePath
to the root.
class PathContext c whereSource
Contexts that are instances of PathContext
contain the current AbsolutePath
.
Any user-defined combinators (typically allR
and congruence combinators) should update the AbsolutePath
using @@
.
absPath :: c -> AbsolutePathSource
Retrieve the current absolute path.
Extend the current absolute path by one descent.
PathContext AbsolutePath | The simplest instance of |
absPathT :: (PathContext c, Monad m) => Translate c m a AbsolutePathSource
Lifted version of absPath
.
Relative Paths
rootPath :: PathContext c => c -> PathSource
Retrieve the Path
from the root to the current node.
pathsToT :: (PathContext c, Walker c g, MonadCatch m) => (g -> Bool) -> Translate c m g [Path]Source
Find the Path
s to every node that satisfies the predicate.
onePathToT :: (PathContext c, Walker c g, MonadCatch m) => (g -> Bool) -> Translate c m g PathSource
Find the Path
to the first node that satisfies the predicate (in a pre-order traversal).
oneNonEmptyPathToT :: (PathContext c, Walker c g, MonadCatch m) => (g -> Bool) -> Translate c m g PathSource
Find the Path
to the first descendent node that satisfies the predicate (in a pre-order traversal).
prunePathsToT :: (PathContext c, Walker c g, MonadCatch m) => (g -> Bool) -> Translate c m g [Path]Source
Find the Path
s to every node that satisfies the predicate, ignoring nodes below successes.
uniquePathToT :: (PathContext c, Walker c g, MonadCatch m) => (g -> Bool) -> Translate c m g PathSource
Find the Path
to the node that satisfies the predicate, failing if that does not uniquely identify a node.
uniquePrunePathToT :: (PathContext c, Walker c g, MonadCatch m) => (g -> Bool) -> Translate c m g PathSource
Build a Path
to the node that satisfies the predicate, failing if that does not uniquely identify a node (ignoring nodes below successes).
Building Lenses from Paths
exhaustPathL :: (Walker c g, MonadCatch m) => Path -> Lens c m g gSource
repeatPathL :: (Walker c g, MonadCatch m) => Path -> Lens c m g gSource
Repeat as many iterations of the Path
as possible.
rootL :: (Walker c g, MonadCatch m) => AbsolutePath -> Lens c m g gSource
Build a Lens
from the root to a point specified by an AbsolutePath
.