More efficient than acc.reverse ::: b?

Question

I'm tail optimizing a recursive function. At the end, the result will be acc.reverse ::: b. This is O(n) because of reverse and :::. Is there a better performance way to combine the two lists? Thanks.

Ex. Combine List(3, 2, 1) and List(4, 5, 6) to List(1, 2, 3, 4, 5, 6)

Answer 1

The standard library includes the reverse_::: method for this:

scala> List(3, 2, 1) reverse_::: List(4, 5, 6)
res0: List[Int] = List(1, 2, 3, 4, 5, 6)

This is still O(n), but avoids the separate call to :::.

---

Just for the sake of fun and learning, you could easily implement this as a tail-recursive function:

@tailrec
def reverseConcat[A](lefts: List[A], rights: List[A]): List[A] =
  lefts match {
    case Nil => rights
    case head::tail => reverseConcat(tail, head::rights)
  }

Or using foldLeft:

def reverseConcat[A](lefts: List[A], rights: List[A]): List[A] =
  lefts.foldLeft(rights)((xs, x) => x :: xs)

Note that reverse_::: is not implemented using tail-recursion; it uses a var behind the scenes, so might perform differently.