CODEWITHSUNDEEP
listscaladata-structuresconcatenation
Jeff
Jeff

Reputation: 1242

Concatenate lists in constant time in scala?

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.

Upvotes: 12

Views: 2851

Answers (4)

axel22
axel22

Reputation: 32335

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.

Upvotes: 13

Don Stewart
Don Stewart

Reputation: 137957

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.

Upvotes: 2

Andrew McGuinness
Andrew McGuinness

Reputation: 2147

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.

Upvotes: 1

kassens
kassens

Reputation: 4475

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)
  }
}

Upvotes: 0

Related Questions