Portability	ghc
Stability	beta
Maintainer	Neil Sculthorpe <neil@ittc.ku.edu>
Safe Haskell	Safe-Inferred

Language.KURE.Walker

Contents

Shallow Traversals
- Tree Walkers
- Child Transformations
Deep Traversals
- Rewrite Traversals
- Translate Traversals
Utilitity Translations
Paths

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 g whereSource

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.

Methods

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 Int Source

Count the number of children of the current node.

hasChildT :: (Walker c g, MonadCatch m) => Int -> Translate c m g Bool Source

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

Absolute Paths

data AbsolutePath Source

A path from the root.

Instances

Eq AbsolutePath
Show AbsolutePath
PathContext AbsolutePath	The simplest instance of `PathContext` is `AbsolutePath` itself.

rootAbsPath :: AbsolutePath Source

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

Methods

absPath :: c -> AbsolutePath Source

Retrieve the current absolute path.

(@@) :: c -> Int -> cSource

Extend the current absolute path by one descent.

Instances

PathContext AbsolutePath

The simplest instance of PathContext is AbsolutePath itself.

absPathT :: (PathContext c, Monad m) => Translate c m a AbsolutePath Source

Lifted version of absPath.

Relative Paths

type Path = [Int]Source

A path is a route to descend the tree from an arbitrary node.

rootPath :: PathContext c => c -> Path Source

Retrieve the Path from the root to the current node.

rootPathT :: (PathContext c, Monad m) => Translate c m a Path Source

Lifted version of rootPath.

pathsToT :: (PathContext c, Walker c g, MonadCatch m) => (g -> Bool) -> Translate c m g [Path]Source

Find the Paths to every node that satisfies the predicate.

onePathToT :: (PathContext c, Walker c g, MonadCatch m) => (g -> Bool) -> Translate c m g Path Source

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 Path Source

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 Paths 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 Path Source

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 Path Source

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

pathL :: (Walker c g, MonadCatch m) => Path -> Lens c m g gSource

Construct a Lens by following a Path.

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

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

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.

Applying transformations at the end of Paths

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

Apply a Rewrite at a point specified by a Path.

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

Apply a Translate at a point specified by a Path.

Testing Paths

testPathT :: (Walker c g, MonadCatch m) => Path -> Translate c m g Bool Source

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