ExRoseTree (ExRoseTree v0.1.4)

A Rose Tree with Functional Zipper in Elixir

What's a Rose Tree?

A Rose Tree, also known as a multi-way or m-way tree by some, is a general-purpose, recursively defined data structure where each position can have an an arbitrary value and an arbitrary number of children. Each child is, itself, another Rose Tree.

ExRoseTree is implemented as a very simple struct defstruct ~w(term children)a with an equally simple typespec:

@type t() :: %__MODULE__{
        term: term(),
        children: [t()]
      }

What's it good for?

Practically speaking, a few good use cases for Rose Trees could be:

outlines
file systems
parsing HTML/XML documents
abstract syntax trees
decision trees
data visualization (org charts, family trees, taxonomies, nested menus)

This implementation also comes with a companion ExRoseTree.Zipper data structure, and greatly enhances the usefulness of the standard Rose Tree.

So what's a Zipper?

A Zipper of a given data structure can be thought of as taking the derivative of that data structure. It provides an efficient, context-aware approach to traversing and manipulating the contents of the Rose Tree.

In his foundational paper formalizing the idea, Gerard Huet perhaps describes it best:

The basic idea is simple: the tree is turned inside-out like a returned glove, pointers from the root to the current position being reversed in a path structure. The current location holds both the downward current subtree and the upward path. All navigation and modification primitives operate on the location structure. Going up and down in the structure is analogous to closing and opening a zipper in a piece of clothing, whence the name.

And what's a Zipper of a Rose Tree good for?

In practice, ExRoseTree.Zipper can be used as an effective means of representing everything from a cursor in a text editor to a selected item in a nested sidebar/dropdown menu in a UI which needs to maintain persistent focus. Essentially, anything that has an arbitrary hierarchy and would necessitate or benefit from the capability of being context-aware could be a candidate for a Rose Tree with Zipper.

Installation

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

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

Example Usage

alias ExRoseTree, as: Tree
alias ExRoseTree.Zipper

Tree.new(1)
# %ExRoseTree{term: 1, children: []}

tree = Tree.new(1, [2,3,4,5])
# %ExRoseTree{term: 1, children: [
#   %ExRoseTree{term: 2, children: []},
#   %ExRoseTree{term: 3, children: []},
#   %ExRoseTree{term: 4, children: []},
#   %ExRoseTree{term: 5, children: []},
# ]}

zipper = Zipper.new(tree)
# %ExRoseTree.Zipper{
#   focus: %ExRoseTree{
#     term: 1,
#     children: [
#       %ExRoseTree{term: 2, children: []},
#       %ExRoseTree{term: 3, children: []},
#       %ExRoseTree{term: 4, children: []},
#       %ExRoseTree{term: 5, children: []}
#     ]
#   },
#   prev: [],
#   next: [],
#   path: []
# }

zipper = Zipper.last_child(zipper)
# %ExRoseTree.Zipper{
#   focus: %ExRoseTree{term: 5, children: []},
#   prev: [
#     %ExRoseTree{term: 4, children: []},
#     %ExRoseTree{term: 3, children: []},
#     %ExRoseTree{term: 2, children: []}
#   ],
#   next: [],
#   path: [%ExRoseTree.Zipper.Location{prev: [], term: 1, next: []}]
# }

zipper = Zipper.backward(zipper)
# %ExRoseTree.Zipper{
#   focus: %ExRoseTree{term: 4, children: []},
#   prev: [
#     %ExRoseTree{term: 3, children: []},
#     %ExRoseTree{term: 2, children: []}
#   ],
#   next: [%ExRoseTree{term: 5, children: []}],
#   path: [%ExRoseTree.Zipper.Location{prev: [], term: 1, next: []}]
# }

