Measured Finger Trees

As I wrote a couple of weeks ago about Finger Trees,

Finger trees combine several features that make them incredibly useful, including [functional] purity, flexibility, efficiency, and simplicity.

A large portion of those advantages spring from the structure of the finger trees themselves, which provide efficient, purely functional deque operations and concatenation. While I was working on completing my finger tree implementation, I began to wonder how it achieved its efficiency, specifically the efficient concatenation. Hinze and Paterson say,

It is easy to check that in each of the invocations of [foldWings], the list argument has length at most 4, so each of these invocations takes Θ(1) time. The recursion terminates when we reach the bottom of the shallower tree, with up to 4 insertions, so the total time taken is Θ(log(min{n1 , n2})), where n1 and n2 are the numbers of elements in the argument trees.

...which is a little too telegraphic for me. The problem is that, in order to get the log n behavior, the tree must be balanced, and no operation in building the finger tree explicitly keeps the tree balanced. Then, I realized that the the structure of the tree it self performed that magic.

Consider a normal binary tree where each node has a data element and two children, and the element in the node is greater than any value under its left child and less than any value under its right child. If the tree is complete, then it is balanced; every internal node has two children, so an operation that traverses from the root of the tree to a specific leaf visits log n nodes. However, if the tree was built from a sorted sequence with no effort at keeping it balanced will structurally resemble a linked list, and an operation attempting to find a specific node will visit n nodes. As a result, with no effort to keep the tree balanced, the worst-case behavior of tree operations will be O(n), not O(log n).

So, what does it mean to be balanced? There are several possibilities; a complete tree is obviously balanced. For finger trees, however, I think the best definition lies in the number of elements at a depth k as compared to depth k-1. For example, continuing with the complete binary tree, the number of elements at depth 0 is 1, the root element. The number of elements at depth 1 is 2; the number at depth 2 is 4; and the number at depth 3 is 8. The number of elements grows exponentially with depth.

Now look at the structure of the finger tree. The spine of the finger tree, where the depth of the structure lies, is not made of a collection of elements, but a collection of 2-3 tree Nodes of the elements of the current level. To put it another way, the first layer of the finger tree contains elements of type T, in the Empty or Single form or in the two Digits; the second layer contains Node<T> elements, and the third layer contains Node<Node<T>> elements. Now, assume that the tree is made entirely of instances of Deep, with a terminal spine of Empty, and that the digits are minimal, in the sense of having the fewest possible contents. At depth 0 are 2 elements of type T. At depth 1 are two elements of type Node<T>, each containing at least 2 elements of type T for a total of at least 4 elements of type T. At depth 2 are two elements of type Node<Node<T>>, containing a total of 8 elements of type T.

As a result of its structure, even in the case of this minimal tree, the number of elements grows exponentially with depth. The finger tree is balanced by its structure with no explicit operations to keep it balanced.

Of course, part of that structure is the guarantee that only elements at each end are easily accessible. But the other half of the finger tree remedies that....

Measurement

I have no intention of trying to provide an insightful lesson into the use of monoids, which when combined with the finger tree make the data structure a very powerful too. For that, check out Monoids and Finger Trees by Heinrich Apfelmus. Instead, I intend to just describe how the monoids and measures work with the Java finger trees.

What is a monoid? On one hand, it is a triple of a set of values, called a carrier set, an operation which is closed in the carrier set as well as being associative, and a specific value from the carrier set which is an identity. On another hand, it is an implementation of the following interface.

public interface Monoid<T>
{
  public T zero();
  public T plus(T l, T r);
}

With, of course the same property requirements and where T is the carrier set.  For a standard example of monoids, there are

  public static class IntegerAdd implements Monoid<Integer>
  {
    @Override public Integer plus(Integer l, Integer r) { return l + r; }
    @Override public Integer zero() { return 0; }
  }

integers as the carrier set with addition as the operation and 0 as the identity form a monoid. Also,

  public static class IntegerMult implements Monoid<Integer>
  {
    @Override public Integer plus(Integer l, Integer r) { return l * r; }
    @Override public Integer zero() { return 1; }
  }

