Portability | ghc |
---|---|

Stability | beta |

Maintainer | Neil Sculthorpe <neil@ittc.ku.edu> |

Safe Haskell | Safe-Infered |

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 (Injection a (Generic a), Generic a ~ Generic (Generic a)) => Node a where
- type Generic a :: *
- numChildren :: a -> Int

- numChildrenT :: (Monad m, Node a) => Translate c m a Int
- hasChild :: Node a => Int -> a -> Bool
- hasChildT :: (Monad m, Node a) => Int -> Translate c m a Bool
- class (MonadCatch m, Node a) => Walker c m a where
- childL :: Int -> Lens c m a (Generic a)
- allT :: Monoid b => Translate c m (Generic a) b -> Translate c m a b
- oneT :: Translate c m (Generic a) b -> Translate c m a b
- allR :: Rewrite c m (Generic a) -> Rewrite c m a
- anyR :: Rewrite c m (Generic a) -> Rewrite c m a
- oneR :: Rewrite c m (Generic a) -> Rewrite c m a

- childR :: Walker c m a => Int -> Rewrite c m (Generic a) -> Rewrite c m a
- alltdR :: (Walker c m a, a ~ Generic a) => Rewrite c m (Generic a) -> Rewrite c m (Generic a)
- allbuR :: (Walker c m a, a ~ Generic a) => Rewrite c m (Generic a) -> Rewrite c m (Generic a)
- allduR :: (Walker c m a, a ~ Generic a) => Rewrite c m (Generic a) -> Rewrite c m (Generic a)
- anytdR :: (Walker c m a, a ~ Generic a) => Rewrite c m (Generic a) -> Rewrite c m (Generic a)
- anybuR :: (Walker c m a, a ~ Generic a) => Rewrite c m (Generic a) -> Rewrite c m (Generic a)
- anyduR :: (Walker c m a, a ~ Generic a) => Rewrite c m (Generic a) -> Rewrite c m (Generic a)
- onetdR :: (Walker c m a, a ~ Generic a) => Rewrite c m (Generic a) -> Rewrite c m (Generic a)
- onebuR :: (Walker c m a, a ~ Generic a) => Rewrite c m (Generic a) -> Rewrite c m (Generic a)
- prunetdR :: (Walker c m a, a ~ Generic a) => Rewrite c m (Generic a) -> Rewrite c m (Generic a)
- innermostR :: (Walker c m a, Generic a ~ a) => Rewrite c m (Generic a) -> Rewrite c m (Generic a)
- childT :: Walker c m a => Int -> Translate c m (Generic a) b -> Translate c m a b
- foldtdT :: (Walker c m a, Monoid b, a ~ Generic a) => Translate c m (Generic a) b -> Translate c m (Generic a) b
- foldbuT :: (Walker c m a, Monoid b, a ~ Generic a) => Translate c m (Generic a) b -> Translate c m (Generic a) b
- onetdT :: (Walker c m a, a ~ Generic a) => Translate c m (Generic a) b -> Translate c m (Generic a) b
- onebuT :: (Walker c m a, a ~ Generic a) => Translate c m (Generic a) b -> Translate c m (Generic a) b
- prunetdT :: (Walker c m a, Monoid b, a ~ Generic a) => Translate c m (Generic a) b -> Translate c m (Generic a) b
- crushtdT :: (Walker c m a, Monoid b, a ~ Generic a) => Translate c m (Generic a) b -> Translate c m (Generic a) b
- crushbuT :: (Walker c m a, Monoid b, a ~ Generic a) => Translate c m (Generic a) b -> Translate c m (Generic a) b
- collectT :: (Walker c m a, a ~ Generic a) => Translate c m (Generic a) b -> Translate c m (Generic a) [b]
- collectPruneT :: (Walker c m a, a ~ Generic a) => Translate c m (Generic a) b -> Translate c m (Generic a) [b]
- data AbsolutePath
- rootAbsPath :: AbsolutePath
- extendAbsPath :: Int -> AbsolutePath -> AbsolutePath
- class PathContext c where
- contextPath :: c -> AbsolutePath

