Control.Layer

The children-and-rebuild interface a generic traversal runs on, and the collecting queries that ride it.

A Layer(a) is one node sort’s one-layer view: kids lists a node’s immediate same-sort children in a fixed order, and rebuild puts a new child list back in that same order. Everything generic (Control.Rewrite’s strategies, the queries here) is written against the pair, so a sort joins the library by supplying two functions and nothing else.

Both halves are pure structure, never effectful: the effects of a traversal belong to the rewrite being applied, so a layer stays a plain record and the row polymorphism lives one layer up.

Traversal order is fixed and documented everywhere it matters. Every walk here is root first, then children in kids order, and nothing consults a hash map, so the node sequence a query sees is a pure function of the tree.

Every query here terminates on a finite tree: each is structurally recursive through kids, and none of them looks at anything rebuild produced. That puts the one termination obligation on the layer itself, where it is checkable by reading two functions: kids must return strict subterms of its argument and must not manufacture nodes. The fueled combinators in Control.Rewrite exist for the loops that this discipline cannot rule out, the ones a rewrite rule creates by feeding its own output back in.

Types

Layer

type Layer(a) = Layer { kids: (a) -> List(a), rebuild: (a, List(a)) -> a }

One node sort’s one-layer view: its immediate children and the inverse that replaces them. rebuild(x, kids(x)) must return a node equal to x, and rebuild must fail closed (return x unchanged) when the replacement list does not match the node’s shape.

Functions and Values

plate_layer

plate_layer : forall a. () -> Control.Layer.Layer(a)

The layer a Plate instance supplies, so a sort that derived Plate joins every traversal here and in Control.Rewrite without a hand-written pair.

The two interfaces agree on the shape and disagree only on how they report a violation of it, and that disagreement is the whole of the translation: rebuild raises Fail on a replacement list that does not match the node, and a layer says the same thing by returning the node unchanged. Nothing else is adapted, because children is already the order kids promises.

lay_kids

lay_kids : forall a. (Control.Layer.Layer(a), a) -> List(a)

The immediate children of x, in the layer’s fixed order.

lay_rebuild

lay_rebuild : forall a. (Control.Layer.Layer(a), a, List(a)) -> a

x with its immediate children replaced by cs, in the layer’s order.

lay_descend

lay_descend : forall e0 a. (Control.Layer.Layer(a), (a) -> a ! {e0}, a) -> a ! {e0}

Apply f to each immediate child of x and rebuild. The one-layer map: it never recurses, so a traversal scheme built on it controls its own depth.

lay_universe

lay_universe : forall a. (Control.Layer.Layer(a), a) -> List(a)

Every node of the tree, root first, depth first in kids order.

lay_size

lay_size : forall a. (Control.Layer.Layer(a), a) -> Int

The number of nodes in the tree.

lay_size(countdown, 3)

4

lay_depth

lay_depth : forall a. (Control.Layer.Layer(a), a) -> Int

The height of the tree: 1 at a leaf.

lay_depth(countdown, 3)

4

lay_collect

lay_collect : forall e0 a. (Control.Layer.Layer(a), (a) -> Bool ! {e0}, a) -> List(a) ! {e0}

Every node satisfying q, root first, depth first. The gather half of an analysis pass: one predicate replaces a hand-written collecting recursion.

lay_collect(countdown, even, 3)

[2, 0]

lay_count_where

lay_count_where : forall e0 a. (Control.Layer.Layer(a), (a) -> Bool ! {e0}, a) -> Int ! {e0}

How many nodes satisfy q.

lay_any

lay_any : forall e0 a. (Control.Layer.Layer(a), (a) -> Bool ! {e0}, a) -> Bool ! {e0}

Whether any node satisfies q. Short-circuits: the first accepting node ends the walk, so a hit near the root costs nothing.

lay_summarize

lay_summarize : forall e0 a b. (Control.Layer.Layer(a), (a) -> b ! {e0}, (b, b) -> b ! {e0}, b, a) -> b ! {e0}

Fold a per-node summary over the whole tree: measure scores one node and combine merges two summaries, starting from unit. The caller supplies the combining operation, so one walk serves counting, maximizing, and collecting alike.

lay_index_where

lay_index_where : forall e0 a. (Control.Layer.Layer(a), (a) -> Bool ! {e0}, a) -> List(Int) ! {e0}

The preorder index of every node satisfying q. An index is a deterministic address into the tree: 0 is the root, and the numbering is fixed because kids is.

lay_at_index

lay_at_index : forall a. (Control.Layer.Layer(a), Int, a) -> Option(a)

The node at a preorder index, or None when the index is past the end.

lay_path_to

lay_path_to : forall a. (Control.Layer.Layer(a), Int, a) -> Option(List(Int))

The preorder index path from the root to the node at index i: the index of each ancestor, root first, ending at i itself. None when the index is past the end. The path is what a pass reports when it must point at a node without carrying the node.

lay_path_to(countdown, 3, 3)

Some([0, 1, 2, 3])

lay_indexed

lay_indexed : forall a. (Control.Layer.Layer(a), a) -> List((Int, a))

Every node’s preorder index paired with the node, root first. The indexed walk an occurrence table is built from.

lay_edges

lay_edges : forall a. (Control.Layer.Layer(a), a) -> List((a, a))

The immediate children of every node, flattened: the one-layer relation of the whole tree as parent-child pairs in preorder. A dependency or occurrence graph is one map off this.