ex_zipper v0.1.3 ExZipper.Zipper View Source

An Elixir implementation of Huet’s Zipper1, with gratitude to Rich Hickey’s Clojure implementation2.

Zippers provide a method of navigating and editing a tree while maintaining enough state data to reconstruct the tree from the currently focused node.

For the most part, functions defined on ExZipper.Zipper return either an ExZipper.Zipper struct or an error tuple of the form {:error, :error_type}, if the function tries to move to a point on the tree that doesn’t exist. This allows easy chaining of functions with a quick failure mode if any function in the chain returns an error.

Link to this section Summary

Types

error()

maybe_zipper()

t()

Functions

append_child(zipper, new_child)

Appends a child as the rightmost child of the current focus. Returns an error if called on a leaf

branch?(zipper)

Returns true if the current focus of the zipper is a branch, even if it has no children, false otherwise

children(zipper)

Returns the children of the current focus, or an error if called on a leaf

down(zipper)

Moves to the leftmost child of the current focus, or returns an error if the current focus is a leaf or an empty branch

edit(zipper, func)

Replaces the current focus with the result of applying the given function to the current focus

end?(zipper)

Returns true if a depth-first walkthrough of the zipper has been exhausted

insert_child(zipper, new_child)

Inserts a child as the leftmost child of the current focus. Returns an error if called on a leaf

insert_left(zipper, node)

Inserts a new node as a new sibling to the immediate left of the current focus. Does not change focus. Returns an error if called on the root

insert_right(zipper, node)

Inserts a new node as a new sibling to the immediate right of the current focus. Does not change focus. Returns an error if called on the root

left(zipper)

Moves to the next sibling to the left of the current focus. Returns an error if at the root or already at the leftmost sibling at its depth in the tree

leftmost(zipper)

Moves to the leftmost sibling at the same depth as the current focus. Remains in place if already focused on the leftmost sibling. Returns an error if called on the root

lefts(zipper)

Returns all left siblings of the current focus. Returns an error if called on the root

list_zipper(list)

Returns a new zipper built from the given list

make_node(zipper, node, children)

Returns a new node created from node and children. The zipper first argument is to provide the context from which to determine how to create a new node

next(zipper)

Moves to the next focus in a depth-first walk through the zipper. If it reaches the end, subsequent calls to next return the same focus

node(zipper)

Returns the current focus of the zipper

path(zipper)

Returns a path of nodes leading from the root to, but excluding, the current focus. Returns an empty list at the root

prev(zipper)

Moves to the previous focus in a depth-first walk through the zipper. Returns an error if called on the end of the walk. Returns the root if called on the root

remove(zipper)

Removes the current focus from the zipper, moving focus to the node previous to the current focus in a depth-first walk. Will return an error if called on the root

replace(zipper, new_focus)

Replaces the current focus with the node passed as the second argument

right(zipper)

Moves to the next sibling to the right of the current focus. Returns an error if at the root or already at the rightmost sibling at its depth in the tree

rightmost(zipper)

Moves to the leftmost sibling at the same depth as the current focus. Remains in place if already focused on the leftmost sibling. Returns an error if called on the root

rights(zipper)

Returns all left right of the current focus. Returns an error if called on the root

root(zipper)

Returns to the root of the zipper. Remains in place if already on the root

to_list(zipper)

Returns a flat list of all the elements in the zipper, ordered via a depth-first walk, including the root

up(zipper)

Moves up to the parent of the current focus, or returns an error if already at the root of the zipper

zipper(is_branch, children, make_node, root)

Returns a new zipper with root as the root tree of the zipper, and is_branch, children and make_node as the internal functions that define construction parameters for the tree

Link to this section Types

error()

error() :: {:error, atom()}

maybe_zipper()

maybe_zipper() :: Zipper.t() | Zipper.error()

t()

t() :: %ExZipper.Zipper{crumbs: nil | map(), focus: any(), functions: map()}

Link to this section Functions

append_child(zipper, new_child)

append_child(Zipper.t(), any()) :: Zipper.maybe_zipper()