integers with multiplication (as "plus", the operation) and 1 (as the zero) form another monoid. ("1 is the zero of multiplication." I dedicate that sentence to my four (!) calculus instructors at the University of Texas at Austin, who are probably rolling in their graves at the thought of me discussing mathematics (even though I don't think any of them are dead).)

Anyway, with a monoid, the next thing I need to build is a Measure,

public abstract class Measure<T, V> implements Monoid<V>
{
  public final Monoid<V> monoid;
  public Measure(Monoid<V> monoid) { this.monoid = monoid; }
  @Override public V plus(V v1, V v2) { return monoid.plus(v1, v2); }
  public V plus(V v1, V v2, V v3) { return monoid.plus(v1, monoid.plus(v2, v3)); }
  @Override public V zero() { return monoid.zero(); }
  public abstract V measure(T t);
}

A Measure<T,V> is a monoid over a carrier set V, based on a lower level monoid which is passed as an argument to the Measure's constructor. The measure adds two operations. One is a three-argument plus method, which is safe due to the properties of the monoid and very convenient. The other is the method measure, which takes an element of a type T and projects that element into the carrier set, V. To put that another way, measure constructs a tag value for the T element as required by the ultimate data structure being constructed from the finger tree.

An example Measure is

  public static class Counter<T> extends Measure<T,Integer>
  {
    public Counter() { super(Monoids.INTEGER_ADD); }
    @Override public Integer measure(T t) { return 1; }
  }

The Counter projects elements of T into the carrier set Integer by returning 1; with the Integer addition monoid, this measure counts the elements in a measured data structure.

Following along Hinze and Paterson, Digits are relatively unchanged, although they do now carry a reference to a Measure used to compute measure tags for the Digit instances. Nodes, on the other hand, also carry a tag value

  public final V tag;

representing the measure of the contents of the Node. Likewise the Empty, Single, and Deep classes have tag fields. The tag of Empty is the zero of the monoid, while Single and Deep are tagged with the plus-combination of the tags of the contained elements.

Besides managing the tag values, what can you do with a measured finger tree? How about splitTree?

  public abstract Split<MeasuredFingerTree<T,V>,T,V> splitTree(Predicate<V> p, V i);

A Split of a finger tree is a triple containing two finger trees and a designated value. If you have a finger tree representing a sequence of elements \(t_i\) tagged with measures \(v_i\),
\[ (t_0,v_0), (t_1,v_1), \ldots, (t_n,v_n) \]
as well as a monotonic predicate p over V and an initial V value i, splitTree creates a Split structure containing
\[ [ (t_0,v_0), \ldots, (t_{j-1},v_{j-1}) ], t_j, [ (t_{j+1},v_{j+1}), \ldots, (t_n,v_n) ] \]
where \(p(i + v_0 + \ldots + v_{j-1}) \equiv \textbf{false})\), but \(p(i + v_0 + \ldots + v_j) \equiv \textbf{true})\). In other words, splitTree divides the finger tree into a prefix where the predicate p is false, a designated value where p becomes true, and a suffix, where p remains true if it is monotonic. (For more on monotonic predicates, see apfelmus' article; basically it means the predicate is false up to some value where it becomes true and remains true for all further values. All modulo the monoid, of course.)

A predicate is an implementation of the interface

public interface Predicate<V>
{
  public boolean apply(V v);
}

and an example is

final int half = max/2;
new Predicate<Integer>() { @Override public boolean apply(Integer v) { return half < v; } };

where max is the number of elements in a given collection. Given the Counter measure, this predicate can split a tree in half.

The splitTree method is implemented by Empty as

    @Override public Split<MeasuredFingerTree<T,V>, T, V> splitTree(Predicate<V> p, V i) { throw new IndexOutOfBoundsException(); }

In other words, and Empty finger tree cannot be split. For Single, the implementation is

    @Override
    public Split<MeasuredFingerTree<T, V>, T, V> splitTree(Predicate<V> p, V i)
    {
      MeasuredFingerTree<T, V> empty = empty(measure);
      return new Split<MeasuredFingerTree<T, V>, T, V>(empty, t, empty);
    }

(Hinze and Paterson put some preconditions on the operation:

Note also that the preconditions \(\neg p.i\) and \(p.(i + t)\) are used only if the split occurs at one or other end of the sequence. Consequently, if we treat those cases specially it suffices to require that the initial tree t is non-empty....

which is reflected in the assumption that a Single element represents the right place to split.)

For Deep instances, splitTree is

    @Override
    public Split<MeasuredFingerTree<T,V>,T,V> splitTree(Predicate<V> p, V i)
    {
      final V vpr = measure.plus(i, left.measure());
      if (p.apply(vpr))
      {
        final Split<Digit<T,V>,T,V> spl = left.splitDigit(p, i);
        MeasuredFingerTree<T,V> prefix = empty(measure);
        for (T t : spl.prefix()) { prefix = prefix.addLast(t); }
        final MeasuredFingerTree<T,V> suffix = deep(spl.suffix(), spine, right);
        return new Split<MeasuredFingerTree<T,V>,T,V>(prefix, spl.current(), suffix);
      }
      final V vm = measure.plus(vpr, spine.tag);
      if (p.apply(vm))
      {
        final Split<MeasuredFingerTree<Node, V>, Node<T,V>, V> splSpine = spine.splitTree(p, vpr);
        final Split<Digit<T,V>,T,V> splDigit
            = splSpine.current().toDigit().splitDigit(p, measure.plus(vpr, splSpine.prefix().tag));
        final MeasuredFingerTree<T,V> prefix = deep(left,splSpine.prefix(), splDigit.prefix());
        final MeasuredFingerTree<T,V> suffix = deep(splDigit.suffix(), splSpine.suffix(), right);
        return new Split<MeasuredFingerTree<T,V>,T,V>(prefix, splDigit.current(), suffix);
      }
      else
      {
        final Split<Digit<T,V>,T,V> spl = right.splitDigit(p, vm);
        MeasuredFingerTree<T,V> suffix = empty(measure);
        for (T t : spl.suffix()) { suffix = suffix.addLast(t); }
        final MeasuredFingerTree<T,V> prefix = deep(left, spine, spl.prefix());
        return new Split<MeasuredFingerTree<T,V>,T,V>(prefix, spl.current(), suffix);
      }
    }

The first branch is taken if the split point is in the left Digit, the second if the split point is in the spine, and the third if the split point is in the right Digit. The first and third branches are symmetric. The second branch first splits the spine (producing splSpine), then converts the designated element (which is a Node<T>, remember) to a Digit and splits it to get the designated element and partial prefixes and suffixes to be added to the original edge digit and the prefix and suffix spines. All three branches use a specialized Deep constructor, the deep method, which correctly handles the possibility of empty Digits. (Under normal circumstances, the invariant of Digits includes that they are non-empty.)

Because of the balanced nature of the finger tree, this method can only recurse into the spine log n times; the other operations are constant time; as a result this method is O(log n).

I will post links to the code soon, after I have played with it some more. In the mean time, I did find an implementation of finger trees in the Functional Java library.

Comments

Thanks for this wonderful post. I just stumbled on it a few days back when trying to write a javascript finger tree implementation and it was immensely useful.

I was wondering if you ever got around to posting the code -- I'm a little stumped on the logic around splitDigit and I'd love a peak. Otherwise I think I have it all buttoned up, but without splitTree it's not all that useful.

Also, is there an explicit license for this code? I'd like to MIT license my implementation but it draws heavily from your example so it could be considered derivative. I'd really like your explicit permission to license it so permissively (with attribution, of course).

Dean Landolt
'2012-02-13T21:15:59.582-06:00'

Copyright © 2007-2017 Tommy M. McGuire