Conc-tree list

Not to be confused with cons.

A conc-tree is a data structure that stores element sequences, and provides amortized O(1) time append and prepend operations, O(log n) time insert and remove operations and O(log n) time concatenation. This data structure is particularly viable for functional task-parallel and data-parallel programming, and is relatively simple to implement compared to other data-structures with similar asymptotic complexity. Conc-trees were designed to improve efficiency of data-parallel operations that do not require sequential left-to-right iteration order, and improve constant factors in these operations by avoiding unnecessary copies of the data. Orthogonally, they are used to efficiently aggregate data in functional-style task-parallel algorithms, as an implementation of the conc-list data abstraction. Conc-list is a parallel programming counterpart to functional cons-lists, and was originally introduced by the Fortress language.

Operations

The basic conc-tree operation is concatenation. Conc-trees work on the following basic data-types:

trait Conc[T] {
  def left: Conc[T]
  def right: Conc[T]
  def level: Int
  def size: Int
}

case class Empty[T] extends Conc[T] {
  def level = 0
  def size = 0
}

case class Single[T](elem: T) extends Conc[T] {
  def level = 0
  def size = 1
}

case class <>[T](left: Conc[T], right: Conc[T]) extends Conc[T] {
  val level = 1 + math.max(left.level, right.level)
  val size = left.size + right.size
}

The <> type represents inner nodes, and is pronounced conc, inspired by :: (the cons type) in functional lists, used for sequential programming.

Concatenation in O(log n) time then works by ensuring that the difference in levels (i.e. heights) between any two sibling trees is one or less, similar to invariants maintained in AVL trees. This invariant ensures that the height of the tree (length of the longest path from the root to some leaf) is always logarithmic in the number of elements in the tree. Concatenation is implemented as follows:

def concat(xs: Conc[T], ys: Conc[T]) {
  val diff = ys.level - xs.level
  if (math.abs(diff) <= 1) new <>(xs, ys)
  else if (diff < -1) {
    if (xs.left.level >= xs.right.level) {
      val nr = concat(xs.right, ys)
      new <>(xs.left, nr)
    } else {
      val nrr = concat(xs.right.right, ys)
      if (nrr.level == xs.level - 3) {
        val nr = new <>(xs.right.left, nrr)
        new <>(xs.left, nr)
      } else {
        val nl = new <>(xs.left, xs.right.left)
        new <>(nl, nrr)
      }
    }
  } else {
    // symmetric case
  }
}

Amortized O(1) time appends (or prepends) are achieved by introducing a new inner node type called Append, and using it to encode a logarithmic-length list of conc-trees, strictly decreasing in height. Every Append node ap must satisfy the following invariants:

1. Level of ap.left.right is always strictly larger than the level of ap.right.

2. The tree ap.right never contains any Append nodes (i.e. it is in the normalized form, composed only from <>, Single and Empty).

With these invariants, appending is isomorphic to binary number addition—two adjacent trees of the same height can be linked on constant time, with at most a logarithmic number of carry operations. This is illustrated in the following figure, where an element is being appended to a conc-tree that corresponds to a binary number 11:

Conc-tree append operation

This binary number representation is similar to that of purely functional random access lists by Okasaki, with the difference that random access lists require all the trees to be complete binary trees, whereas conc-trees are more relaxed, and only require balanced trees. These more relaxed invariants allow conc-trees to retain logarithmic time concatenation, while random access lists allow only O(n) concatenation.

The following is an implementation of an append method that is worst-case O(log n) time and amortized O(1) time:

case class Append[T](left: Conc[T], right: Conc[T]) extends Conc[T] {
  val level = 1 + math.max(left.level, right.level)
  val size = left.size + right.size
}

private def append[T](xs: Append[T], ys: Conc[T]) =
  if (xs.right.level > ys.level) new Append(xs, ys)
  else {
    val zs = new <>(xs.right, ys)
    xs.left match {
      case ws @ Append(_, _) => append(ws, zs)
      case ws => if (ws.level <= xs.level) concat(ws, zs) else new Append(ws, zs)
    }
  }
}

Conc-tree constructed this way never has more than O(log n) Append nodes, and can be converted back to the normalized form (one using only <>, Single and Empty nodes) in O(log n) time.

A detailed demonstration of these operations can be found in online resources, or in the original conc-tree paper. It was shown that these basic operations can be extended to support worst-case O(1) deque operations, while keeping the O(log n) concatenation time bound, at the cost of increasing the constant factors of all operations.