Unveränderliche Listen mit wahlfreiem Zugriff

In Scala setzt man wegen ihrer unbestrittenen Vorteile sehr oft unveränderliche Datenstrukturen ein. Besonders praktisch sind Listen. Wie schon beim funktionalen Urgestein Lisp bestehen Listen aus „Cons“-Einheiten: Ein Feld für den Wert am Listenanfang („head“), und eine Referenz auf den Rest der Liste („tail“). Wird eine solche Liste als Stack verwendet, also nur „vorne“ gearbeitet, ist alles in Ordnung, und auch, wenn man sowieso alle Listenelemente durchgehen will. Wenn man allerdings auf ein bestimmtes Listenelement zugreifen will, hat man den Aufwand O(n).

Auf den ersten Blick scheint es so, als könne man ein so einfaches und einleuchtendes Konzept nicht großartig verbessern. Aber es gibt doch einen Weg: Chris Okasaki hatte die geniale Idee, Listen und binäre Bäume miteinander zu „kreuzen“, um einen O(log n) Zugriff auf ein Listenelement zu erhalten, wobei das Einfügen oder Abtrennen des Listenkopfs immer noch wie bei normalen Listen den Aufwand O(1) hat.

Wie funktioniert nun die Wunderliste? Angenommen, ich habe sieben Werte, die ich speichern will. Dann kann ich sie in einen binären Baum stecken: Das erste Element in die Wurzel, das zweite links darunter, drei und vier unter die zwei, dann fünf rechts unter der Wurzel und sechs und sieben unter die fünf. Um zu einem beliebigen Element zu gelangen, brauche ich maximal drei Schritte, nicht sieben wie in einer normalen Liste. Aber was ist, wenn der Baum nicht so schön vollständig gefüllt ist? Okasaki-Listen sind Listen von vollständigen binären Bäumen. Weitere Elemente werden als „Einer-Bäume“ vorn an die Liste angehängt, es sei denn, der erste und der zweite Baum der Liste sind gleichgroß, denn dann kann man beide zusammenfassen: Das neue Element wird die Wurzel, der erste Baum zum linken Teilbaum und der zweite zum rechten Teilbaum. An den Bäumen wird also nachträglich nichts mehr geändert (was in einer unveränderlichen Datenstruktur nicht ohne weiteres möglich ist), sondern sie werden nur zu einem größeren Baum kombiniert. Fügen wir nacheinander Elemente zu unsere Siebener-Baum-Liste hinzu (der Listenkopf ist links und die Zahlen geben die Größe der Bäume an):
7
1-7
1-1-7
3-7 <–die beiden Einer-Bäume wurden zusammengefasst
1-3-7
1-1-3-7
3-3-7 <–die beiden Einer-Bäume wurden zusammengefasst
7-7 <–die beiden Dreier-Bäume wurden zusammengefasst
15 <–die beiden Siebener-Bäume wurden zusammengefasst
1-15

Natürlich muss man bei der tail-Methode das ganze rückwärts abspulen, also eventuell Bäume wieder splitten. Um ein Element per Index zu finden, schaut man, ob der Index kleiner als die Größe des ersten Baums ist, denn dann kann er es uns feundlicherweise heraussuchen. Falls nicht, frage ich rekursiv meine Restliste (wobei natürlich der Index um die Größe des ersten Baums vermindert werden muss). Es läßt sich zeigen, dass diese Abfrage genau wie die Abfrage in einem Binärbaum den Aufwand O(log n) hat. Selbst wenn wir in der längsten Liste (1-1-3-7, also 12 Elemente) in unserem Beispiel nach dem letzen Element fragen, haben wir nur 6 Abfragen: 3 um bis zum letzen Baum zu gelangen, und 3 im Siebener-Baum selbst.

Falls diese Erklärungen nicht so ganz einleuchtend sind, empfehle ich, es sich vom "Erfinder" persönlich erklären zu lassen: Purely Functional Random-Access Lists. Die Bilder dort helfen beim Verständnis.

Hier ist eine wirklich rudimentäre (und kaum getestete) Implementierung:

object RAList {

  val EMPTY = new RAList[Nothing](None)

  abstract class RANode[+A] {
    def apply(index: Int): A
  }

  object RANil extends RANode[Nothing] {
    override def apply(index: Int) = error("no such element")
  }

  class RATree[+A](val size: Int, val a: A, val left: RANode[A], val right: RANode[A]) 
          extends RANode[A] {
    override def apply(index: Int) = index match {
      case 0 => a
      case s if s <= (size - 1) / 2 => left(index - 1)
      case s if s > (size - 1) / 2 => right(index - (size + 1) / 2)
      case _ => error("no such element")
    }
  }
}

import RAList._

class RAList[+A] private(data: Option[(RATree[A], RAList[A])]) {

  private def this(left: RATree[A], right: RAList[A]) = this(Some(left, right))

  def isEmpty = data == None

  private def hd = data.get._1
  private def tl = data.get._2

  def apply(index: Int): Option[A] = if (isEmpty) None
  else if (hd.size <= index) tl(index - hd.size)
  else Some(hd(index))

  def head: Option[A] = data.map(_._1.a)

  def tail: Option[RAList[A]] = if (isEmpty) None
  else (hd.left, hd.right) match {
    case (l: RATree[A], r: RATree[A]) => Some(new RAList(l, new RAList(r, tl)))
    case _ => Some(tl)
  }

  def :: [B >: A](a : B): RAList[B] = 
    if (! isEmpty && ! tl.isEmpty && hd.size == tl.hd.size) new RAList(
      new RATree(2*hd.size + 1, a, hd, tl.hd), tl.tl)
  else new RAList(new RATree(1, a, RANil, RANil), this)

  def size: Int = if (isEmpty) 0 else hd.size + tl.size
}

Wie man sieht fehlen noch viele Methoden, und ich habe auch darauf verzichtet, RAList irgendwie in die Scala-Collections einzupassen („diese Übung sei dem geneigten Leser überlassen“). Eine RAList konstruiert man wie eine normale Liste, nur heißt das Ende EMPTY statt Nil:

import RAList._

val list = 1 :: 2 :: 3 :: 4 :: EMPTY

for (i <- 0 to 5) println(list(i))
//--> Some(1)
//--> Some(2)
//--> Some(3)
//--> Some(4)
//--> None
//--> None

println(list.head)
//--> Some(1)

println(list.tail.get.tail.get.head)
//--> Some(3)

Debasish Gosh hat ebenfalls einen Blog-Beitrag über Okasakis Listen geschrieben, und nicht nur das, sondern auch gleich ein Google-Code-Projekt für diese und andere Datenstrukturen eingerichtet. Ich vermute stark, dass sein Code besser als meine kleine Spielimplementierung ist.