Zipper
Navigate a binary tree with a zipper: move the focus left, right and up, read and change the focused node, and get the whole tree back.
Adapted from Exercism’s problem specification (MIT). Listed under Collections & Algorithms.
// FILE: zipper.nomi
//# A zipper over a binary tree: a focus on one node that can move and edit
//# the tree around it.
/// A binary tree node: a value and a subtree on each side, either of which
/// may be missing.
pub struct Tree<T>
value: T
left: Maybe<Tree<T>>
right: Maybe<Tree<T>>
end
/// A tree seen from one of its nodes, the focus. The zipper holds the focus
/// subtree and the path back to the root, nearest parent first, so moving
/// the focus or changing it rebuilds only the nodes on that path.
pub opaque struct Zipper<T>
focus: Tree<T>
path: List<Crumb<T>>
end
/// One step up from a focus: the parent's value and the parent's other
/// subtree, on the side the focus was not.
enum Crumb<T>
FromLeft {value: T, right: Maybe<Tree<T>>}
FromRight {value: T, left: Maybe<Tree<T>>}
end
impl Zipper<T>
/// A zipper on `tree` with its root in focus.
pub fn from_tree(tree: Tree<T>) -> Zipper<T>
{focus: tree, path: []}
end
/// The whole tree, whatever the focus.
pub fn to_tree(zipper: Zipper<T>) -> Tree<T>
case Zipper.up(zipper)
Some(parent) -> Zipper.to_tree(parent)
None -> zipper.focus
end
end
/// The value of the focus node.
pub fn value(zipper: Zipper<T>) -> T
zipper.focus.value
end
/// The zipper on the focus's left subtree, or `None` when it has none.
pub fn left(zipper: Zipper<T>) -> Maybe<Zipper<T>>
{value:, left:, right:} = zipper.focus
Some(Zipper{focus: left?, path: [.FromLeft{value:, right:}, ..zipper.path]})
end
/// The zipper on the focus's right subtree, or `None` when it has none.
pub fn right(zipper: Zipper<T>) -> Maybe<Zipper<T>>
{value:, left:, right:} = zipper.focus
Some(Zipper{focus: right?, path: [.FromRight{value:, left:}, ..zipper.path]})
end
/// The zipper on the focus's parent, or `None` at the root.
pub fn up(zipper: Zipper<T>) -> Maybe<Zipper<T>>
case zipper.path
[] ->
None
[.FromLeft{value:, right:}, ..path] ->
Some(Zipper{focus: {value:, left: Some(zipper.focus), right:}, path:})
[.FromRight{value:, left:}, ..path] ->
Some(Zipper{focus: {value:, left:, right: Some(zipper.focus)}, path:})
end
end
/// `zipper` with the focus node's value replaced by `value`.
pub fn set_value(zipper: Zipper<T>, value: T) -> Zipper<T>
{..zipper, focus: {.., value:}}
end
/// `zipper` with the focus node's left subtree replaced by `left`.
pub fn set_left(zipper: Zipper<T>, left: Maybe<Tree<T>>) -> Zipper<T>
{..zipper, focus: {.., left:}}
end
/// `zipper` with the focus node's right subtree replaced by `right`.
pub fn set_right(zipper: Zipper<T>, right: Maybe<Tree<T>>) -> Zipper<T>
{..zipper, focus: {.., right:}}
end
end
// FILE: zipper_test.nomi
import zipper.{Tree, Zipper}
/// One canonical operation on a zipper.
enum Operation
Left
Right
Up
SetValue Int
SetLeft Maybe<Tree<Int>>
SetRight Maybe<Tree<Int>>
end
/// A node with no subtrees.
fn leaf(value: Int) -> Tree<Int>
{value:, left: None, right: None}
end
/// The tree every canonical case starts from.
fn initial_tree() -> Tree<Int>
{value: 1, left: Some({value: 2, left: None, right: Some(leaf(3))}), right: Some(leaf(4))}
end
/// The zipper on the initial tree after each operation in turn, or `None`
/// once a move finds no node.
fn follow(operations: List<Operation>) -> Maybe<Zipper<Int>>
start = initial_tree() |> Zipper.from_tree() |> Some()
Iter.reduce(operations, start, fn zipper, operation -> apply(zipper?, operation))
end
fn apply(zipper: Zipper<Int>, operation: Operation) -> Maybe<Zipper<Int>>
case operation
.Left -> Zipper.left(zipper)
.Right -> Zipper.right(zipper)
.Up -> Zipper.up(zipper)
.SetValue(value) -> Some(Zipper.set_value(zipper, value))
.SetLeft(left) -> Some(Zipper.set_left(zipper, left))
.SetRight(right) -> Some(Zipper.set_right(zipper, right))
end
end
test "the tree after the operations"
cases: List<(String, List<Operation>, Tree<Int>)> = [
("data is retained", [], initial_tree()),
("tree from deep focus", [.Left, .Right], initial_tree()),
(
"set_value",
[.Left, .SetValue(5)],
{
value: 1,
left: Some({value: 5, left: None, right: Some(leaf(3))}),
right: Some(leaf(4)),
},
),
(
"set_value after traversing up",
[.Left, .Right, .Up, .SetValue(5)],
{
value: 1,
left: Some({value: 5, left: None, right: Some(leaf(3))}),
right: Some(leaf(4)),
},
),
(
"set_left with leaf",
[.Left, .SetLeft(Some(leaf(5)))],
{
value: 1,
left: Some({value: 2, left: Some(leaf(5)), right: Some(leaf(3))}),
right: Some(leaf(4)),
},
),
(
"set_right with null",
[.Left, .SetRight(None)],
{value: 1, left: Some(leaf(2)), right: Some(leaf(4))},
),
(
"set_right with subtree",
[.SetRight(Some({value: 6, left: Some(leaf(7)), right: Some(leaf(8))}))],
{
value: 1,
left: Some({value: 2, left: None, right: Some(leaf(3))}),
right: Some({value: 6, left: Some(leaf(7)), right: Some(leaf(8))}),
},
),
(
"set_value on deep focus",
[.Left, .Right, .SetValue(5)],
{
value: 1,
left: Some({value: 2, left: None, right: Some(leaf(5))}),
right: Some(leaf(4)),
},
),
]
subtests cases, (description, operations, expected), description
assert follow(operations) |> Maybe.map(Zipper.to_tree) == Some(expected)
end
end
test "the value at the focus"
[
("left, right and value", [Operation.Left, .Right], 3),
("left, right, and up", [.Left, .Up, .Right, .Up, .Left, .Right], 3),
("test ability to descend multiple levels and return", [.Left, .Right, .Up, .Up], 1),
]
|> subtests (description, operations, expected), description
assert follow(operations) |> Maybe.map(Zipper.value) == Some(expected)
end
end
test "no node to move to"
[
("dead end", [Operation.Left, .Left]),
("traversing up from top", [.Up]),
]
|> subtests (description, operations), description
assert follow(operations) == None
end
end
test "different paths to same zipper"
assert follow([.Left, .Up, .Right]) == follow([.Right])
endok the tree after the operations (8 cases)
ok the value at the focus (3 cases)
ok no node to move to (2 cases)
ok different paths to same zipper
test result: ok. 14 passed, 0 failed
How it’s written
Section titled “How it’s written”Tree<T>is a struct of a value and twoMaybe<Tree<T>>subtrees, so the canonical data’snullsubtree isNoneand every tree has a root node to focus on.Zipper.from_treetherefore cannot fail.- Nomi values cannot change, so the zipper is the persistent structure zippers were invented for: an opaque struct of the focus subtree and the path back to the root, nearest parent first. Each step of the path is a private
Crumb,FromLeftorFromRight, holding the parent’s value and its other subtree. A move or a change answers a new zipper and rebuilds only the nodes on the path;to_treewalksupuntil there is no parent. left,rightandupanswerMaybe<Zipper<T>>, withNonewhere there is no node to move to, which is the canonical “dead end” and “traversing up from top”.leftandrightread the subtree with?inside the new zipper’s literal (focus: left?).set_value,set_leftandset_rightcannot fail and answer aZipper<T>, each one spread update of the focus ({..zipper, focus: {.., value:}}).- The “different paths to same zipper” case is one
==between two zippers.==compares the zipper, its path of crumbs and its trees structurally, so none of the three types derivesEquatable. - The canonical cases are a starting tree and a list of operations, all on the same tree. The test file writes each operation as an
Operationvariant andfollowapplies them with oneIter.reduceover aMaybe<Zipper<Int>>, asapply(zipper?, operation): the?exits the lambda, so the first move that finds no node leavesNonefor the rest of the fold. The cases are threesubteststables by what they expect (a tree, a value, no zipper) and one test for the two paths.leafandinitial_treekeep the expected trees short. - The canonical data’s
left,rightandvalueoperations at the end of a case are what the table asserts: a case ending invalueis a row of the value table, andto_treeis applied by the tree table.