zipper = Zipper.rewind_map(zipper, &Tree.map_term(&1, fn t -> t * 10 end))
# %ExRoseTree.Zipper{
#   focus: %ExRoseTree{
#     term: 10,
#     children: [
#       %ExRoseTree{term: 2, children: []},
#       %ExRoseTree{term: 3, children: []},
#       %ExRoseTree{term: 40, children: []},
#       %ExRoseTree{term: 5, children: []},
#     ]
#   },
#   prev: [],
#   next: [],
#   path: []
# }

Zipper.to_tree(zipper)
# %ExRoseTree{
#   term: 10,
#   children: [
#     %ExRoseTree{term: 2, children: []},
#     %ExRoseTree{term: 3, children: []},
#     %ExRoseTree{term: 40, children: []},
#     %ExRoseTree{term: 5, children: []}
#   ]
# }

Testing and Disclaimer

While great pains have been taken to provide extensive test coverage--over 800 tests at present, this library is still pre-1.0, so be sure to do your due diligence for your own use case.

To run the test suite:

$ mix deps.get
$ mix test

To run test coverage with excoveralls:

$ mix deps.get
$ mix coveralls

or for HTML output:

$ mix deps.get
$ MIX_ENV=test mix coveralls.html

Summary

Guards

empty?(value)

leaf?(value)

parent?(value)

rose_tree?(value)

Basic Functionality

all_rose_trees?(values)

Returns whether a list of values are all ExRoseTrees or not. Will return true if passed an empty list.

empty()

Initializes an empty tree.

new(term, children \\ [])

Initializes a new tree with the given term.

Term

get_term(tree)

Returns the inner term of an ExRoseTree.

map_term(tree, map_fn)

Applies the given function to the tree term.

set_term(tree, term)

Sets the tree term to the given term.

Children

append_child(tree, child)

Appends the given child to the tree's children.

get_children(tree)

Returns the children of an ExRoseTree.

has_child?(tree, predicate)

Returns whether or not the current tree has a child that matches the predicate.

insert_child(tree, child, index)

Inserts a new child into the tree's children at the given index.

map_children(tree, map_fn)

Applies the given function to each child tree. The map_fn should return a valid ExRoseTree struct.

pop_first_child(tree)

Removes the first child of the tree's children.

pop_last_child(tree)

Removes the last child of the tree's children.

prepend_child(tree, child)

Prepends the given child to the tree's children.

remove_child(tree, index)

Removes a child from the tree's children at the given index.

set_children(tree, children)

Sets the tree children to the given list of children.

Special

unfold(seed, unfold_fn)

Given a seed value and an unfold_fn(), generates a new rose tree.

Types

predicate()

t()

The foundational, recursive data type of an ExRoseTree.

unfold_fn()

A function that takes a seed value and returns a new ExRoseTree and a list of new seeds to use for children. Care must be taken that you don't create a function that infinitely creates new seeds, in other words, the function should have a terminating base case.

Guards

empty?(value)

(macro)

leaf?(value)

(macro)

parent?(value)

(macro)

rose_tree?(value)

(macro)

Basic Functionality

all_rose_trees?(values)

@spec all_rose_trees?([term()]) :: boolean()

Returns whether a list of values are all ExRoseTrees or not. Will return true if passed an empty list.

Examples

iex> trees = for t <- [5,4,3,2,1], do: ExRoseTree.new(t)
...> ExRoseTree.all_rose_trees?(trees)
true

empty()

@spec empty() :: t()

Initializes an empty tree.

Examples

iex> ExRoseTree.empty()
%ExRoseTree{term: nil, children: []}

new(term, children \\ [])

@spec new(term(), [t() | term()]) :: t()

Initializes a new tree with the given term.

Examples

iex> ExRoseTree.new("new term")
%ExRoseTree{term: "new term", children: []}

iex> ExRoseTree.new(5, [4, 3, 2, 1])
%ExRoseTree{
  term: 5,
  children: [
    %ExRoseTree{term: 4, children: []},
    %ExRoseTree{term: 3, children: []},
    %ExRoseTree{term: 2, children: []},
    %ExRoseTree{term: 1, children: []}
  ]
}

