Условно объединить элементы в последовательности - PullRequest
Новая
       21

Условно объединить элементы в последовательности

0 голосов
/ 27 июня 2018

У меня есть список объектов в последовательности val as = Seq[A]. A выглядит так: 

import java.time.Instant
case class A(t: String, start: Instant, end: Instant)

Теперь я хочу объединить элемент в as условно: всякий раз, когда два последующих, то есть непосредственно смежных, элементы a1 и a2 имеют одинаковое значение для t, они должны быть объединены в одно, как это: 

object A {
  def merge(a1: A, a2: A): A = {
    require(a1.t == a2.t)
    A(a1.t, a1.start, a2.end)
  }
}

Обратите внимание, что элементы, которые непосредственно не преуспевают в другом, никогда не должны объединяться, например ::

Seq(A("a", ...), A("a", ...), A("b", ...), ...) // -> merge the first two elements

Тем не менее: 

Seq(A("a", ...), A("b", ...), A("a", ...), ...) // -> do not merge any elements

Существует аналогичный вопрос для SO , но он объединяет несколько списков, поэтому он не применим к моему случаю.

Мой первый подход: 

as.zip(as.tail)
  .map { 
    case (a1: A, a2: A) if (a1.t == a2.t) => merge(a1, a2)
    case (a1: A, a2: A) => ???
  }

Хотя есть несколько недостатков. Кроме того, я не уверен, что делать во втором случае (то есть оставить a1 и a2 как есть), это также не работает для более чем одного последующего элемента, который должен быть объединен.

Моя интуиция ведет меня больше к foldLeft: 

as.foldLeft(???)(A.merge)

Это решает проблему с несколькими последующими элементами, которые необходимо объединить. Однако он попытается объединить все элементы, что невозможно с моей реализацией merge.

Я мог бы адаптировать merge(), но мне остается неясным, как: если a1.t == a2.t, тип результата должен быть новым A, тогда как в противном случае он должен "возвращать" a1 и a2, поскольку они были.

Мой подход к последней идее заключался в добавлении этих методов в класс A: 

def merge(that: A): (A, Option[A]) =
  if (this.t == that.t)
    (A(t, this.start, that.end), None)
  else
    (this, Some(that))

Но здесь я не могу реально использовать вывод merge() в foldLeft() вызове последовательности as.

Основная проблема заключается в любом подходе: как мне справиться с тем фактом, что иногда (при совпадении t) я хочу добавить один новый A к новой последовательности, тогда как в других случаях мне нужно добавить два элемента.

Я немного растерялся, как решить эту проблему функциональным программированием. Конечно, я мог бы перебрать список as, сохранить те, которые должны быть объединены в новую структуру данных, и сгенерировать их снова. Есть ли лучший способ?

Ответы [ 2 ]

0 голосов
/ 27 июня 2018

Основываясь на ответе RoberMP, если вы используете foldRight для построения List, вы можете использовать сопоставление с шаблоном с оператором cons, который должен быть более эффективным, чем хвостовые операции: 

def merge(sequence: Seq[A]) = {
  sequence.foldRight(List.empty[A]) {
    case (A(t1, x, _), A(t2, _, y) :: list) if t1 == t2 => A(t1, x, y) :: list
    case (other, list) => other :: list
  }
}

Это работает справа налево, так что мы можем использовать :: в сопоставлении, но все равно должен иметь намеченный результат.

0 голосов
/ 27 июня 2018

Я думаю, что foldLeft - это правильный подход, что-то вроде (не проверено): 

as.foldLeft(Seq.empty[A])(merge)

def merge(acc: Seq[A], a: A): Seq[A] = {
  if(acc.isEmpty) Seq(a)
  else if(acc.last.t == a.t) acc.init :+ A(a.t, acc.last.start, a.end)
  else acc :+ a
}

Обратите внимание, что здесь много операций с хвостом, поэтому не знаю, является ли Seq лучшим видом коллекции для этого варианта использования

...