On Outlines, Rose Trees and Zippers

In this article we will discuss outlines, like the ones we compose before writing an article or speech, hierarchical lists, rose trees, and zippers, where the last three are data structures used in computer science. All four are closely related, and the last three prove useful in the design and construction of web applications. We will discuss these notions in general, as well as their application to building a parser-renderer for Markdown and a content-management system based on it. While the ideas are independent of any particular programming language, we will present some snippets of code using Elm, a statically typed language of pure functions.

Introduction

In school, we all learned how to make outlines — the starting point for a writing assignment, a plan for a lesson, event, project, etc. Here is an example:

Vertebrates
   Cold-blooded
       Frogs
       Salamanders
       Snakes
       Turtles
    Warm-blooded
       Dogs
       Cats
       Horses

An outline is characterized by lines of text (strings) that are indented a certain amount, say, a multiple k of three spaces. The integer k defines the level of the piece of text. Thus we could also represent the outline as a list of pairs:

type alias Outline = List (String, Int),

namely,

[(“Vertebrates”, 0), (“Cold-blooded”, 1), 
 (“Frogs”, 2), (“Salamanders”, 2), 
 {“Snakes”, 2), (“Turtles”, 2), 
 (“Warm-blooded”, 1), (“Dogs”, 2), 
 (“Cats”, 2), (“Horses”, 2)]

We use the Elm programming language to express such notions here and below.

