ExZipper

An Elixir implementation of Huet's Zipper, with gratitude to Rich Hickey's Clojure implementation.

Installation

@deps [
  ex_zipper: "~> 0.1.3"
]

Usage

Below is an outline of the API provided by ExZipper.Zipper. See the full documentation here for usage examples

Creating zippers

ExZipper provides one zipper construction function for working with plain lists, ExZipper.Zipper.list_zipper/1

iex> Zipper.list_zipper([1,[],2,[3,[4,5]]])

For more complex cases, ExZipper.Zipper.zipper/4 provides a mechanism to define your own zipper, passing for its first three arguments functions to

determine whether a node is a branch
return the children of a branch node
create a new node from an existing node and a new set of children

and your root data structure as its fourth argument.

For example, to create a zipper for a data structure of nested maps, where a branch's children are defined under the :kids key:

  iex> Zipper.zipper(
  ...>   fn node -> is_map(node) and Map.has_key?(node, :kids) end,
  ...>   fn %{kids: kids} -> kids end,
  ...>   fn node, new_kids -> %{node | kids: new_kids} end,
  ...>   %{ value: "top", kids: [%{value: "first inner"}, %{value: "last inner}]}
  ...> )

Navigating zippers

The following functions move through a zipper and return either a new zipper, or an error of the form {:error, :atom_describing_the_error}

Zipper.down moves to the first (leftmost) child of the current node
Zipper.up moves to the parent of the current node
Zipper.right moves to the next sibling on the right of the current node
Zipper.left moves to the next sibling on the left of the current node
Zipper.rightmost moves to the furthest right sibling of the current node, or remains in place if already focused on the rightmost sibling
Zipper.leftmost moves to the furthest left sibling of the current node, or remains in place if already focused on the leftmost sibling
Zipper.root traverses the zipper all the way back to the root node, or remains in place if already focused on the root

The following functions move through a zipper via a depth-first walk. That is, moving as deep down one branch of the tree before moving laterally.

Zipper.next moves to the next node, preferring to move to a child over a sibling
Zipper.prev moves back up through a depth-first ordering of the tree
Zipper.end? returns true if the zipper has reached the end of a depth-first walk. At this point, the walk has been exhausted, and cannot be reversed.

Editing zippers

The following functions modify the zipper without shifting focus away from the current node. They will return a zipper, or an error, if called with an invalid zipper as input (for example, trying to insert a child into a leaf node)

Zipper.insert_child inserts a new child as the first (leftmost) child of the current node, without moving focus from the current node
Zipper.append_child inserts a new child as the last (rightmost) child of the current node, without moving focus from the current node
Zipper.insert_left inserts a new node as the sibling immediately to the left of the current node, without moving focus from the current node
Zipper.insert_right inserts a new node as the sibling immediately to the right of the current node, without moving focus from the current node
Zipper.replace/2 replaces the zipper's current node with the new node passed to this function as the second argument
Zipper.edit/2 replaces the zipper's current node with the result of calling the function passed as a second argument on the current node
Zipper.remove/1 removes the current node from the zipper, returning a zipper focused on the previous node (via a depth-first walk)

Helper functions

Zipper.node/1 returns the zipper's current node
Zipper.lefts/1 returns a list of the current node's left siblings
Zipper.rights/1 returns a list of the current node's right siblings
Zipper.path/1 returns a list of nodes creating a path from the root down to, but excluding, the current node
Zipper.to_list/1 returns a depth-first walk ordered list of a zipper's elements
Zipper.branch? returns true if the current node is a branch (that is, if it can have children, even if it currently does not have any)
Zipper.children returns a list of the current node's children, or an error if called on a leaf
Zipper.make_node takes a zipper, a node, and a list of children and returns a new node constructed from the second and third arguments. The first argument, the zipper, is passed only to provide context on how to construct the new node.

License

This library is released under the UNLICENSE.

aus70/ex_zipper