Appends a child as the rightmost child of the current focus. Returns an error if called on a leaf.

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> zipper |> Zipper.append_child(6) |> Zipper.node
[1,[],[2,3,[4,5]],6]
iex> zipper |> Zipper.down |> Zipper.append_child(6)
{:error, :append_child_of_leaf}

branch?(zipper)

branch?(Zipper.t()) :: boolean()

Returns true if the current focus of the zipper is a branch, even if it has no children, false otherwise.

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> Zipper.branch?(zipper)
true
iex> zipper |> Zipper.down |> Zipper.branch?
false
iex> zipper |> Zipper.down |> Zipper.right |> Zipper.branch?
true

children(zipper)

children(Zipper.t()) :: [any()] | Zipper.error()

Returns the children of the current focus, or an error if called on a leaf.

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> Zipper.children(zipper)
[1,[],[2,3,[4,5]]]
iex> zipper |> Zipper.down |> Zipper.children
{:error, :children_of_leaf}
iex> zipper |> Zipper.down |> Zipper.right |> Zipper.children
[]

down(zipper)

down(Zipper.t()) :: Zipper.maybe_zipper()

Moves to the leftmost child of the current focus, or returns an error if the current focus is a leaf or an empty branch.

Example

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> zipper |> Zipper.down |> Zipper.node
1
iex> zipper |> Zipper.down |> Zipper.down
{:error, :down_from_leaf}
iex> zipper |> Zipper.down |> Zipper.right |> Zipper.down
{:error, :down_from_empty_branch}

edit(zipper, func)

edit(Zipper.t(), (any() -> any())) :: Zipper.t()

Replaces the current focus with the result of applying the given function to the current focus

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> zipper = Zipper.down(zipper)
iex> Zipper.node(zipper)
1
iex> zipper = Zipper.edit(zipper, &(&1 * 10))
iex> Zipper.node(zipper)
10

end?(zipper)

end?(Zipper.t()) :: boolean()

Returns true if a depth-first walkthrough of the zipper has been exhausted.

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> zipper = zipper |> Zipper.next |> Zipper.next |> Zipper.next
iex> Zipper.node(zipper)
[2,3,[4,5]]
iex> Zipper.end?(zipper)
false
iex> zipper = zipper |> Zipper.next |> Zipper.next |> Zipper.next |> Zipper.next |> Zipper.next |> Zipper.next
iex> Zipper.node(zipper)
[1,[],[2,3,[4,5]]]
iex> Zipper.end?(zipper)
true

insert_child(zipper, new_child)

insert_child(Zipper.t(), any()) :: Zipper.maybe_zipper()

Inserts a child as the leftmost child of the current focus. Returns an error if called on a leaf.

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> zipper |> Zipper.insert_child(6) |> Zipper.node
[6,1,[],[2,3,[4,5]]]
iex> zipper |> Zipper.down |> Zipper.insert_child(6)
{:error, :insert_child_of_leaf}

insert_left(zipper, node)

insert_left(Zipper.t(), any()) :: Zipper.maybe_zipper()

Inserts a new node as a new sibling to the immediate left of the current focus. Does not change focus. Returns an error if called on the root.

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> Zipper.insert_left(zipper, 0)
{:error, :insert_left_of_root}
iex> zipper |> Zipper.down |> Zipper.insert_left(0) |> Zipper.root |> Zipper.node
[0,1,[],[2,3,[4,5]]]

insert_right(zipper, node)

insert_right(Zipper.t(), any()) :: Zipper.maybe_zipper()

Inserts a new node as a new sibling to the immediate right of the current focus. Does not change focus. Returns an error if called on the root.

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> Zipper.insert_right(zipper, 0)
{:error, :insert_right_of_root}
iex> zipper |> Zipper.down |> Zipper.insert_right(0) |> Zipper.root |> Zipper.node
[1,0,[],[2,3,[4,5]]]

left(zipper)

left(Zipper.t()) :: Zipper.maybe_zipper()

