在Scala中，当两个元素不应该变成一个元素时，如何折叠

Question

我有一个Pair的列表，它表示具有开始索引和结束索引的行。类型为(Int,Int)，由两个整数组成的元组。

现在我想把任何相互接触的线连在一起，例如。

List((1,5)，(6,10)，(12,20))应该转换为List((1,10)，(12,20))，因为行(1,5)触及行(6,10)。只有相邻的线才会连接成一条线。

我的第一个想法是在列表上使用foldleft，问题是foldleft需要将两个元素转换成一个元素，最终只输出一个(Int,Int)。

第二个想法是递归解决方案，我做了程序，但这似乎不是最好的或最简单的想法。我们取两个元素，有时输出一个或两个元素，这种想法似乎应该应用于许多情况，就像foldleft一样。

有什么通用的方法或模式或库来解决这个问题吗?

---

单线在一维平面上，它不是一个x,y点。(Int,Int)是一维平面上的起点和终点。

澄清触摸的定义。列表中的所有行都不重叠，这是一个前提条件，即(1,3)和(2,4)不能存在于列表中，因为它们重叠。

(1,3)，(4,5)可以存在于列表中，因为它们不重叠。

(1,3)，(4,5)不接触，因为3和4之间的距离正好是1。

对于问题((1,5)，(6,10)，(6,12)，(13,15))中给出的列表，这是一个无效列表，因为(6,10)，(6,12)重叠。

---

对于你的信息，这是我的工作代码之前，我写这个问题在这里，你可以看到它不是很好。我只是用我的知识构建递归函数建立一个结果，并返回结果。

  private def joinAtoB(a: LineLike, b: LineLike): LineLike = {
    newFunction(a.start, b.end)
  }
  private def joinTouchingLines(a: LineLike, b: LineLike): Option[LineLike] = {
    if ((a.end + 1) == b.start)
      Some(joinAtoB(a, b))
    else
      None
  }
  @tailrec
  def joinLinesRec(list: List[LineLike], result: List[LineLike] = List[LineLike]())
                     :List[LineLike] = {
    list match {
      case Nil => result
      case item :: Nil => item :: result
      case first :: second :: rest => {
        val joined = joinTouchingLines(first, second)
        val prepend = joined match {
          case None => List(first, second)
          case Some(joinedItem) => List(joinedItem)
        }
        joinLinesRec(rest, prepend ::: result)
      }
    }
  }

Answer 1

您可以使用foldRight代替foldLeft，并使用模仿cons (::)的二进制函数，除非相邻元素接触:

def combine(x: (Int, Int), lst: List[(Int, Int)]) = (x, lst) match {
  case (_, Nil) => List(x)
  case ((a, b), (c, d) :: rest) => if (c == b+1)
                                     (a, d) :: rest
                                   else
                                     (a, b) :: lst
}

Answer 2

使用foldLeft很简单，但是如果去掉重叠或触摸时的规则部分则更简单:

def touching(fp: (Int, Int), sp: (Int, Int)) = 
  if (fp._2 >= sp._1) sys.error("Overlap " + fp + " and " + sp) 
  else if (fp._2 == sp._1 - 1) true 
  else false

然后你可以决定什么时候要追加，什么时候要扩展最后对:

list.foldLeft(List[(Int,Int)]()){
  (l, p) => 
    if (l.isEmpty || !touching(l.head, p)) p :: l
    else (l.head._1, p._2) :: l.tail
}.reverse