Geek Answers Handbook

Work in Scala collections in general

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

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 reorganize this function in the most general way . The current implementation works for any type of input sequence, but always returns a collection of type List [T]. I want to achieve the following behavior:

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

It would be great if LCS could handle String s and Array s:

  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 that using the Scala 2.8 collection library you can achieve at least the first requirement. We will be happy to see a “heavy” machine, such as a higher grade polymorphism, class classes, CanBuildFrom, etc.

Thanks!

+7
source share
2 answers

To clear my comment, here is what you would do (there was no explanation, for this, 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() }

You can use the constructor directly inside the internal function, but you have to rework the algorithm; Be that as it may, you add items to the list title, while builders add to the end. So, to keep the same algorithm, we make the list intermediate.

+5
source

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)
+2
source

More articles:


All Articles