Buffer type with purely functional API, using a mutable buffer and cheap copy-on-write scheme

buffer.scala

import java.util.concurrent.atomic._
import collection.mutable.ArrayBuffer

/**
 * Buffer type with purely functional API, using mutable
 * `ArrayBuffer` and cheap copy-on-write scheme.
 * Idea described by Bryan O'Sullivan in http://www.serpentine.com/blog/2014/05/31/attoparsec/
 */
class Buffer[A](id: AtomicLong, stamp: Long, values: ArrayBuffer[A], size: Int) {
  
  /** Snoc a value onto the end of this `Buffer`, possibly using (unobservable) mutation of `values`! */
  def :+(a: A): Buffer[A] =
    if (id.compareAndSet(stamp, stamp+1)) { // threads race to be able to mutably update 'values'
      values += a
      new Buffer(id, stamp+1, values, size+1)
    }
    else // losers are forced to make a copy of the buffer
      new Buffer(new AtomicLong(0), 0, ArrayBuffer.empty[A] ++ values.take(size) :+ a, size + 1)

  def toSeq: Seq[A] = values.view.take(size)

  override def toString = "Buffer(" ++ toSeq.mkString(", ") ++ ")"
}

object Buffer {
  def empty[A]: Buffer[A] = new Buffer(new AtomicLong(0), 0, ArrayBuffer.empty[A], 0)
}

Interestingly, this idea can be extended to deal with a large number of mutable APIs. Our only requirement is that the mutation be 'append-only'. That is, once a value is set, it must never be updated again. For instance, we can have a purely functional Map data type which updates values in place, subject only to the requirement that we never overwrite the value of a key (or if we need to, we need to then make a copy).

This seems to relate to the limited form of mutation provided by use of laziness, except that unlike laziness, we don't need to construct the whole computation 'in advance' to take advantage of it.