在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. 獲取可與頭部合併尾部的所有元素，然後將它們合併（可以摺疊使用）到一個新的頭
3. 將新頭放在一個尾巴上，尾巴是通過取出在步驟＃2不能合併的所有東西形成的，然後在步驟＃1將它們重新插入（在尾部爲空的情況下帶有強制性尾部子句）

我認爲這可以更好地作爲Stream。請注意，我假設名單是最初由差異訂購，因爲我使用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 

有Scala中使用ListBuffer，以避免在年底反過來也是另一個很酷的技巧：

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