ExRoseTree - a Rose Tree and Zipper in Elixir with a slew of navigation primitives

Your Libraries & OS Mentoring Libraries
, , ,
1

Hello everyone,

I’m excited to announce the release of ExRoseTree, a Rose Tree and Zipper in Elixir with a slew of navigation primitives and traversal functions.

This project began as a generic exploration in designing a Zipper for another project of mine using a much more specialized version of a rose tree, but I enjoyed working on it so much that I decided to flesh it out and hopefully make it useful to others, whether directly in their own projects or simply just through learning more about the data structures and algorithms themselves.

Aside from the obvious goals of implementing a rose tree with a functional zipper, my primary aim was to elevate it above a simple ‘example-style’ implementation, as many one-off data structure implementations remain, by designing a sort of navigational pattern language API on top of the Zipper with the hopes of greatly improving its intuitive usability. Furthermore, I wanted to buttress it with extensive test coverage and example usage.

A few possible use-cases

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

Basically anything that can be hierarchically represented and has (potentially) arbitrary branching. Combined with the Zipper, you get an efficient and context-aware method of traversing and manipulating the tree.

An overview of the “navigational pattern language” (inspired by gender-neutral family tree taxonomy)

Common prefixes include first, last, next, and previous and, along with the _at suffix, are used in conjunction with several major categories of navigation primitives:

  • Direct ancestors - i.e. parent, grandparent, great_grandparent (7 fns)
  • Direct descendants - i.e. child, grandchild, great_grandchild (9 fns)
  • sibling - both before and after the current focus (21 fns)
  • nibling - gender-neutral for niece/nephew (16 fns)
  • pibling - gender-neutral for aunt/uncle (17 fns)
  • Cousins - first cousins, second cousins, etc (12 fns)

Other, less common, descriptors that are used include ancestral, descendant, and extended.

Many of the navigation functions take an optional predicate, allowing you to do a specialized find within the confines of the navigation.

For example Zipper.first_sibling(zipper) will move the Zipper’s focus to the first sibling if one exists, or return nil. But Zipper.first_sibling(zipper, &(&.term == 5)) will look for the first occurrence of a node with its term equal to 5. This is done starting from the first sibling within the list of all previous siblings of the current focus. If a match is found, the Zipper’s focus is moved there. If none match, or if there are no previous siblings, the function will return nil.

Generic and specialized traversals

In addition to the navigation primitives above, there are a wide range of traversal functions, including pure movement, searching, mapping, and accumulating.

The main, single-move traversal primitives include:

  • rewind - moves the focus back along the Zipper’s path. This is like the actual unzipping of a physical zipper, the path being the zipped together teeth of the zipper. Since unzip and zip are overloaded in other contexts (like Enum), I opted for a different word that still captured the essence of the operation.
  • forward - moves the focus to the “right” in a breadth-first manner, towards the last node
  • backward - moves the focus to the “left” in a breadth-first manner, towards the root
  • descend - moves the focus “down” in a depth-first manner, towards the last node
  • ascend - moves the focus “up” in a depth-first manner, towards the root

These (and the other nav primitives) can be used in several generic traversal functions:

  • move_for/3
  • move_if/3
  • move_until/3
  • move_while/3
  • find/3
  • map/3
  • accumulate/4

The 5 main traversal types provide shortcut functions combining their movement with each of the generic traversals, for example: forward_if/2, forward_find/2 or forward_accumulate/3. Ultimately each traversal type has a total of 8 helper functions related to the main primitive: one for each generic traversal function and one for repeating the movement all the way to either the last node or the root.

While there is enough meat here for it get its first release, it is still a work-in-progress, and I already have several ideas for areas of improvement. If you are so inclined to provide feedback, suggestions, or corrections to the docs, design, or functionality, I’d be much obliged. And if you feel like getting hands on with bug fixes or new features, I’m more than open to proposals and pull-requests.

Hopefully some of you find ExRoseTree useful, or at the very least interesting to peruse. So thanks in advance and happy zipping!

13 Likes
2

Zippers are great! This library looks very complete.

Some documentation feedback: highlight unfold and usage of it, since it looks like the main mechanism for turning your tree-like-thing into a rose tree.

3

Thank you! Yes, clarifying documentation is high on my priority list: I’d rather make something that already exists better understood before adding more functionality. In that light, thanks for the pointer; I’ll give some love to unfold and try to come up with some more useful examples!