比acc.reverse更高效::: b？

Question

我是尾巴優化遞歸函數。最後，結果將是acc.reverse ::: b。由於reverse和:::，這是O（n）。是否有更好的性能方式來組合這兩個列表？謝謝。

Ex。結合List(3, 2, 1)和List(4, 5, 6)到List(1, 2, 3, 4, 5, 6)

Answer 1

標準庫包括用於此reverse_:::方法：

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

這仍然是O（n），但避免了對:::單獨呼叫。

---

只是爲了樂趣和學習的份上，你可以很容易地實現這是一個尾遞歸函數：

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

或者使用foldLeft：

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

注意reverse_:::是沒有使用尾遞歸實現;它在幕後使用var，所以可能會有不同的表現。