tur/zip

(defstruct ZipOps [])

how to navigate a tree type T: the three functions of clojure.zip.

branch? says whether a node can have children, children lists them in order, and make-node rebuilds a node with a new list of children. Build one with zip/ops. :heap :copy, so a location carries it as one word.

Since: generic-zipper-plan ZP1

(defstruct ZipFrame [])

one level of a location's path (internal).

lefts holds the left siblings NEAREST FIRST, pnode the parent as it was on the way down, up the next frame out (the NULL link at the root), rights the right siblings in order, and changed whether anything below this frame was edited -- zip/up rebuilds the parent only then.

Since: generic-zipper-plan ZP1

(defstruct ZipLoc [])

a location in a tree of T: the focused node plus the path to it.

end is Clojure's :end marker, set by zip/next past the last node.

Since: generic-zipper-plan ZP1

(zip/-top? [T])

internal: is this path link the root's (the NULL link)?

(zip/-no-frame [T])

internal: the root's path link.

(zip/-rev-onto [T])

internal: xs reversed, in front of acc.

(zip/-append1 [T])

internal: xs with x added at the end.

(zip/-loc [T])

internal: a location that is not the end marker.

(zip/-frame [T])

internal: a path frame.

(zip/-mark [T])

internal: the frame with changed set; the root link as is.

(zip/-depth-acc [T])

internal: tail-recursive frame count behind zip/depth.

(zip/-ancestors-acc [T])

internal: the parents of every frame from f out, root first.

(zip/ops [T])

bundle the three functions that describe a tree type T.

(defdata Tree :heap :copy (Leaf int) (Node (Cons Tree)))
(def tree-ops
  (zip/ops (fn [t : Tree] : bool (match t (Leaf _) false (Node _) true))
           (fn [t : Tree] : (Cons Tree) (match t (Leaf _) (tnil) (Node cs) cs))
           (fn [t : Tree cs : (Cons Tree)] : Tree (Node cs))))

Since: generic-zipper-plan ZP1

(zip/zipper [T])

open a zipper at the root of a tree.

(zip/node (zip/zipper tree-ops t))  ; => t

Since: generic-zipper-plan ZP1

(zip/node [T])

the node at a location.

(zip/node (zip/zipper tree-ops t))  ; => t

Since: generic-zipper-plan ZP1

(zip/branch? [T])

can the node at a location have children?

(zip/branch? (zip/zipper tree-ops (Leaf 1)))  ; => false

Since: generic-zipper-plan ZP1

(zip/children [T])

the children of the node at a location, in order.

Panics with "called children on a leaf node" when zip/branch? is false, as Clojure throws: a leaf and an empty branch are different things.

(tlength (zip/children (zip/zipper tree-ops t)))  ; => number of children

Since: generic-zipper-plan ZP1

(zip/make-node [T])

build a node with the location's ops.

(zip/make-node z (zip/node z) (tnil))  ; => the focused node, childless

Since: generic-zipper-plan ZP1

(zip/ancestors [T])

the nodes on the path from the root to a location's parent.

Clojure's path. Each is the node as it was on the way down, so an edit below it is not reflected until zip/up rebuilds it.

(tlength (zip/ancestors (zip/zipper tree-ops t)))  ; => 0

Since: generic-zipper-plan ZP1

(zip/lefts [T])

the left siblings of a location, in document order.

(zip/lefts (zip/zipper tree-ops t))  ; => (tnil)

Since: generic-zipper-plan ZP1

(zip/rights [T])

the right siblings of a location, in document order.

(zip/rights (zip/zipper tree-ops t))  ; => (tnil)

Since: generic-zipper-plan ZP1

(zip/depth [T])

how many levels a location is below the root.

(zip/depth (zip/zipper tree-ops t))  ; => 0

Since: generic-zipper-plan ZP1

(zip/end? [T])

has zip/next walked past the last node?

(zip/end? (zip/zipper tree-ops t))  ; => false

Since: generic-zipper-plan ZP1

(zip/down [T])

move to the leftmost child.

(zip/down (zip/zipper tree-ops (Node (tcons-of (Leaf 1) (tnil)))))
; => (Some loc), with (Leaf 1) in focus

Since: generic-zipper-plan ZP1

(zip/up [T])

move to the parent, rebuilding it if anything below was edited.

An unedited parent is returned as it was, with no allocation, so a walk that edits nothing shares every node with the original tree.

(zip/up (zip/zipper tree-ops t))  ; => None

Since: generic-zipper-plan ZP1

(zip/right [T])

move to the next sibling.

(zip/right (zip/zipper tree-ops t))  ; => None

Since: generic-zipper-plan ZP1

(zip/left [T])

move to the previous sibling.

