scala - 递归累积集合元素

Question

我有一个具有整数范围的元素集合，例如

case class Element(id: Int, from: Int, to: Int)
val elementColl: Traversable[Element]

我想将它们积累到

case class ElementAcc(ids: List[Int], from: Int, to: Int)

根据以下算法:

1. 从我的 elementColl 中取出一个 Element 并用它创建一个新的 ElementsAcc，它与 具有相同的 from/to元素已被采用。
2. 迭代 elementColl 中的剩余元素，以查找与 ElementAcc 具有重叠整数范围的 Element。
3. 如果找到，请将其添加到 ElementAcc 中，并扩展 ElementAcc 的整数范围以包含新 Element 的范围<
4. 如果没有找到，则对 elementColl 中尚未分配给 ElementAcc 的剩余元素重复上述过程

这应该会导致 ElementAcc 的集合。虽然仅递归地将元素添加到累加器似乎很容易，但我不知道如何处理 elementColl 的缩小大小，以便我不会将相同的 Element 添加到多个 ElementAcc 的

编辑:我认为我不清楚范围的扩展。让我通过一个例子来澄清这一点:

我的累加器当前的范围为 1 到 5。范围为 6 到 8 的元素与累加器范围不重叠，因此不会被包含在内。范围为 4 到 7 的元素确实重叠，将被包含在内，并且生成的累加器的范围为 1 到 7。

Answer 1

我会这样:

1) 编写一个接受 ElementAcc 和 Element 并返回 ElementAcc 的函数。 该函数如下所示:

def extend(acc: ElementAcc, e: Element): ElementAcc = {
  if(acc.from <= e.from && e.from <= acc.to)
    ElementAcc(e.id :: acc.ids, acc.from, math.max(acc.to, e.to))
  else if (acc.from <= e.to && e.to <= acc.to)
    ElementAcc(e.id :: acc.ids, math.min(acc.from, e.from), acc.to)
  else acc
}

foldLeft 在累积对象时通常是很好的解决方案。 它需要累加器的初始值和一个接受累加器和元素并返回累加器的函数。然后它会累积可遍历的所有元素。

编辑:

2) 要在不同的列表上累积，您必须创建另一个函数来组合 List[ElementAcc] 和 Element :

def overlap(acc: ElementAcc, e: Element): Boolean = {
  (acc.from <= e.from && e.from <= acc.to) || (acc.from <= e.to && e.to <= acc.to)
} 

def dispatch(accList: List[ElementAcc], e: Element): List[ElementAcc] = accList match {
  case Nil => List(ElementAcc(List(e.id), e.from, e.to))
  case acc :: tail =>
    if (overlap(acc, e)) extend(acc, e) :: tail
    else acc :: dispatch(tail, e)
}

3)它与foldLeft一起使用:

val a = Element(0, 0, 5)
val b = Element(1, 3, 8)
val c = Element(2, 20, 30)
val sorted = List(a, b, c).foldLeft(List[ElementAcc]())(dispatch)

sorted: List[ElementAcc] = List(ElementAcc(List(1, 0),0,8), ElementAcc(List(2),20,30))