iex> children = [
...>   %ExRoseTree{term: 4, children: []},
...>   3,
...>   %ExRoseTree{term: 2, children: []},
...>   %ExRoseTree{term: 1, children: []}
...> ]
...> ExRoseTree.new(5, children)
%ExRoseTree{
  term: 5,
  children: [
    %ExRoseTree{term: 4, children: []},
    %ExRoseTree{term: 3, children: []},
    %ExRoseTree{term: 2, children: []},
    %ExRoseTree{term: 1, children: []}
  ]
}

Term

get_term(tree)

@spec get_term(t()) :: term()

Returns the inner term of an ExRoseTree.

Examples

iex> tree = ExRoseTree.new(5)
...> ExRoseTree.get_term(tree)
5

map_term(tree, map_fn)

@spec map_term(t(), (term() -> term())) :: t()

Applies the given function to the tree term.

Examples

iex> tree = ExRoseTree.new(5)
...> ExRoseTree.map_term(tree, fn x -> x * 2 end)
%ExRoseTree{term: 10, children: []}

set_term(tree, term)

@spec set_term(t(), term()) :: t()

Sets the tree term to the given term.

Examples

iex> tree = ExRoseTree.new(5)
...> ExRoseTree.set_term(tree, "five")
%ExRoseTree{term: "five", children: []}

Children

append_child(tree, child)

@spec append_child(t(), t() | term()) :: t()

Appends the given child to the tree's children.

Examples

iex> tree = ExRoseTree.new(5, [4, 3, 2, 1])
...> ExRoseTree.append_child(tree, 0)
%ExRoseTree{
  term: 5,
  children: [
    %ExRoseTree{term: 4, children: []},
    %ExRoseTree{term: 3, children: []},
    %ExRoseTree{term: 2, children: []},
    %ExRoseTree{term: 1, children: []},
    %ExRoseTree{term: 0, children: []}
  ]
}

get_children(tree)

@spec get_children(t()) :: [t()]

Returns the children of an ExRoseTree.

Examples

iex> tree = ExRoseTree.new(5, [4,3,2,1])
...> ExRoseTree.get_children(tree)
[
  %ExRoseTree{term: 4, children: []},
  %ExRoseTree{term: 3, children: []},
  %ExRoseTree{term: 2, children: []},
  %ExRoseTree{term: 1, children: []}
]

has_child?(tree, predicate)

@spec has_child?(t(), (t() -> boolean())) :: boolean()

Returns whether or not the current tree has a child that matches the predicate.

Examples

iex> tree = ExRoseTree.new(5, [4,3,2,1])
...> ExRoseTree.has_child?(tree, &(&1.term == 2))
true

insert_child(tree, child, index)

@spec insert_child(t(), t() | term(), integer()) :: t()

Inserts a new child into the tree's children at the given index.

Examples

iex> tree = ExRoseTree.new(5, [4, 3, 2, 1])
...> ExRoseTree.insert_child(tree, 3.5, 2)
%ExRoseTree{
  term: 5,
  children: [
    %ExRoseTree{term: 4, children: []},
    %ExRoseTree{term: 3, children: []},
    %ExRoseTree{term: 3.5, children: []},
    %ExRoseTree{term: 2, children: []},
    %ExRoseTree{term: 1, children: []}
  ]
}

map_children(tree, map_fn)

@spec map_children(t(), (t() -> t())) :: t()

Applies the given function to each child tree. The map_fn should return a valid ExRoseTree struct.

Examples

iex> tree = ExRoseTree.new(5, [4, 3, 2, 1])
...> ExRoseTree.map_children(tree, fn child ->
...>   ExRoseTree.map_term(child, fn x -> x * 2 end)
...> end)
%ExRoseTree{
  term: 5,
  children: [
    %ExRoseTree{term: 8, children: []},
    %ExRoseTree{term: 6, children: []},
    %ExRoseTree{term: 4, children: []},
    %ExRoseTree{term: 2, children: []}
  ]
}

pop_first_child(tree)

@spec pop_first_child(t()) :: {t(), t() | nil}

