Xipper

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

Zippers provide an elegant solution for traversing a tree-like data structure, while maintaining enough state data to reconstruct the entire tree from any of its child nodes.

All that is required to create a zipper for a data structure is the data structure itself and a set of functions that define behaviours around nodes of the data structure. See below and the documentation for Xipper.new/4 for details.

Basic Usage and API Reference

For more complete documentation and examples, see the documentation for Xipper either inline in the file here, or on hexdocs.pm.

Creating a zipper

• Xipper.new/4 creates a new zipper and is probably the most involved function in the API. It takes as its arguments a root data structure for the zipper and three functions that define behaviours around nodes of that data structure.

For a nested list data structure

zipper = Xipper.new(
  # root data structure
  [1, 2, [3, [4, 5], 6], [], 7],

  # function for determining whether a node is a branch
  &is_list/1,

  # function for returning a branch node's children
  fn branch_node -> branch_node end,

  # function for creating a new node from an existing node and a list of children
  fn _node, children -> children end
)

For a map data structure

zipper = Xipper.new(
  %{name: "a", children: [%{name: "b"}, %{name: "c"}]},

  fn branch -> is_map(branch) && Map.has_key?(branch, :children) end,

  fn branch -> Map.get(branch, :children) end,

  fn
    node = %{children: _}, children -> %{node | children: children}
    node, children -> Map.put(node, :children, children)
  end
)

Querying a zipper

• Xipper.focus/1 returns the current focus of the zipper
• Xipper.children/1 returns the children of the current focus
• Xipper.is_branch/1 returns true if the current focus is a branch node (i.e. it has or can have children)
• Xipper.is_end/1 returns true if a depth-first walk through the zipper (see next/1 and prev/1) has been completed
• Xipper.lefts/1 returns the left-hand siblings of the current focus
• Xipper.rights/1 returns the right-hand siblings of the current focus
• Xipper.path/1 returns a list consisting of the parent, grandparent, etc. nodes of the current focus

Navigating a zipper

• Xipper.down/1 shifts focus to the leftmost child of the current focus
• Xipper.up/1 shifts focus to the parent of the current focus
• Xipper.left/1 shifts focus to the immediate left-hand sibling of the current focus
• Xipper.right/1 shifts focus to the immediate right-hand sibling of the current focus
• Xipper.leftmost/1 shifts to the leftmost sibling of the current focus
• Xipper.rightmost/1 shifts to the rightmost sibling of the current focus
• Xipper.next/1 shifts focus to the next node in a depth-first walk of the zipper
• Xipper.prev/1 shifts focus to the previous node in a depth-first walk of the zipper
• Xipper.root/1 shifts focus to the topmost root of the zipper

Modifying a zipper

• Xipper.edit/2 replaces the current node with the result of calling a given function on the current node
• Xipper.replace/2 replaces the current node with the passed replacement value
• Xipper.remove/1 removes the current focus, and shifts focus to the previous (via depth-first walk) node
• Xipper.insert_child/2 inserts the given child node as the first child of the current node without shifting focus
• Xipper.append_child/2 appends the given child node as the last child of the current node without shifting focus
• Xipper.insert_left/2 inserts the given node immediately to the left of the current node without shifting focus
• Xipper.insert_right/2 inserts the given node immediately to the right of the current node without shifting focus
• Xipper.make_node/3 takes a zipper, a node, and a set of children and returns a new node based on the user defined function passed into the zipper constructor. (NB this does not modify the zipper, but returns a value that could be used to modify it)

Installation

If available in Hex, the package can be installed by adding xipper to your list of dependencies in mix.exs:

def deps do
  [
    {:xipper, "~> 0.1.0"}
  ]
end

Documentation can be generated with ExDoc and published on HexDocs. Once published, the docs can be found at https://hexdocs.pm/xipper.