Moves to the next sibling to the left of the current focus. Returns an error if at the root or already at the leftmost sibling at its depth in the tree.

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> Zipper.left(zipper)
{:error, :left_from_root}
iex> zipper |> Zipper.down |> Zipper.left
{:error, :left_from_leftmost}
iex> zipper |> Zipper.down |> Zipper.right |> Zipper.right |> Zipper.left |> Zipper.node
[]

leftmost(zipper)

leftmost(Zipper.t()) :: Zipper.maybe_zipper()

Moves to the leftmost sibling at the same depth as the current focus. Remains in place if already focused on the leftmost sibling. Returns an error if called on the root.

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> Zipper.leftmost(zipper)
{:error, :leftmost_from_root}
iex> zipper |> Zipper.down |> Zipper.leftmost |> Zipper.node
1
iex> zipper |> Zipper.down |> Zipper.right |> Zipper.right |> Zipper.leftmost |> Zipper.node
1

lefts(zipper)

lefts(Zipper.t()) :: [any()] | Zipper.error()

Returns all left siblings of the current focus. Returns an error if called on the root.

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> Zipper.lefts(zipper)
{:error, :lefts_of_root}
iex> zipper |> Zipper.down |> Zipper.lefts
[]
iex> zipper |> Zipper.down |> Zipper.rightmost |> Zipper.lefts
[1,[]]

list_zipper(list)

list_zipper(list()) :: Zipper.t()

Returns a new zipper built from the given list

Example

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

make_node(zipper, node, children)

make_node(Zipper.t(), any(), [any()]) :: any()

Returns a new node created from node and children. The zipper first argument is to provide the context from which to determine how to create a new node.

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> Zipper.make_node(zipper, [8,9], [10,11,12])
[10,11,12]

next(zipper)

next(Zipper.t()) :: Zipper.t()

Moves to the next focus in a depth-first walk through the zipper. If it reaches the end, subsequent calls to next return the same focus

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> zipper |> Zipper.next |> Zipper.node
1
iex> zipper |> Zipper.next |> Zipper.next |> Zipper.node
[]
iex> zipper |> Zipper.next |> Zipper.next
...> |> Zipper.next |> Zipper.next |> Zipper.node
2
iex> zipper = zipper |> Zipper.down |> Zipper.rightmost
...> |> Zipper.down |> Zipper.rightmost
...> |> Zipper.down |> Zipper.rightmost
iex> zipper |> Zipper.next |> Zipper.node
[1,[],[2,3,[4,5]]]
iex> zipper |> Zipper.next |> Zipper.next |> Zipper.node
[1,[],[2,3,[4,5]]]

node(zipper)

node(Zipper.t()) :: any()

Returns the current focus of the zipper

Example

iex> zipper = Zipper.list_zipper([1,[2,3,[4,5]]])
iex> Zipper.node(zipper)
[1,[2,3,[4,5]]]
iex> zipper |> Zipper.down |> Zipper.node
1

path(zipper)

path(Zipper.t()) :: [any()]

Returns a path of nodes leading from the root to, but excluding, the current focus. Returns an empty list at the root.

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> Zipper.path(zipper)
[]
iex> zipper = zipper |> Zipper.down |> Zipper.rightmost |> Zipper.down
iex> zipper.focus
2
iex> Zipper.path(zipper)
[[1,[],[2,3,[4,5]]],[2,3,[4,5]]]

prev(zipper)

prev(Zipper.t()) :: Zipper.maybe_zipper()

Moves to the previous focus in a depth-first walk through the zipper. Returns an error if called on the end of the walk. Returns the root if called on the root.

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> zipper |> Zipper.prev |> Zipper.node
[1,[],[2,3,[4,5]]]
iex> zipper |> Zipper.down |> Zipper.rightmost |> Zipper.prev |> Zipper.node
[]
iex> zipper |> Zipper.down |> Zipper.rightmost |> Zipper.down |> Zipper.rightmost
...> |> Zipper.down |> Zipper.rightmost |> Zipper.next |> Zipper.prev
{:error, :prev_of_end}

