Concatenate lists in constant time in scala?

Question

In Scala, is there a built-in function or external library for concatenating two lists (or arrays, or vectors, or listbuffers, etc) in constant time? Such an operation would presumably destroy / mutate the two original lists. All the functions I see for concatenating lists run in linear time, as far as I can tell.

Thanks much.

How could you possibly copy N (i.e. a variable number of) items in constant time? — , Jun 11 '11 at 13:00
@delnan: He didn't ask to copy the values. For example, you can join two binary trees in constant time by creating a new root with the two trees as the child nodes. (You'd have to see 'list' with the loose meaning of 'sequence' in this case.) — kassens, Jun 11 '11 at 13:32
See if you can make of use of a DList. See http://stackoverflow.com/questions/3352418/what-is-a-dlist. Eventually you'll still need a linear operation to construct the final list, but it's probably the closest to something readily available. — huynhjl, Jun 11 '11 at 15:41

axel22 · Accepted Answer · 2011-06-11T17:31:45.520

13

There is the UnrolledBuffer which has the concat method taking another UnrolledBuffer and returning their concatenation in O(1). It is destructive to the argument buffer - the second buffer will be empty after this calling this method.

edited Jun 11 '11 at 17:31

answered Jun 11 '11 at 15:44

axel22

32,045
9
125
137

score 2 · Answer 2 · answered Jun 11 '11 at 16:13

The classic (going back to at least Hughes '84) approach in functional languages to solve constant-time append in is via "difference lists", where appending to the list is encoded as function composition.

Here's a sketch in Haskell:

newtype DList a = DL { unDL :: [a] -> [a] }

So a DList is a function from lists to lists. Some introduction forms:

-- The empty list is the identity function
empty       = DL id    

-- Singletons are the compositions of the cons function
singleton   = DL . (:)

-- Appending two lists is just composition
append xs ys = DL (unDL xs . unDL ys)

The full implementation is on Hackage, and should be trivial to translate to Scala.

I believe scalaz has a DList implementation. http://code.google.com/p/scalaz/ though I can't find it on github. — huynhjl, Jun 11 '11 at 16:43

score 1 · Answer 3 · answered Jun 11 '11 at 14:25

I was thinking that a DoubleLinkedList could offer a constant-time append, since you could join the end of one list to the beginning of another without having to traverse either one.

However, neither the scala.collections.mutable.DoubleLinkedList or java.util.List work that way.

The reason is probably that it would mean a.append(b) would modify both a and b, which would be unexpected.

score 0 · Answer 4 · answered Jun 11 '11 at 14:14

Here is a simple immutable data structure that supports constant time concatenation. It just shows that it is possible, but is not intended for practical use. The items implementation to retrieve the elements has a pretty bad run-time and could easily be improved by walking the tree with an iterator.

I'm wondering if there are any better data structures?

sealed abstract class Tree[+T] {
  def items: List[T]
  def append[U >: T](v: U): Tree[U] = this append Leave(v)
  def append[U >: T](other: Tree[U]) = Node(this, other)
}

case class Node[+T](val left: Tree[T], val right: Tree[T]) extends Tree[T] {
  def items = left.items ++ right.items
}

case class Leave[+T](val value: T) extends Tree[T] {
  def items = List(value)
}

case object EmptyTree extends Tree[Nothing] {
  def items = Nil
}

object ConstantTimeConcatenation {
  def main(args: Array[String]) {
    val first = EmptyTree append 1 append 2 append 3
    val second = EmptyTree append 4 append 5
    val both = first append second // runs in linear time
    println(both.items)
  }
}

Concatenate lists in constant time in scala?

4 Answers4