Общая работа с коллекциями Scala

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

Спасибо!


types generics scala generic-programming scala-collections
person Nikolay Artamonov    schedule 20.04.2011    source источник
comment
Хотя это не точно по цели, вы сможете добиться желаемого, следуя ответу на stackoverflow.com / questions / 5410846. Однако я рекомендую вам не использовать прямую рекурсию, поскольку вам придется создать смехотворное количество конструкторов, чтобы сделать это таким образом. Вспомогательная функция, рекурсивная со строителями, сделает свое дело.   -  person Rex Kerr    schedule 20.04.2011

Ответы (2)


arrow_upward
6
arrow_downward

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

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

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

person Rex Kerr    schedule 20.04.2011
comment
Спасибо, Рекс! Ваше замечательное объяснение использования коллекций scala - это именно то, что я хотел знать. ДОЛЖЕН ПРОЧИТАТЬСЯ всем, кто заинтересован в интеграции собственных универсальных методов, работающих с коллекциями, с каркасом коллекций scala. - person Nikolay Artamonov; 21.04.2011

arrow_upward
2
arrow_downward

Замена 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)
person Rachel Shallit    schedule 20.04.2011
comment
Это только частичное решение. Как видите, типом времени компиляции в каждом случае является Seq [T]. Кроме того, он не работает должным образом со строками и массивами. См. Ответ Рекса Керра выше, он полностью решил проблему. - person Nikolay Artamonov; 21.04.2011