ZipperEx

An Elixir implementation for Zipper based on the paper Functional pearl: the zipper. by Gérard Huet.

ZipperEx provides functions to handle and traverse tree data structures.

Installation

The package can be installed by adding zipper_ex to your list of dependencies in mix.exs:

def deps do
  [
    {:zipper_ex, "~> 0.1"}
  ]
end

The documentation can be found on hexdocs.

Usage

To create a zipper you can use the ZipperEx.Zipable protocol or create a module.

Creating a zipper module

Imagine we have a tree structure based on a tuple with an integer value and a list of cildren. The leafs of the tree are also integers. A tree may then look like the following:

{1, [2, {3, [4, 5]}, 6, {7, [0]}]}
#   1
# +-+-+---+-+
# 2   3   6 7
#   +-+-+   +
#   4   5   0

To handle this tree we create the following module:

defmodule My.Zipper do
  use ZipperEx

  @impl ZipperEx
  def branch?(item) do
    case item do
      {_, [_ | _]} -> true
      _else -> false
    end
  end

  @impl ZipperEx
  def children({_, children}), do: children

  @impl ZipperEx
  def make_node({value, _children}, children), do: {value, children}

  def make_node(value, children), do: {value, children}
end

For use ZipperEx we have to implement the callbacks c:branch?/1, c:children/1 and c:make_node/2.

The My.Zipper module contains all functions the ZipperEx also provides.

We can now use My.Zipper.

iex> alias My.Zipper
iex> zipper = Zipper.new({1, [2, {3, [4, 5]}, 6, {7, [0]}]})
#ZipperEx<{1, [2, {3, [4, 5]}, 6, {7, [0]}]}>
iex> zipper = Zipper.down(zipper)
#ZipperEx<2>
iex> zipper = Zipper.right(zipper)
#ZipperEx<{3, [4, 5]}>
iex> zipper |> Zipper.remove() |> Zipper.root()
{1, [2, 6, {7, [0]}]}

Using the ZipperEx.Zipable protocol

Similar to the module example the protocol needs implementations for ZipperEx.Zipable.branch?/1, ZipperEx.Zipable.children/1 and ZipperEx.Zipable.make_node/2.

defmodule My.TreeNode do
  @moduledoc false

  defstruct value: nil, children: []

  def new({value, children}) do
    struct!(__MODULE__, value: value, children: Enum.map(children, &new/1))
  end

  def new(value), do: struct!(__MODULE__, value: value)

  defimpl ZipperEx.Zipable do
    def branch?(%{children: [_ | _]}), do: true

    def branch?(_node), do: false

    def children(%{children: children}), do: children

    def make_node(node, children), do: %{node | children: children}
  end

  defimpl Inspect do
    def inspect(node, _opts), do: "#TreeNode<#{node.value}, #{inspect(node.children)}>"
  end
end

My.TreeNode can then be used as follows:

iex> alias My.TreeNode
iex> tree = TreeNode.new({1, [2, {3, [4, 5]}]})
iex> zipper = ZipperEx.new(tree)
iex> ZipperEx.down(zipper)
#ZipperEx<#TreeNode<2, []>>
iex> zipper |> ZipperEx.down() |> ZipperEx.rightmost()
#ZipperEx<#TreeNode<3, [#TreeNode<4, []>, #TreeNode<5, []>]>>
iex> {_zipper, acc} = ZipperEx.traverse(zipper, [], fn z, acc ->
...>   node = ZipperEx.node(z)
...>   {z, [node.value | acc]}
...> end)
iex> acc
[5, 4, 3, 2, 1]