remove(zipper)

remove(Zipper.t()) :: Zipper.maybe_zipper()

Removes the current focus from the zipper, moving focus to the node previous to the current focus in a depth-first walk. Will return an error if called on the root

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> Zipper.remove(zipper)
{:error, :remove_root}
iex> zipper |> Zipper.down |> Zipper.remove |> Zipper.node
[[],[2,3,[4,5]]]

replace(zipper, new_focus)

replace(Zipper.t(), any()) :: Zipper.t()

Replaces the current focus with the node passed as the second argument.

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> zipper = Zipper.down(zipper)
iex> Zipper.node(zipper)
1
iex> zipper = Zipper.replace(zipper, 10)
iex> Zipper.node(zipper)
10

right(zipper)

right(Zipper.t()) :: Zipper.maybe_zipper()

Moves to the next sibling to the right of the current focus. Returns an error if at the root or already at the rightmost sibling at its depth in the tree.

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> Zipper.right(zipper)
{:error, :right_from_root}
iex> zipper |> Zipper.down |> Zipper.right |> Zipper.node
[]
iex> zipper |> Zipper.down |> Zipper.right |> Zipper.right |> Zipper.right
{:error, :right_from_rightmost}

rightmost(zipper)

rightmost(Zipper.t()) :: Zipper.maybe_zipper()

Moves to the leftmost sibling at the same depth as the current focus. Remains in place if already focused on the leftmost sibling. Returns an error if called on the root.

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> Zipper.rightmost(zipper)
{:error, :rightmost_from_root}
iex> zipper |> Zipper.down |> Zipper.rightmost|> Zipper.node
[2,3,[4,5]]
iex> zipper |> Zipper.down |> Zipper.rightmost |> Zipper.rightmost |> Zipper.node
[2,3,[4,5]]

rights(zipper)

rights(Zipper.t()) :: [any()] | Zipper.error()

Returns all left right of the current focus. Returns an error if called on the root.

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> Zipper.rights(zipper)
{:error, :rights_of_root}
iex> zipper |> Zipper.down |> Zipper.rights
[[],[2,3,[4,5]]]
iex> zipper |> Zipper.down |> Zipper.rightmost |> Zipper.rights
[]

root(zipper)

root(Zipper.t()) :: Zipper.t()

Returns to the root of the zipper. Remains in place if already on the root.

Examples

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> zipper |> Zipper.root |> Zipper.node
[1,[],[2,3,[4,5]]]
iex> zipper |> Zipper.down |> Zipper.rightmost |> Zipper.down |> Zipper.root |> Zipper.node
[1,[],[2,3,[4,5]]]

to_list(zipper)

to_list(Zipper.t()) :: [any()]

Returns a flat list of all the elements in the zipper, ordered via a depth-first walk, including the root

Examples

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

up(zipper)

up(Zipper.t()) :: Zipper.maybe_zipper()

Moves up to the parent of the current focus, or returns an error if already at the root of the zipper

Example

iex> zipper = Zipper.list_zipper([1,[],[2,3,[4,5]]])
iex> Zipper.up(zipper)
{:error, :up_from_root}
iex> zipper |> Zipper.down |> Zipper.right |> Zipper.up |> Zipper.node
[1,[],[2,3,[4,5]]]

zipper(is_branch, children, make_node, root)

zipper((any() -> boolean()), (any() -> [any()]), (any(), [any()] -> any()), any()) :: Zipper.t()

Returns a new zipper with root as the root tree of the zipper, and is_branch, children and make_node as the internal functions that define construction parameters for the tree.

In order, the arguments are

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

Example

iex> zipper = Zipper.zipper(               # zipper for nested lists
...>   &is_list/1,                         # a branch can have children, so, a list
...>   &(&1),                              # the children of a list is the list itself
...>   fn _node, children -> children end, # a new node is just the new list
...>   [1,[2,3,[4,5]]]
...> )
iex> zipper.focus
[1,[2,3,[4,5]]]