Concat отсортированный generi c последовательность

Question

Мне нужно объединить две общие c последовательности, я пытался сделать это вот так, но понимаю, что это неправильно. Как мне это сделать правильно? (Мне нужно получить новый Seq, который тоже будет заказан)

object Main extends App{
  val strings = Seq("f", "d", "a")
  val numbers = Seq(1,5,4,2)
  val strings2 = Seq("c", "b");
  val strings3 = strings2.concat(strings)
  println(strings3)
  println(numbers)
}


class Seq[T] private(initialElems: T*) {
  override def toString: String = initialElems.toString

  val elems = initialElems

  def concat(a:Seq[T]) = a.elems ++ this.elems
}

object Seq {
  def apply[T: Ordering](initialElems: T*): Seq[T] = new Seq(initialElems.sorted:_*)
}

Answer 1

Вы не можете объединить два отсортированных массива, используя порядок ++. ++ просто вставьте одну последовательность в конец другой.

Вам нужно реализовать что-то вроде merge операции из алгоритма сортировки слияния и создать новый Seq из объединенных элементов без сортировки . Итак, вам нужно сделать 3 вещи:

1. Реализовать слияние:

   def merge(a: Seq[T], b: Seq[T]): YourElemsType[T] = ???

2. Реализовать новый метод для создания Seq экземпляр без сортировки в object Seq:

   def fromSorted(initialElems: T*): Seq[T] = new Seq(initialElems:_*)

3. Ведь ваш concat может быть реализован как композиция merge и fromSorted:

   def concat(a:Seq[T]): Seq[T] = Seq.fromSorted(merge(this, a))

Подробнее о сортировке слиянием wiki

Answer 2

Вы можете создать функцию, которая будет go через оба списка брать заголовки обоих списков и сравнивать их, а затем добавлять соответствующий заголовок в список результатов. Затем нужно взять следующие две головы и повторять, пока не закончится один список.

Вот пример хвостовой рекурсии:

import scala.annotation.tailrec

def merge[A](a: List[A], b: List[A])(implicit ordering: Ordering[A]): List[A] = {

  @tailrec
  def go(a: List[A], b: List[A], acc: List[A] = Nil): List[A] = {

    (a, b) match {
      case (ax :: as, bx :: bs) => if(ordering.compare(ax, bx) < 0) go(as, bx :: bs, ax :: acc) else go(ax :: as, bs, bx :: acc)
      case (Nil, bs) => acc.reverse ++ bs
      case (as, Nil) => acc.reverse ++ as
      case _ => acc.reverse
    }

  }

  go(a, b)

}

val strings = List("a", "d", "f")
val strings2 = List("b", "c")
merge(strings, strings2) // List(a,b,c,d,e)

Я использовал List вместо Seq. Лучше не использовать Seq, который является очень общим типом, а использовать более конкретные типы коллекций c, которые лучше всего подходят для вашей задачи, например Vector, List, ArraySeq et c.