Clever Geek Handbook

More efficient than acc.reverse: b?

I am a tail optimizing recursive function. In the end, the result will be acc.reverse ::: b

. It's O (n) because of reverse

and :::

. Is there a better way to combine two lists? Thank.

Ex. Combine List(3, 2, 1)

and List(4, 5, 6)

withList(1, 2, 3, 4, 5, 6)

+3


source to share


1 answer


The standard library includes a method reverse_:::

for this:

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

It's still O (n), but avoids a separate call :::

.

Just for fun and learning, you can easily implement this as a tail recursion 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 this is reverse_:::

not implemented with tail-recursion; it uses var

behind the scenes, so it might work differently.

+5


source






More articles:


All Articles