以通用方式對Scala集合進行操作

我編寫了查找longest common subsequence（LCS）的函數。例如，對於字符BANANA和ATANA的兩個序列，它返回AANA。實現是遞歸算法的天真無效的適應，但這與這個問題的目的無關。以通用方式對Scala集合進行操作

def LCS[T](a: Seq[T], b: Seq[T]): Seq[T] = { 
    if (a.isEmpty || b.isEmpty) 
     Seq.empty 
    else if (a.head == b.head) 
     a.head +: LCS(a.tail, b.tail) 
    else { 
     val case1 = LCS(a.tail, b) 
     val case2 = LCS(a, b.tail) 
     if (case1.length > case2.length) case1 else case2 
    } 
}

我想在最通用的方式可能重構這一功能。當前實現適用於任何類型的輸入序列，但始終返回List [T]類型的集合。我想實現以下行爲：

 
LCS(List('B','A','N','A','N','A'), List('A','T','A','N','A')) -> List('A','A','N','A') 
LCS(Vector('B','A','N','A','N','A'), Vector('A','T','A','N','A')) -> Vector('A','A','N','A') 

...and so on for all other Seqs...

這將是美好的，如果LCS還可以處理字符串 S和陣列 S：

 
LCS("BANANA", "ATANA") -> "AANA" 
LCS(Array('B','A','N','A','N','A'), Array('A','T','A','N','A')) -> Array('A','A','N','A')

相信使用Scala 2.8泛型集合庫的幫助至少可以達到第一個要求。很高興看到「重型」機器，如更高級的多態，類型類，CanBuildFrom等等。

謝謝！

來源

2011-04-20 Nikolay Artamonov

雖然這不是*完全*目標，你應該能夠通過遵循http://stackoverflow.com/questions/5410846的答案來完成你想要的。我建議你不要使用簡單的遞歸，但是，因爲你必須讓一些荒謬的建設者這樣做。與建設者一起遞歸的幫助函數可以解決這個問題。 – 2011-04-20 17:39:10

沖洗掉我的意見，這裏是你會怎麼做（沒有給出的解釋 - 對於這一點，一看便知，以this question ）。

def LCS[A,C](a: C, b: C)(
    implicit c2i: C => Iterable[A], cbf: collection.generic.CanBuildFrom[C,A,C] 
): C = { 
    val builder = cbf() 
    def ListLCS(a: Iterable[A], b: Iterable[A]): List[A] = { 
    if (a.isEmpty || b.isEmpty) Nil 
    else if (a.head==b.head) a.head :: ListLCS(a.tail,b) 
    else { 
     val case1 = ListLCS(a.tail, b) 
     val case2 = ListLCS(a, b.tail) 
     if (case1.length > case2.length) case1 else case2 
    } 
    } 
    builder ++= ListLCS(c2i(a), c2i(b)) 
    builder.result() 
}

可以直接在內部函數中使用構建器，但是您必須重新修改算法;實際上，您可以將項目添加到列表的頭部，而建設者將添加到最後。所以，爲了保持相同的算法，我們將列表作爲中間值。

來源

2011-04-20 18:01:32

感謝雷克斯！你的精彩[解釋]（http://stackoverflow.com/questions/5410846）「pimping」scala系列正是我想知道的。必須向所有感興趣的人集成使用scala集合框架來運行集合的自己的泛型方法。 – 2011-04-21 15:18:36

與a.companion.empty更換Seq.empty給了我一個功能，這種行爲：

scala> LCS(Vector(1, 2, 1, 2, 3), Vector(1, 1, 3)) 
res3: Seq[Int] = Vector(1, 1, 3) 

scala> LCS(List(1, 2, 1, 2, 3), List(1, 1, 3)) 
res4: Seq[Int] = List(1, 1, 3) 

scala> LCS("BANANA", "ANA")      
res5: Seq[Char] = Vector(A, N, A) 

scala> LCS(Array(1, 2, 1, 2, 3), Array(1, 1, 3)) 
res6: Seq[Int] = ArrayBuffer(1, 1, 3)

來源

2011-04-20 17:26:31

這只是部分解決方案。正如你所看到的，每種情況下的編譯時類型都是Seq [T]。除此之外，它並不適用於Strings和Arrays。請參閱上面的Rex Kerr的回答，他完全解決了問題。 – 2011-04-21 15:25:02

以通用方式對Scala集合進行操作

回答

相關問題