Removes the first child of the tree's children.

Examples

iex> tree = ExRoseTree.new(5, [4, 3, 2, 1])
...> ExRoseTree.pop_first_child(tree)
{
  %ExRoseTree{
    term: 5,
    children: [
      %ExRoseTree{term: 3, children: []},
      %ExRoseTree{term: 2, children: []},
      %ExRoseTree{term: 1, children: []}
    ]
  }, %ExRoseTree{term: 4, children: []}
}

pop_last_child(tree)

@spec pop_last_child(t()) :: {t(), t() | nil}

Removes the last child of the tree's children.

Examples

iex> tree = ExRoseTree.new(5, [4, 3, 2, 1])
...> ExRoseTree.pop_last_child(tree)
{
  %ExRoseTree{
    term: 5,
    children: [
      %ExRoseTree{term: 4, children: []},
      %ExRoseTree{term: 3, children: []},
      %ExRoseTree{term: 2, children: []}
    ]
  }, %ExRoseTree{term: 1, children: []}
}

prepend_child(tree, child)

@spec prepend_child(t(), t() | term()) :: t()

Prepends the given child to the tree's children.

Examples

iex> tree = ExRoseTree.new(5, [4, 3, 2, 1])
...> ExRoseTree.prepend_child(tree, 0)
%ExRoseTree{
  term: 5,
  children: [
    %ExRoseTree{term: 0, children: []},
    %ExRoseTree{term: 4, children: []},
    %ExRoseTree{term: 3, children: []},
    %ExRoseTree{term: 2, children: []},
    %ExRoseTree{term: 1, children: []}
  ]
}

remove_child(tree, index)

@spec remove_child(t(), integer()) :: {t(), t() | nil}

Removes a child from the tree's children at the given index.

Examples

iex> tree = ExRoseTree.new(5, [4, 3, 2, 1])
...> ExRoseTree.remove_child(tree, 2)
{
  %ExRoseTree{
    term: 5,
    children: [
      %ExRoseTree{term: 4, children: []},
      %ExRoseTree{term: 3, children: []},
      %ExRoseTree{term: 1, children: []}
    ]
  },
  %ExRoseTree{term: 2, children: []}
}

set_children(tree, children)

@spec set_children(t(), [t() | term()]) :: t()

Sets the tree children to the given list of children.

Examples

iex> tree = ExRoseTree.new(5)
...> ExRoseTree.set_children(tree, [4, 3, 2, 1])
%ExRoseTree{
  term: 5,
  children: [
    %ExRoseTree{term: 4, children: []},
    %ExRoseTree{term: 3, children: []},
    %ExRoseTree{term: 2, children: []},
    %ExRoseTree{term: 1, children: []}
  ]
}

Special

unfold(seed, unfold_fn)

@spec unfold(seed :: term(), unfold_fn()) :: t()

Given a seed value and an unfold_fn(), generates a new rose tree.

Examples

iex> unfolder = fn
...>   x when x > 0 -> {Integer.to_string(x), Enum.to_list(0..x-1)}
...>   x -> {Integer.to_string(x), []}
...> end
...> ExRoseTree.unfold(3, unfolder)
%ExRoseTree{
  term: "3",
  children: [
    %ExRoseTree{term: "0", children: []},
    %ExRoseTree{
      term: "1",
      children: [%ExRoseTree{term: "0", children: []}]
    },
    %ExRoseTree{
      term: "2",
      children: [
        %ExRoseTree{term: "0", children: []},
        %ExRoseTree{
          term: "1",
          children: [%ExRoseTree{term: "0", children: []}]
        }
      ]
    }
  ]
}

Types

predicate()

@type predicate() :: (t() -> boolean())

t()

@type t() :: %ExRoseTree{children: [t()], term: term()}

The foundational, recursive data type of an ExRoseTree.

term can by any valid Erlang term()
children is a list of t()

unfold_fn()

@type unfold_fn() :: (seed :: term() -> {term(), [seed :: term()]})