Copyright | (c) 2012--2021 The University of Kansas |
---|---|
License | BSD3 |
Maintainer | Neil Sculthorpe <neil.sculthorpe@ntu.ac.uk> |
Stability | beta |
Portability | ghc |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
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.
Synopsis
- class Walker c u where
- allR :: MonadCatch m => Rewrite c m u -> Rewrite c m u
- allT :: (MonadCatch m, Monoid b) => Transform c m u b -> Transform c m u b
- oneT :: MonadCatch m => Transform c m u b -> Transform c m u b
- anyR :: MonadCatch m => Rewrite c m u -> Rewrite c m u
- oneR :: MonadCatch m => Rewrite c m u -> Rewrite c m u
- childL :: (ReadPath c crumb, Eq crumb, MonadCatch m) => crumb -> Lens c m u u
- childR :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => crumb -> Rewrite c m u -> Rewrite c m u
- childT :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => crumb -> Transform c m u b -> Transform c m u b
- alltdR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u
- allbuR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u
- allduR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u
- anytdR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u
- anybuR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u
- anyduR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u
- onetdR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u
- onebuR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u
- prunetdR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u
- innermostR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u
- allLargestR :: (Walker c u, MonadCatch m) => Transform c m u Bool -> Rewrite c m u -> Rewrite c m u
- anyLargestR :: (Walker c u, MonadCatch m) => Transform c m u Bool -> Rewrite c m u -> Rewrite c m u
- oneLargestR :: (Walker c u, MonadCatch m) => Transform c m u Bool -> Rewrite c m u -> Rewrite c m u
- foldtdT :: (Walker c u, MonadCatch m, Monoid b) => Transform c m u b -> Transform c m u b
- foldbuT :: (Walker c u, MonadCatch m, Monoid b) => Transform c m u b -> Transform c m u b
- onetdT :: (Walker c u, MonadCatch m) => Transform c m u b -> Transform c m u b
- onebuT :: (Walker c u, MonadCatch m) => Transform c m u b -> Transform c m u b
- prunetdT :: (Walker c u, MonadCatch m, Monoid b) => Transform c m u b -> Transform c m u b
- crushtdT :: (Walker c u, MonadCatch m, Monoid b) => Transform c m u b -> Transform c m u b
- crushbuT :: (Walker c u, MonadCatch m, Monoid b) => Transform c m u b -> Transform c m u b
- collectT :: (Walker c u, MonadCatch m) => Transform c m u b -> Transform c m u [b]
- collectPruneT :: (Walker c u, MonadCatch m) => Transform c m u b -> Transform c m u [b]
- allLargestT :: (Walker c u, MonadCatch m, Monoid b) => Transform c m u Bool -> Transform c m u b -> Transform c m u b
- oneLargestT :: (Walker c u, MonadCatch m) => Transform c m u Bool -> Transform c m u b -> Transform c m u b
- childrenT :: (ReadPath c crumb, Walker c u, MonadCatch m) => Transform c m u [crumb]
- summandIsTypeT :: forall c m a u. (MonadCatch m, Injection a u) => a -> Transform c m u Bool
- pathL :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => Path crumb -> Lens c m u u
- localPathL :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => LocalPath crumb -> Lens c m u u
- exhaustPathL :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => Path crumb -> Lens c m u u
- repeatPathL :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => Path crumb -> Lens c m u u
- pathR :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => Path crumb -> Rewrite c m u -> Rewrite c m u
- pathT :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => Path crumb -> Transform c m u b -> Transform c m u b
- localPathR :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => LocalPath crumb -> Rewrite c m u -> Rewrite c m u
- localPathT :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => LocalPath crumb -> Transform c m u b -> Transform c m u b
- testPathT :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => Path crumb -> Transform c m u Bool
Shallow Traversals
Tree Walkers
class Walker c u where Source #
Walker
captures the ability to walk over a tree containing nodes of type u
,
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 u -> Rewrite c m u Source #
Apply a rewrite to all immediate children, succeeding if they all succeed.
allT :: (MonadCatch m, Monoid b) => Transform c m u b -> Transform c m u b Source #
Apply a transformation to all immediate children, succeeding if they all succeed.
The results are combined in a Monoid
.
oneT :: MonadCatch m => Transform c m u b -> Transform c m u b Source #
Apply a transformation to the first immediate child for which it can succeed.
anyR :: MonadCatch m => Rewrite c m u -> Rewrite c m u Source #
Apply a rewrite to all immediate children, suceeding if any succeed.
oneR :: MonadCatch m => Rewrite c m u -> Rewrite c m u Source #
Apply a rewrite to the first immediate child for which it can succeed.
childL :: (ReadPath c crumb, Eq crumb, MonadCatch m) => crumb -> Lens c m u u Source #
Construct a Lens
to the n-th child node.
Child Transformations
childR :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => crumb -> Rewrite c m u -> Rewrite c m u Source #
Apply a rewrite to a specified child.
childT :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => crumb -> Transform c m u b -> Transform c m u b Source #
Apply a transformation to a specified child.
Deep Traversals
Traversals for Rewrites
alltdR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u Source #
Apply a rewrite in a top-down manner, succeeding if they all succeed.
allbuR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u Source #
Apply a rewrite in a bottom-up manner, succeeding if they all succeed.
allduR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u Source #
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 u, MonadCatch m) => Rewrite c m u -> Rewrite c m u Source #
Apply a rewrite in a top-down manner, succeeding if any succeed.
anybuR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u Source #
Apply a rewrite in a bottom-up manner, succeeding if any succeed.
anyduR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u Source #
Apply a rewrite twice, in a top-down and bottom-up way, using one single tree traversal, succeeding if any succeed.
onetdR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u Source #
Apply a rewrite to the first node for which it can succeed, in a top-down traversal.
onebuR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u Source #
Apply a rewrite to the first node for which it can succeed, in a bottom-up traversal.
prunetdR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u Source #
Attempt to apply a Rewrite
in a top-down manner, pruning at successful rewrites.
innermostR :: (Walker c u, MonadCatch m) => Rewrite c m u -> Rewrite c m u Source #
A fixed-point traveral, starting with the innermost term.
allLargestR :: (Walker c u, MonadCatch m) => Transform c m u Bool -> Rewrite c m u -> Rewrite c m u Source #
Apply a rewrite to the largest node(s) that satisfy the predicate, requiring all to succeed.
anyLargestR :: (Walker c u, MonadCatch m) => Transform c m u Bool -> Rewrite c m u -> Rewrite c m u Source #
Apply a rewrite to the largest node(s) that satisfy the predicate, succeeding if any succeed.
oneLargestR :: (Walker c u, MonadCatch m) => Transform c m u Bool -> Rewrite c m u -> Rewrite c m u Source #
Apply a rewrite to the first node for which it can succeed among the largest node(s) that satisfy the predicate.
Traversals for Transformations
foldtdT :: (Walker c u, MonadCatch m, Monoid b) => Transform c m u b -> Transform c m u b Source #
Fold a tree in a top-down manner, using a single Transform
for each node.
foldbuT :: (Walker c u, MonadCatch m, Monoid b) => Transform c m u b -> Transform c m u b Source #
Fold a tree in a bottom-up manner, using a single Transform
for each node.
onetdT :: (Walker c u, MonadCatch m) => Transform c m u b -> Transform c m u b Source #
Apply a transformation to the first node for which it can succeed, in a top-down traversal.
onebuT :: (Walker c u, MonadCatch m) => Transform c m u b -> Transform c m u b Source #
Apply a transformation to the first node for which it can succeed, in a bottom-up traversal.
prunetdT :: (Walker c u, MonadCatch m, Monoid b) => Transform c m u b -> Transform c m u b Source #
Attempt to apply a Transform
in a top-down manner, pruning at successes.
crushtdT :: (Walker c u, MonadCatch m, Monoid b) => Transform c m u b -> Transform c m u b Source #
An always successful top-down fold, replacing failures with mempty
.
crushbuT :: (Walker c u, MonadCatch m, Monoid b) => Transform c m u b -> Transform c m u b Source #
An always successful bottom-up fold, replacing failures with mempty
.
collectT :: (Walker c u, MonadCatch m) => Transform c m u b -> Transform c m u [b] Source #
An always successful traversal that collects the results of all successful applications of a Transform
in a list.
collectPruneT :: (Walker c u, MonadCatch m) => Transform c m u b -> Transform c m u [b] Source #
Like collectT
, but does not traverse below successes.
allLargestT :: (Walker c u, MonadCatch m, Monoid b) => Transform c m u Bool -> Transform c m u b -> Transform c m u b Source #
Apply a transformation to the largest node(s) that satisfy the predicate, combining the results in a monoid.
oneLargestT :: (Walker c u, MonadCatch m) => Transform c m u Bool -> Transform c m u b -> Transform c m u b Source #
Apply a transformation to the first node for which it can succeed among the largest node(s) that satisfy the predicate.
Utilitity Transformations
childrenT :: (ReadPath c crumb, Walker c u, MonadCatch m) => Transform c m u [crumb] Source #
List the children of the current node.
summandIsTypeT :: forall c m a u. (MonadCatch m, Injection a u) => a -> Transform c m u Bool Source #
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
Building Lenses from Paths
pathL :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => Path crumb -> Lens c m u u Source #
localPathL :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => LocalPath crumb -> Lens c m u u Source #
exhaustPathL :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => Path crumb -> Lens c m u u Source #
repeatPathL :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => Path crumb -> Lens c m u u Source #
Repeat as many iterations of the Path
as possible.
Applying transformations at the end of Paths
pathR :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => Path crumb -> Rewrite c m u -> Rewrite c m u Source #
Apply a rewrite at a point specified by a Path
.
pathT :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => Path crumb -> Transform c m u b -> Transform c m u b Source #
Apply a transformation at a point specified by a Path
.
localPathR :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => LocalPath crumb -> Rewrite c m u -> Rewrite c m u Source #
Apply a rewrite at a point specified by a LocalPath
.
localPathT :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => LocalPath crumb -> Transform c m u b -> Transform c m u b Source #
Apply a transformation at a point specified by a LocalPath
.