kure-2.16.12: Combinators for Strategic Programming

Copyright (c) 2012--2014 The University of Kansas BSD3 Neil Sculthorpe beta ghc None Haskell2010

Language.KURE.Walker

Description

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

# 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.

Minimal complete definition

allR

Methods

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.

Instances

 Typeable (* -> * -> Constraint) Walker

## 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

Construct a `Lens` by following a `Path`.

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

Build a `Lens` from the root to a point specified by a `LocalPath`.

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

Construct a `Lens` that points to the last node at which the `Path` can be followed.

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`.

## Testing Paths

testPathT :: (ReadPath c crumb, Eq crumb, Walker c u, MonadCatch m) => Path crumb -> Transform c m u Bool Source

Check if it is possible to construct a `Lens` along this path from the current node.