The example just given is a hierarchical list: a list of elements endowed with a function level that assigns to every list element an integer, and which satisfies the following:

   if e is a list element and e' is the next element, 
   then level(e') <= level(e) + 1

In other words, the next element is either one level deeper, or at the same or a previous level. This condition ensures that one can reconstruct an outline from a hierarchical list of strings.

Still another way of thinking about our data is via *labeled rose trees*, as in the figure below. A rose tree is a tree in which each node can have an arbitrary number of children. In the Figure, the root node, labeled *Vertebrates*, has two children, labeled *Cold-blooded* and *Warm-blooded*. These nodes have four and three children, respectively.

Vertebrate rose tree

In Elm, a rose tree is defined by

type Tree a = Tree { label : a, children : List (Tree a) }

The definition is taken from the package zwilias/elm-rosetree. For converting outlines to trees and vice versa, one can use the package htree.

Using rose trees

So far, so good. But for what purposes might we use a rose tree?
For lack of more extensive knowledge of the subject, I’ll recount my own experience. For a project I was working on, I had decided to build a pure Elm parser for Markdown that would also support the rendering of mathematical formulas using MathJax. Doing a bit of homework before starting, I read the very last section of this Commonmark spec. The article recommends a two-phase approach: first discover the block structure of the text (ordinary paragraphs quotations, lists, etc), then parse the content of those blocks. Since a given block may have any number of child blocks, this structure is naturally represented as a rose tree. As an example, consider the following piece of markdown text, which fits naturally into the outline paradigm:

# Philosophy notes
*Monday*
> **Nature of reality?**
   Why something rather than nothing. 
 
   If nothing, no one to ask this question.
 
   Tree in forest / fall
Confusing.

The lines beginning with “Why”, “If”, and “Tree” are indented three spaces and therefore are children of the quotation block that contains the word “Nature.” When parsed, this text yields a structure which could be represented as

[ (DOCUMENT, Root, 0)
 , (Philosophy…, Heading 1, 1)
 , (Monday, Italic, 1)
 , (Nature …, Quotation, 1)
 , (Why …, Paragraph, 2)
 , (If …, Paragraph, 2)
 , (Tree …, Paragraph, 2)
 , (Confusing …, Paragraph, 1)
]

where we list content, block type and level. The same structure can be represented as in the figure below:

Parse tree

There is a root block, four level one blocks, one of which has three children, each of which are of level two. In the case at hand, the nodes of the tree are labeled by both content (a string) and a type. Thus the left-most block above has content “Philosophy notes” and type Heading 1.

Building rose trees

How does one build up the rose tree as the parser reads the input text in the example? This key is to use the right data structure, which in this case is a zipper. One can think of such an entity as a rose tree plus a focus, which is a subtree, the “currently focused subtree.” Here is the formal definition from zwilias/elm-rosetree, where we have omitted one field which is an implementation detail:

{-| Represents a location within a tree,
always pointing at the root or one of
its descendant trees.
-}
type Zipper a
   = Zipper
    {  focus : Tree a
     , before : List (Tree a)
     , after : List (Tree a)
     , …
    }

As an example, let Vertebrates be the outline considered at the beginning of this article. Here we use the convention that tree is represented by the label of its root node, where we tacitly assume that these are unique. The zipper for this rose tree has various states, which we can think of as being represented by the pair (Tree, focus), e.g, (Vertebrates, Vertebrates), (Vertebrates, Cold-blooded), (Vertebrates, Frogs), etc. Here we have gone from state to state of the zipper by choosing a child of the current focus as the new focus. But we could also choose a sibling or a parent, or even the root. In a word, a zipper is a structure endowed with a set of functions for building a tree, navigating it, and transforming it :

Imagine walking through a Tree structure. You can step from a node to its parent, its children or one of its siblings. At every step of the way, you’re “at” a tree. A `Tree.Zipper` represents such a step, and offers an API to navigate and modify the tree structure while walking through it.
— zwilias/rosetree

Here are a few details on how Markdown text is parsed into a rose tree. This is an operation that we want to do as fast as possible. Therefore, instead of doing character-oriented parsing, we adopt a line-oriented strategy:

1. Split the input text into lines

2. Process the lines using a finite-state machine that constructs a hierarchical list of the form (element, level), where an element consists of content (a string) and information on the type of block, e.g., heading, paragraph, quotation, math element, etc.

3. Convert the hierarchical list into a rose tree using HTree.fromList, where
HTree is defined here .

Step (2) is very efficient, because the finite-state machine needs only examine the first line of a block to determine its type.

Table of contents

The example of the vertebrates reveals another use of rose trees: construction of an active table of contents. Imagine that the outline above is the table of contents for an online book. In its original state, it looks like this:

Vertebrates
 + Cold-blooded
 + Warm-blooded

Click on Cold-blooded. The outline “opens”:

Vertebrates
   Cold-blooded
      Frogs
      Salamanders
      Snakes
      Turtles
+ Warm-blooded

Click on Warm-blooded, and it becomes

Vertebrates
   + Cold-blooded
     Warm-blooded
        Dogs
        Cats
        Horses

You can imagine the outline having more levels, so that one can reveal grand-children, great-grandchildren, etc. The key to a pleasant and efficient construction of such an active table of contents is the realization that it is represented by a zipper — a rose tree with a subree that is “in focus.”

Here is a demo which also includes some code. This is also the technology used in this draft book on physics.

Diffing and Merging

Another application of rose trees, again one which came up in parsing Math + Markdown, is the following. When a document is parsed, the result is an abstract syntax tree whose nodes are marked with an id of the form [blockId, version]. The version is incremented each time an edit is made, and the blockId uniquely identifies the block. Mathematical formulas are rendered via an interface with Mathjax.js. For this interface to function properly, nodes containing mathematical text require a “fresh” id to be properly rendered. Because rendering mathematical text is expensive, one does not want to re-render nodes unnecessarily. Therefore having all fresh id’s for new versions, while it works, is a bad idea. A way around this difficulty is to diff the new and old abstract syntax trees, replacing only those nodes in the old tree whose content has changed. This operation on abstract syntax trees results in large performance gains, gains that are quite apparent to an author editing a document.

For a minimal example of the diff/merge process, consider two pieces of text. one has the form

Equation A
Equation B

while the other has the form below

Equation A
Equation BB

Call these textP and textQ respectively. Let parse version text be the parsing function; we will apply it to textP with version= 7 to obtain the following tree:

First tree

Now change equation B to equation BB and apply parse 8 textQ. The app in which parse lives keeps track of each version, incrementing it whenever an edit is made. This is the resulting tree:

Second parse tree

Finally, we diff the last two trees by comparing the respective node contents. Here is the result:

New tree: diffed and merged

MathJax remembers that the node with id [1,7] has already been processed and leaves it alone. But it has never seen a node with id [2,8], and so it is processed. Since human editors work on a small piece of text at time, this strategy results in much faster rendering. A page may have fifty math elements, but in a typical edit-parse-render cycle, at most one of the math elements changes and therefore has to be re-rendered.

Remark. The diff-merge strategy described above uses the Tree.Diff package Such a strategy is analogous the one which Elm uses in diffing and patching its virtual DOM. Diff-patch is one of the reasons that Elm is able to render the model of an application efficiently and therefore rapidly.

I would like to thank Ilias van Peer for many helpful comments in the preparation of this article.