- absPathT :: (PathContext c, Monad m) => Translate c m a AbsolutePath
- type Path = [Int]
- rootPath :: AbsolutePath -> Path
- pathsToT :: (PathContext c, Walker c m a, a ~ Generic a) => (Generic a -> Bool) -> Translate c m (Generic a) [Path]
- onePathToT :: (PathContext c, Walker c m a, a ~ Generic a) => (Generic a -> Bool) -> Translate c m (Generic a) Path
- oneNonEmptyPathToT :: (PathContext c, Walker c m a, a ~ Generic a) => (Generic a -> Bool) -> Translate c m (Generic a) Path
- prunePathsToT :: (PathContext c, Walker c m a, a ~ Generic a) => (Generic a -> Bool) -> Translate c m (Generic a) [Path]
- uniquePathToT :: (PathContext c, Walker c m a, a ~ Generic a) => (Generic a -> Bool) -> Translate c m (Generic a) Path
- uniquePrunePathToT :: (PathContext c, Walker c m a, a ~ Generic a) => (Generic a -> Bool) -> Translate c m (Generic a) Path
- pathL :: (Walker c m a, a ~ Generic a) => Path -> Lens c m (Generic a) (Generic a)
- exhaustPathL :: (Walker c m a, a ~ Generic a) => Path -> Lens c m (Generic a) (Generic a)
- repeatPathL :: (Walker c m a, a ~ Generic a) => Path -> Lens c m (Generic a) (Generic a)
- rootL :: (Walker c m a, a ~ Generic a) => AbsolutePath -> Lens c m (Generic a) (Generic a)
- pathR :: (Walker c m a, a ~ Generic a) => Path -> Rewrite c m (Generic a) -> Rewrite c m (Generic a)
- pathT :: (Walker c m a, a ~ Generic a) => Path -> Translate c m (Generic a) b -> Translate c m (Generic a) b
- testPathT :: (Walker c m a, a ~ Generic a) => Path -> Translate c m a Bool

# Nodes

class (Injection a (Generic a), Generic a ~ Generic (Generic a)) => Node a whereSource

A `Node`

is any node in the tree that you wish to be able to traverse.

`Generic`

is a sum of all the types of the sub-nodes, transitively, of `a`

.
We use `Generic a ~ a`

to signify that something is its own Generic.
Simple expression types might be their own sole `Generic`

, more complex examples
will have a new datatype for the `Generic`

, which will also be an instance of class `Node`

.

numChildren :: a -> IntSource

Count the number of immediate child `Node`

s.

numChildrenT :: (Monad m, Node a) => Translate c m a IntSource

Lifted version of `numChildren`

.

# Tree Walkers

class (MonadCatch m, Node a) => Walker c m a whereSource

`Walker`

captures the ability to walk over a tree of `Node`

s,
using a specific context `c`

and a `MonadCatch`

`m`

.

Minimal complete definition: `childL`

.

Default definitions are provided for `allT`

, `oneT`

, `allR`

, `anyR`

and `oneR`

, but they may be overridden for efficiency.
For small numbers of interesting children this will not be an issue, but for a large number,
say for a list of children, it may be.

childL :: Int -> Lens c m a (Generic a)Source

allT :: Monoid b => Translate c m (Generic a) b -> Translate c m a bSource

Apply a `Generic`

`Translate`

to all immediate children, succeeding if they all succeed.
The results are combined in a `Monoid`

.

oneT :: Translate c m (Generic a) b -> Translate c m a bSource

allR :: Rewrite c m (Generic a) -> Rewrite c m aSource

# Rewrite Traversals

childR :: Walker c m a => Int -> Rewrite c m (Generic a) -> Rewrite c m aSource

Apply a `Rewrite`

to a specified child.

alltdR :: (Walker c m a, a ~ Generic a) => Rewrite c m (Generic a) -> Rewrite c m (Generic a)Source

Apply a `Rewrite`

in a top-down manner, succeeding if they all succeed.

allbuR :: (Walker c m a, a ~ Generic a) => Rewrite c m (Generic a) -> Rewrite c m (Generic a)Source

Apply a `Rewrite`

in a bottom-up manner, succeeding if they all succeed.

allduR :: (Walker c m a, a ~ Generic a) => Rewrite c m (Generic a) -> Rewrite c m (Generic a)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 m a, a ~ Generic a) => Rewrite c m (Generic a) -> Rewrite c m (Generic a)Source

Apply a `Rewrite`

in a top-down manner, succeeding if any succeed.

anybuR :: (Walker c m a, a ~ Generic a) => Rewrite c m (Generic a) -> Rewrite c m (Generic a)Source

Apply a `Rewrite`

in a bottom-up manner, succeeding if any succeed.

anyduR :: (Walker c m a, a ~ Generic a) => Rewrite c m (Generic a) -> Rewrite c m (Generic a)Source

Apply a `Rewrite`

twice, in a top-down and bottom-up way, using one single tree traversal,
succeeding if any succeed.

prunetdR :: (Walker c m a, a ~ Generic a) => Rewrite c m (Generic a) -> Rewrite c m (Generic a)Source

Attempt to apply a `Rewrite`

in a top-down manner, pruning at successful rewrites.

