Объединение элементов в списке Scala

Question

Я пытаюсь перенести следующий фрагмент кода Java в Scala. Он берет список MyColor объектов и объединяет все те, которые находятся в дельте друг друга. Это похоже на проблему, которую можно элегантно решить, используя некоторые функциональные возможности Scala. Любые советы?

List<MyColor> mergedColors = ...;
MyColor lastColor = null;
for(Color aColor : lotsOfColors) {
  if(lastColor != null) {
    if(lastColor.diff(aColor) < delta) {
      lastColor.merge(aColor);
      continue;
    }
  }
  lastColor = aColor;
  mergedColors.add(aColor);
}

Answer 1

Вот еще одно рекурсивное решение, которое имеет преимущество в том, что является хвостовой рекурсией (поэтому нет шансов переполнения стека), но с другой стороны делает много манипуляций со списком, поэтому может быть расточительным. Призыв к обратному выводу в конце состоит в том, чтобы вернуть выходные цвета в порядок ввода, но в этом нет необходимости, если вы не заботитесь о порядке.

def processColors(colors: List[Color], delta: Double): List[Color] = {
  def process(in: List[Color], accum: List[Color]): List[Color] = in match {
      case x :: y :: ys if x.diff(y) < delta => process( x.merge(y) :: ys, accum )
      case x :: xs                           => process( xs, x :: accum )
      case Nil                               => accum
    }

  process(colors, Nil).reverse
}

Answer 2

Я предполагаю, что ваши цвета расположены в списке так, что цвета "близко" в цветовом пространстве (то есть с низким значением diff) находятся рядом в списке. Тогда я бы использовал фолд:

val unmergedColors: List[MyColor] = ...
val mergedColors = (Nil:List[MyColor] /: unmergedColors)( (list,c) => {
  list match {
    case oldc :: rest if (oldc.diff(c) < delta) => oldc.merge(c) :: rest
    case _ => c :: list
  }
}).reverse

Здесь, я предполагаю, что merge изменено, чтобы вернуть новый цвет, который является слиянием двух предыдущих (так что ваши цвета неизменны); в противном случае вы бы oldc.merge(c) ; list в первом случае.

Посмотрим, что здесь происходит.

Начнем с пустого списка новых цветов. Тогда для каждого цвета в неопубликованном списке у нас есть два случая:

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

Наконец, так как мы используем их как операции со стеком, мы заканчиваем, переворачивая список.

Answer 3

Мне кажется, что эта проблема может привести к различным вопросам о том, в чем именно заключается проблема.Например:

• , если решение будет инвариантным при начальном упорядочении вашего списка
• , если различие будет выполнено для слитых или без слияния значений по ходу дела

Но вот что-то забавное, которое использует рекурсию (хотя это не хвостовая рекурсия это, конечно, можно сделать так), например:

type C = MyColor
type Cs = list[C]

def merge(val delta: Double, diff: (C, C) => Double, colors: Cs) : Cs = {

   def _mergeHeadAndGTDiff(head: C, tail: Cs) : Cs = { 
      val (toMerge, rest) = tail.span(diff(head, _) < delta) 
      val newHead = (head :: toMerge).reduceLeft(_ merge _)
      newHead :: (rest match {
           case Nil     => Nil
           case x :: xs => _mergeHeadAndGTDiff(newHead, xs) 
        })          
   }

   colors match {
      case Nil     => Nil
      case x :: xs => _mergeHeadAndGTDiff(x, xs)
   }
}

Решение выглядит следующим образом:

1. Возьмите голову
2. Получите все элементы хвоста, которые можно объединить с головой, а затем объедините их (можноиспользуйте fold) в новую головку
3. заключает новую головку в хвост, который формируется путем взятия всего, что не могло быть объединено на шаге № 2, а затем подключения их обратно на шаге № 1 (с обязательным терминаломпредложение в случае, если хвост пуст)

Это работает лучше, как Stream, я думаю.Обратите внимание, что я предполагаю, что список был изначально упорядочен по diff , потому что я использую span.Это было бы ненужным, если бы его заменили на partition.

Answer 4

Я бы попробовал сложить:

def merge(lotsOfColor: List[MyColor], delta: Double): List[MyColor] =
  lotsOfColor.tail.foldLeft((List(lotsOfColor.head), lotsOfColor.head)) {
    case ((mergedColors, lastColor), aColor) if (lastColor diff aColor) < delta =>
      (mergedColors, lastColor merge aColor)
    case ((mergedColors, _), aColor) => (aColor :: mergedColors, aColor)
  }._1.reverse

Или, немного другой,

def merge(lotsOfColor: List[MyColor], delta: Double): List[MyColor] =
  lotsOfColor.tail.foldLeft((List(lotsOfColor.head), lotsOfColor.head)) {
    case ((mergedColors, lastColor), aColor) =>
      if ((lastColor diff aColor) < delta)
        (mergedColors, lastColor merge aColor)
      else
        (aColor :: mergedColors, aColor)
  }._1.reverse

Есть еще один крутой прием, использующий ListBuffer в Scala, чтобы избежать обратного в конце:

import scala.collection.mutable.ListBuffer
def merge(lotsOfColor: List[MyColor], delta: Double): List[MyColor] =
  lotsOfColor.tail.foldLeft((ListBuffer(lotsOfColor.head), lotsOfColor.head)) {
    case ((mergedColors, lastColor), aColor) if (lastColor diff aColor) < delta =>
      (mergedColors, lastColor merge aColor)
    case ((mergedColors, _), aColor) => 
      mergedColors += aColor
      (mergedColors, aColor)
  }._1.toList