CatSeq: O(1) concatenation of sequences. What is this called?

catseq.scala

import scala.collection.immutable.Seq
object CatSeq {
  val empty: CatSeq[Nothing] = CatSeq[Nothing](0, Seq.empty, Seq.empty)
}
/** Data structure to do O(1) concatenation of lists
 */
case class CatSeq[+T](leftLen: Int, left: Seq[T], right: Seq[T]) extends Seq[T] {
  override def isEmpty = left.isEmpty && right.isEmpty
  override def head = if(left.isEmpty) right.head else left.head
  override def tail = if(left.isEmpty) right.tail else CatSeq(leftLen - 1, left.tail, right)

  def iterator = // go through this trouble to avoid calling right until the last minute.
    new Iterator[T] {
      var isLeft = true
      var iter = left.iterator
      def hasNext = iter.hasNext || (isLeft && {
        iter = right.iterator
        isLeft = false
        iter.hasNext
      })

      def next = {
        val res = iter.next
        if(!iter.hasNext && isLeft) {
          iter = right.iterator
          isLeft = false
        }
        res
      }
    }

  def apply(idx: Int) = if(idx < leftLen) left(idx) else right(idx - leftLen)

  lazy val length = leftLen + right.length

  // TODO: jumping through the CanBuildFrom to make this the default
  // also, could be optimized when that is a CatSeq
  def concat[U>:T](that: Seq[U]): CatSeq[U] = CatSeq(length, this, that)
  override def toString = "CatSeq(%s, %s)".format(left, right)
}

val example = CatSeq.empty concat (List(1, 2)) concat (List(3, 4))
println("%s".format(example))

// use the iterator
example.foreach(println(_))