λ Tony's Blog λ

List with O(1) cons and snoc in Scala

Posted on February 20, 2011

A pseudo difference list with constant time prepend (cons) and append (snoc).

There is an efficiency issue with respect to Scala’s TCO implementation (making this data structure untenable?), however, I have forgotten the details of that.

In any case, a finger-tree is often more appropriate, but it would be nice to revive the Endo[List[A]]!

sealed trait DiffList[A] {
  val endo: List[A] => List[A]

  import DiffList._

  // cons O(1)
  def <::(a: A): DiffList[A] = new DiffList[A] {
    val endo = (z: List[A]) => a :: DiffList.this.endo(z)
  }

  // snoc O(1)
  def ::>(a: A): DiffList[A] = new DiffList[A] {
    val endo = (z: List[A]) => DiffList.this.endo(a :: z)
  }

  // append O(1)
  def :::>(a: DiffList[A]): DiffList[A] = new DiffList[A] {
    val endo = (z: List[A]) => DiffList.this.endo(a.endo(z))
  }

  // O(n)
  def toList = endo(Nil)
}

object DiffList {
  def empty[A]: DiffList[A] = new DiffList[A] {
    val endo = (z: List[A]) => z
  }

  def single[A](a: A): DiffList[A] = a <:: empty[A]
}