(zip/left (zip/zipper tree-ops t))  ; => None

Since: generic-zipper-plan ZP1

(zip/leftmost [T])

move to the first sibling.

(zip/node (zip/leftmost z))  ; => the first child of z's parent

Since: generic-zipper-plan ZP1

(zip/rightmost [T])

move to the last sibling.

(zip/node (zip/rightmost z))  ; => the last child of z's parent

Since: generic-zipper-plan ZP1

(zip/root [T])

zip all the way up and return the (possibly edited) tree.

(zip/root (zip/replace (zip/zipper tree-ops t) (Leaf 9)))  ; => (Leaf 9)

Since: generic-zipper-plan ZP1

(zip/-deepest-last [T])

internal: the last node in pre-order under z (z if a leaf).

(zip/-next-up [T])

internal: next from a node with no child and no right sibling.

(zip/next [T])

move to the next node in a depth-first, pre-order walk.

Past the last node it returns the END marker: a location at the (rebuilt) root for which zip/end? is true. zip/next of the end marker is the end marker; zip/root of it is the tree.

(defn visit-all [T] [z : (ZipLoc T)] : T
  (if (zip/end? z) (zip/root z) (visit-all (zip/next z))))

Since: generic-zipper-plan ZP1

(zip/prev [T])

move to the previous node in a depth-first, pre-order walk.

(zip/prev (zip/zipper tree-ops t))  ; => None

Since: generic-zipper-plan ZP1

(zip/replace [T])

replace the node at a location.

(zip/node (zip/replace z (Leaf 40)))  ; => (Leaf 40)

Since: generic-zipper-plan ZP1

(zip/edit [T])

replace the node at a location with a function of it.

(zip/edit z (fn [t : Tree] : Tree (Leaf 0)))

Since: generic-zipper-plan ZP1

(zip/insert-left [T])

insert a sibling immediately to the left, without moving.

Panics with "Insert at top" at the root, as Clojure throws.

(zip/lefts (zip/insert-left z (Leaf 0)))  ; => ... ending in (Leaf 0)

Since: generic-zipper-plan ZP1

(zip/insert-right [T])

insert a sibling immediately to the right, without moving.

Panics with "Insert at top" at the root, as Clojure throws.

(thead (zip/rights (zip/insert-right z (Leaf 0))))  ; => (Leaf 0)

Since: generic-zipper-plan ZP1

(zip/insert-child [T])

add a first child to the node at a location, without moving.

Panics with "called children on a leaf node" when the node is not a branch.

(thead (zip/children (zip/insert-child z (Leaf 0))))  ; => (Leaf 0)

Since: generic-zipper-plan ZP1

(zip/append-child [T])

add a last child to the node at a location, without moving.

Panics with "called children on a leaf node" when the node is not a branch.

(zip/node (zip/rightmost (unwrap (zip/down (zip/append-child z (Leaf 0))))))
; => (Leaf 0)

Since: generic-zipper-plan ZP1

(zip/remove [T])

delete the node at a location.

Panics with "Remove at top" at the root, as Clojure throws.

(zip/root (zip/remove z))  ; => the tree without z's node

Since: generic-zipper-plan ZP1

(zip/find-next [T])

search forward in pre-order for a node satisfying p.

The search starts AT z: z itself is returned when its node satisfies p. To find the following match, search from (zip/next found).

(zip/find-next (zip/zipper tree-ops t)
               (fn [n : Tree] : bool (match n (Leaf v) (= v 3) (Node _) false)))
; => (Some loc) at (Leaf 3)

Since: generic-zipper-plan ZP2

(zip/edit-all [T])

apply f to every node from z on, in pre-order, and return the root.

Clojure's standard edit loop, shipped: edit the node, move with zip/next, stop at the end. Each node is edited BEFORE its children are visited, so the walk descends into what f returned -- the zipper form of Uniplate's transform, top-down. From the root it rewrites the whole tree.

(zip/edit-all (zip/zipper tree-ops t)
              (fn [n : Tree] : Tree (match n (Leaf v) (Leaf (* v 2)) (Node _) n)))
; => t with every leaf doubled

Since: generic-zipper-plan ZP2

(defstruct Rose :heap [A] (label A) (kids (Cons (Rose A))))

