ZipperEx - Another zipper implementation

Your Libraries & OS Mentoring Libraries
, ,
1

Another zipper implementation base on the paper Functional pearl: the zipper by Gérard Huet. Inspired by the erlang zipper and the great sourceror project.

ZipperEx provides functions to handle and traverse tree data structures.

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]}]}

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]
5 Likes