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 :: (ReadPath c crumb, Eq crumb, MonadCatch m) => crumb -> Lens c m g g

- childR :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => crumb -> Rewrite c m g -> Rewrite c m g
- childT :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => crumb -> 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
- childrenT :: (ReadPath c crumb, Walker c g, MonadCatch m) => Translate c m g [crumb]
- summandIsTypeT :: forall c m a g. (MonadCatch m, Injection a g) => a -> Translate c m g Bool
- pathL :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => Path crumb -> Lens c m g g
- localPathL :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => LocalPath crumb -> Lens c m g g
- exhaustPathL :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => Path crumb -> Lens c m g g
- repeatPathL :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => Path crumb -> Lens c m g g
- pathR :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => Path crumb -> Rewrite c m g -> Rewrite c m g
- pathT :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => Path crumb -> Translate c m g b -> Translate c m g b
- localPathR :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => LocalPath crumb -> Rewrite c m g -> Rewrite c m g
- localPathT :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => LocalPath crumb -> Translate c m g b -> Translate c m g b
- testPathT :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => Path crumb -> 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 :: (ReadPath c crumb, Eq crumb, MonadCatch m) => crumb -> Lens c m g gSource

Construct a `Lens`

to the n-th child node.

## Child Transformations

childR :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => crumb -> Rewrite c m g -> Rewrite c m gSource

Apply a `Rewrite`

to a specified child.

childT :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => crumb -> 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

childrenT :: (ReadPath c crumb, Walker c g, MonadCatch m) => Translate c m g [crumb]Source

List the children of the current node.

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

## Building Lenses from Paths

localPathL :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => LocalPath crumb -> Lens c m g gSource

exhaustPathL :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => Path crumb -> Lens c m g gSource

repeatPathL :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => Path crumb -> Lens c m g gSource

Repeat as many iterations of the `Path`

as possible.

## Applying transformations at the end of Paths

pathR :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => Path crumb -> Rewrite c m g -> Rewrite c m gSource

pathT :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => Path crumb -> Translate c m g b -> Translate c m g bSource

localPathR :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => LocalPath crumb -> Rewrite c m g -> Rewrite c m gSource

localPathT :: (ReadPath c crumb, Eq crumb, Walker c g, MonadCatch m) => LocalPath crumb -> Translate c m g b -> Translate c m g bSource