innermostR :: (Walker c m a, Generic a ~ a) => Rewrite c m (Generic a) -> Rewrite c m (Generic a)Source

A fixed-point traveral, starting with the innermost term.

# Translate Traversals

childT :: Walker c m a => Int -> Translate c m (Generic a) b -> Translate c m a bSource

Apply a `Translate`

to a specified child.

foldtdT :: (Walker c m a, Monoid b, a ~ Generic a) => Translate c m (Generic a) b -> Translate c m (Generic a) bSource

foldbuT :: (Walker c m a, Monoid b, a ~ Generic a) => Translate c m (Generic a) b -> Translate c m (Generic a) bSource

onetdT :: (Walker c m a, a ~ Generic a) => Translate c m (Generic a) b -> Translate c m (Generic a) bSource

onebuT :: (Walker c m a, a ~ Generic a) => Translate c m (Generic a) b -> Translate c m (Generic a) bSource

prunetdT :: (Walker c m a, Monoid b, a ~ Generic a) => Translate c m (Generic a) b -> Translate c m (Generic a) bSource

Attempt to apply a `Translate`

in a top-down manner, pruning at successes.

crushtdT :: (Walker c m a, Monoid b, a ~ Generic a) => Translate c m (Generic a) b -> Translate c m (Generic a) bSource

An always successful top-down fold, replacing failures with `mempty`

.

crushbuT :: (Walker c m a, Monoid b, a ~ Generic a) => Translate c m (Generic a) b -> Translate c m (Generic a) bSource

An always successful bottom-up fold, replacing failures with `mempty`

.

collectT :: (Walker c m a, a ~ Generic a) => Translate c m (Generic a) b -> Translate c m (Generic a) [b]Source

An always successful traversal that collects the results of all successful applications of a `Translate`

in a list.

collectPruneT :: (Walker c m a, a ~ Generic a) => Translate c m (Generic a) b -> Translate c m (Generic a) [b]Source

Like `collectT`

, but does not traverse below successes.

# Paths

## Absolute Paths

data AbsolutePath Source

A path from the root.

Show AbsolutePath | |

PathContext AbsolutePath | The simplest instance of |

rootAbsPath :: AbsolutePathSource

The (empty) `AbsolutePath`

to the root.

extendAbsPath :: Int -> AbsolutePath -> AbsolutePathSource

Extend an `AbsolutePath`

by one descent.

class PathContext c whereSource

Contexts that are instances of `PathContext`

contain the current `AbsolutePath`

.
Any user-defined combinators (typically `childL`

and congruence combinators) should update the `AbsolutePath`

using `extendAbsPath`

.

contextPath :: c -> AbsolutePathSource

Find the current path.

PathContext AbsolutePath | The simplest instance of |

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

Find the `AbsolutePath`

to the current `Node`

.

## Relative Paths

rootPath :: AbsolutePath -> PathSource

Convert an `AbsolutePath`

into a `Path`

starting at the root.

pathsToT :: (PathContext c, Walker c m a, a ~ Generic a) => (Generic a -> Bool) -> Translate c m (Generic a) [Path]Source

onePathToT :: (PathContext c, Walker c m a, a ~ Generic a) => (Generic a -> Bool) -> Translate c m (Generic a) PathSource

oneNonEmptyPathToT :: (PathContext c, Walker c m a, a ~ Generic a) => (Generic a -> Bool) -> Translate c m (Generic a) PathSource

prunePathsToT :: (PathContext c, Walker c m a, a ~ Generic a) => (Generic a -> Bool) -> Translate c m (Generic a) [Path]Source

uniquePathToT :: (PathContext c, Walker c m a, a ~ Generic a) => (Generic a -> Bool) -> Translate c m (Generic a) PathSource

uniquePrunePathToT :: (PathContext c, Walker c m a, a ~ Generic a) => (Generic a -> Bool) -> Translate c m (Generic a) PathSource

# Using Paths

## Building Lenses from Paths

repeatPathL :: (Walker c m a, a ~ Generic a) => Path -> Lens c m (Generic a) (Generic a)Source

Repeat as many iterations of the `Path`

as possible.

rootL :: (Walker c m a, a ~ Generic a) => AbsolutePath -> Lens c m (Generic a) (Generic a)Source

Build a `Lens`

from the root to a point specified by an `AbsolutePath`

.

## Applying transformations at the end of Paths

pathR :: (Walker c m a, a ~ Generic a) => Path -> Rewrite c m (Generic a) -> Rewrite c m (Generic a)Source

pathT :: (Walker c m a, a ~ Generic a) => Path -> Translate c m (Generic a) b -> Translate c m (Generic a) bSource