Operating on Scala collections in generic way

Question

I wrote the function to find longest common subsequence (LCS). For example, for two sequences of chars BANANA and ATANA it returns AANA. Implementation is naive inefficient adaptation of recursive algorithm, but it is irrelevant for purpose of this question.

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

I want to refactor this function in most generic way possible. Current implementation works for any types of input sequences, but always returns collection of type List[T]. I want to achieve following behaviour:

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

It would be wonderful if LCS could also handle Strings and Arrays:

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

I believe with help of Scala 2.8 generic collection library it's possible to achieve at least first requirement. Will be glad to see "heavy" machinery like higher-kinded polymorphism, type classes, CanBuildFrom and so on.

Thanks!

Although this is not *exactly* on target, you should be able to accomplish what you want by following the answer to http://stackoverflow.com/questions/5410846 . I recommend that you not use straightforward recursion, however, since you will have to make a ridiculous number of builders to do it that way. A helper function that recursed with builders would do the trick. — Rex Kerr, Apr 20 '11 at 17:39

score 6 · Accepted Answer · edited May 23 '17 at 12:09

To flush out my comment, here is what you'd do (no explanation given--for that, see the answer to 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()
}

It is possible to use a builder directly inside the inner function, but you'd have to rework the algorithm; as it is, you add items to the head of the list, whereas builders add to the end. So, in order to keep the same algorithm, we make a list as an intermediate.

Thanks Rex! Your wonderful [explanation](http://stackoverflow.com/questions/5410846) of "pimping" scala collections is exactly what I wanted to know. MUST READ to everyone interested in integrating own generic methods operating on collections with scala collection framework. — Nikolay Artamonov, Apr 21 '11 at 15:18

score 2 · Answer 2 · answered Apr 20 '11 at 17:26

2

Replacing Seq.empty with a.companion.empty gave me a function with this behavior:

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)

answered Apr 20 '11 at 17:26

Rachel Shallit

2,002
14
15

It's only partial solution. As you can see, compile-time type in every case is Seq[T]. Besides it doesn't work with Strings and Arrays in proper way. See Rex Kerr's answer above, he solved problem completely. – Nikolay Artamonov Apr 21 '11 at 15:25

Operating on Scala collections in generic way

2 Answers2