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