Работа с коллекциями Scala в общем виде - PullRequest
Новая
       29

Работа с коллекциями Scala в общем виде

7 голосов
/ 20 апреля 2011

Я написал функцию для поиска самой длинной общей подпоследовательности (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 <i>Seq</i>s...

Было бы замечательно, если бы LCS мог также обрабатывать String s и 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')

Я считаю, что с помощью универсальной библиотеки коллекций Scala 2.8 можно выполнить хотя бы первое требование.Будем рады видеть "тяжелые" машины, такие как полиморфизм с более высоким родом, классы типов, CanBuildFrom и т. Д.

Спасибо!

Ответы [ 2 ]

5 голосов
/ 20 апреля 2011

Чтобы очистить мой комментарий, вот что вы должны сделать (объяснение не дано - для этого см. Ответ на этот вопрос ). 

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

Этоможно использовать конструктор непосредственно внутри внутренней функции, но вам придется переделать алгоритм;как таковой, вы добавляете элементы в начало списка, в то время как строители добавляют в конец.Итак, чтобы сохранить тот же алгоритм, мы составляем список в качестве промежуточного звена.

2 голосов
/ 20 апреля 2011

Замена Seq.empty на a.companion.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)
...