在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