在Scala中合併兩個迭代器

Question

我想寫一個merge方法，它需要兩個迭代器並將它們合併在一起。 （也許合併不是描述我想要的最好的詞，但爲了這個問題，它是無關緊要的）。我想這個方法是通用的，可以處理不同的具體迭代。

例如，merge(Set(1,2), Set(2,3))應該返回Set(1,2,3)和 merge(List(1,2), List(2,3))應該返回List(1, 2, 2, 3)。我做了以下天真的嘗試，但編譯器正在抱怨res的類型：它是Iterable[Any]而不是A。

def merge[A <: Iterable[_]](first: A, second: A): A = { 
    val res = first ++ second 
    res 
} 

我該如何解決這個編譯錯誤？ （我更感興趣的是瞭解如何實現這樣的功能，而不是它會爲我出庫，所以爲什麼我的代碼無法正常工作的解釋非常讚賞。）

Answer 1

簽名複製讓我們先從爲什麼你代碼不起作用。首先，你不小心使用了縮寫語法來代替existential type，而不是實際使用綁定在更高版本類型上的類型。

​​

即使修復它雖然不完全得到你想要的。

def merge[A, S[T] <: Iterable[T]](first: S[A], second: S[A]): S[A] = { 
    first ++ second // CanBuildFrom errors :(
} 

這是因爲++不使用類型限制來實現其多態，它採用隱式CanBuildFrom[From, Elem, To]。 CanBuildFrom負責給予適當的Builder[Elem, To]，這是我們用它來建立我們需要的類型的集合一個可變的緩衝區。

所以這意味着我們將不得不給它CanBuildFrom它的願望，一切都會正常工作？

import collection.generic.CanBuildFrom 

// Cannot construct a collection of type S[A] with elements of type A 
// based on a collection of type Iterable[A] 
merge0[A, S[T] <: Iterable[T], That](x: S[A], y: S[A]) 
    (implicit bf: CanBuildFrom[S[A], A, S[A]]): S[A] = x.++[A, S[A]](y) 

都能跟得上:(。

我已經添加了額外的類型註釋++，使編譯器錯誤較多有關。這是什麼告訴我們是因爲我們還沒有明確覆蓋Iterable的++與我們自己對我們的任意S，我們使用Iterable的實現它，這只是恰巧採取從Iterable建立一個隱含的CanBuildFrom的我們S。

這是偶然@ChrisMartin遇到了這個問題（對於他的回答，這整件事情真的是一個冗長的評論）。

不幸的是，Scala不提供這樣的CanBuildFrom，所以看起來我們將不得不手動使用CanBuildFrom。

如此下來的兔子洞，我們去...

讓我們開始通過注意到++其實實際上TraversableLike最初定義，所以我們可以讓我們的自定義merge有點更普遍。

def merge[A, S[T] <: TraversableLike[T, S[T]], That](it: S[A], that: TraversableOnce[A]) 
    (implicit bf: CanBuildFrom[S[A], A, That]): That = ??? 

現在讓我們實際實現該簽名。

import collection.mutable.Builder 

def merge[A, S[T] <: TraversableLike[T, S[T]], That](it: S[A], that: TraversableOnce[A]) 
    (implicit bf: CanBuildFrom[S[A], A, That]): That= { 
    // Getting our mutable buffer from CanBuildFrom 
    val builder: Builder[A, That] = bf() 
    builder ++= it 
    builder ++= that 
    builder.result() 
    } 

請注意，我已經改變了GenTraversableOnce[B] *到TraversableOnce[B] **。這是因爲使Builder的++=工作的唯一方法是進行順序訪問***。這就是CanBuildFrom。它爲您提供了一個可變緩衝區，您可以使用所需的所有值進行填充，然後將緩衝區轉換爲您想要的輸出集合與result。

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

scala> merge(Set(1, 2, 3), Set(2, 3, 4)) 
res1: scala.collection.immutable.Set[Int] = Set(1, 2, 3, 4) 

scala> merge(List(1, 2, 3), Set(1, 2, 3)) 
res2: List[Int] = List(1, 2, 3, 1, 2, 3) 

scala> merge(Set(1, 2, 3), List(1, 2, 3)) // Not the same behavior :(
res3: scala.collection.immutable.Set[Int] = Set(1, 2, 3) 

總之，CanBuildFrom機器讓你構建代碼的事實是，我們常常希望Scala的集合的繼承圖的不同分支之間自動轉換的交易，但它是在一些複雜的成本和偶爾會有不直觀的行爲。權衡相應的權衡。

腳註：

*「廣義」集合了，我們可以「遍歷」至少「一次」，但也許並不多，一些爲了它可能會或可能不會是連續的，例如也許平行。

**與GenTraversableOnce相同，但不是「常規」，因爲它保證順序訪問。

*** TraversableLike通過在內部強制調用seqGenTraversableOnce來解決這個問題，但是我覺得當他們可能有其他預期的時候，這就是欺騙人們的並行性。強制呼叫者決定是否放棄其並行性;不要爲了他們而隱瞞。

Answer 2

初步地，這裏有必要進口對於所有在這個答案的代碼：

import collection.GenTraversableOnce 
import collection.generic.CanBuildFrom 

開始通過看the API doc看到方法簽名Iterable.++（請注意，對於大多數集合are wrong API文檔，你需要點擊「全部簽名」看真實類型）：

def ++[B >: A, That](that: GenTraversableOnce[B]) 
    (implicit bf: CanBuildFrom[Iterable[A], B, That]): That 

從那裏，你可以做一個簡單的轉換，從一個實例方法給一個函數：

def merge[A, B >: A, That](it: Iterable[A], that: GenTraversableOnce[B]) 
    (implicit bf: CanBuildFrom[Iterable[A], B, That]): That = it ++ that 

打破下來：

• [A, B >: A, That] — Iterable有一個類型參數A和++有2個型參數B和That，因此所得到的函數具有所有三種類型參數A，B和That
• it: Iterable[A] —的方法屬於Iterable[A]，所以我們所做的第一個值參數
• that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[Iterable[A], B, That]): That —其餘參數和類型的約束，直接從++