Language.KURE.Walker

This module provides combinators that traverse a tree.

Note that all traversals take place on the node, its children, or its descendents. There is no mechanism for "ascending" the tree.

Traversal Classes

class (Injection a (Generic a), Generic a ~ Generic (Generic a)) => Term a where

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

Associated Types

type Generic a :: *

Generic is a sum of all the interesting sub-types, 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 Term.

Methods

numChildren :: a -> Int

Count the number of interesting children.

class (MonadPlus m, Term a) => Walker c m a where

Walker captures the ability to walk over a Term applying Rewrites, using a specific context c and a MonadPlus m.

Minimal complete definition: childL.

Default instances are provided for allT, allR and anyR, 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.

Methods

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

Construct a Lens pointing at the n-th interesting child of this node.

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

Apply a Generic Translate to all interesting children of this node, succeeding if they all succeed. The results are combined in a Monoid.

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

Apply a Generic Rewrite to all interesting children of this node, succeeding if they all succeed.

anyR :: Rewrite c m (Generic a) -> Rewrite c m a

Apply Generic Rewrite to all interesting children of this node, suceeding if any succeed.

Rewrite Traversals

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

Apply a Rewrite to a specific child.

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

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

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

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

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

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

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

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

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

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

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

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

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

Attempt to apply a Rewrite in a top-down manner, prunning at successful rewrites.

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

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 b

Apply a Translate to a specific child.

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

Fold a tree in a top-down manner, using a single Translate for each node.

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

Fold a tree in a bottom-up manner, using a single Translate for each node.

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

Attempt to apply a Translate in a top-down manner, prunning at successes.

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

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

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

Building Lenses

type Path = [Int]

A Path is a list of Ints, where each Int specifies which interesting child to descend to at each step.

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

Construct a Lens by following a Path.

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

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

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

Repeat as many iterations of the Path as possible.