a rose tree: a label and a list of child trees (Haskell's Data.Tree).

The typed counterpart of Clojure's seq-zip. Every node is a branch -- a leaf is a node with no children -- so zip/down of a leaf is None and zip/append-child works anywhere. kids is a Cons, so zip/down is O(1). Build one with zip/rose or make-struct.

Since: generic-zipper-plan ZP2

(zip/rose [A])

build a rose tree node.

(zip/rose 1 (tcons-of (zip/rose 2 (tnil)) (tnil)))  ; => 1 with one child, 2

Since: generic-zipper-plan ZP2

(zip/rose-ops [A])

the ZipOps of a rose tree.

(zip/zipper (zip/rose-ops) r)  ; same as (zip/rose-zip r)

Since: generic-zipper-plan ZP2

(zip/rose-zip [A])

open a zipper at the root of a rose tree.

(.label (zip/node (zip/rose-zip (zip/rose 7 (tnil)))))  ; => 7

Since: generic-zipper-plan ZP2

(defclass Plated [a])

a type whose values have children of the same type.

lens's Plated / Uniplate's Uniplate: the three ZipOps functions as an instance, so zip/plated can open a zipper with no ops argument. An instance gives one canonical view of a type; for a second view of the same type, build a ZipOps with zip/ops instead.

(definstance Plated [Tree]
  (plate-branch? [t] (match t (Leaf _) false (Node _) true))
  (plate-children [t] (match t (Leaf _) (tnil) (Node cs) cs))
  (plate-rebuild [t cs] (Node cs)))

Since: generic-zipper-plan ZP3

(definstance Plated [Rose])

a rose tree's children are its kids; every node is a branch.

(zip/plated-ops [^Plated T])

the ZipOps a Plated instance describes.

(:: (zip/plated-ops) (ZipOps Tree))

Since: generic-zipper-plan ZP3

(zip/plated [^Plated T])

open a zipper on a value of a Plated type.

(zip/node (zip/plated t))  ; => t

Since: generic-zipper-plan ZP3

(defstruct Traversal [])

how to visit the A-elements of a container S, and put them back.

parts lists the elements of an S in order; fill returns the same S with its elements replaced, in order. The record mirrors stdlib/lens.tur's Lens. Laws:

(fill s (parts s)) = s
(parts (fill s xs)) = xs, when xs has as many elements as (parts s)

:heap :copy, so a cursor carries it as one word.

Since: generic-zipper-plan ZP4

(defstruct ZipCursor [])

a cursor over the elements of a container, focused on one.

shape is the container as opened, lefts the elements before the focus (nearest first), rights those after it (in order).

Since: generic-zipper-plan ZP4

(zip/traversal [S A])

build a Traversal from its two functions.

(zip/traversal (fn [p : Pair] : (Cons int) ...)
               (fn [p : Pair xs : (Cons int)] : Pair ...))

Since: generic-zipper-plan ZP4

(zip/cursor [S A])

open a cursor on the first element of a container.

Opening reads every element once (O(n)); after that each move and edit is O(1), and every cursor stays valid.

(zip/cursor (zip/cons-traversal) (tcons-of 1 (tnil)))  ; => (Some c), focus 1

Since: generic-zipper-plan ZP4

(zip/cursor-focus [S A])

the element a cursor is on.

(zip/cursor-focus c)  ; => the current element

Since: generic-zipper-plan ZP4

(zip/cursor-set [S A])

replace the element a cursor is on.

(zip/cursor-focus (zip/cursor-set c 200))  ; => 200

Since: generic-zipper-plan ZP4

(zip/cursor-edit [S A])

replace the element a cursor is on with a function of it.

(zip/cursor-edit c (fn [x : int] : int (* x 2)))

Since: generic-zipper-plan ZP4

(zip/cursor-next [S A])

move to the next element.

(zip/cursor-next c)  ; => (Some c2), or None at the last element

Since: generic-zipper-plan ZP4

(zip/cursor-prev [S A])

move to the previous element.

(zip/cursor-prev c)  ; => (Some c0), or None at the first element

Since: generic-zipper-plan ZP4

(zip/cursor-close [S A])

write the elements back into the container.

(zip/cursor-close (zip/cursor-set c 200))  ; => s with that element 200

Since: generic-zipper-plan ZP4

(zip/cons-traversal [A])

the Traversal of a list: its elements are itself.

A cursor over it is a persistent list zipper with O(1) moves.

(zip/cursor (zip/cons-traversal) xs)  ; => a cursor over xs

Since: generic-zipper-plan ZP4

(zip/-forest-labels [A])

internal: a forest's labels in pre-order, in front of acc.

(defstruct ZipFill :heap [A] (built (Cons (Rose A))) (rest (Cons A)))

internal: a rebuilt forest and the labels it did not use.

(zip/-fill-forest [A])

internal: relabel a forest in pre-order from xs.

A tree keeps its old label once xs runs out, so fill is total.

(zip/rose-labels [A])

the Traversal of a rose tree's labels, in pre-order.

(zip/cursor (zip/rose-labels) r)  ; => a cursor over r's labels

Since: generic-zipper-plan ZP4