以通用方式在Scala集合上运行

Question

我写了函数来找到最长的公共子序列(LCS).例如,对于两个字符序列BANANA和ATANA,它返回AANA.实现是递归算法的天真低效适应,但它与此问题的目的无关.

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也可以处理String和Array,那将是很棒的:

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等.

谢谢!

Answer 1

为了清除我的评论,这是你要做的事情(没有给出解释 - 为此,请参阅这个问题的答案).

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()
}

可以在内部函数中直接使用构建器,但是您必须重新编写算法; 实际上,您将项目添加到列表的头部,而构建器添加到结尾.因此,为了保持相同的算法,我们将列表作为中间体.