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

Question

我有一个Pair列表,它表示带有起始索引和结束索引的行.类型是(Int,Int)是两个整数的元组.

例如,现在我希望将任何相互接触的线连接在一起.

列表((1,5),(6,10),(12,20))应该转换为List((1,10),(12,20))因为行(1,5)接触行(6,10) ).只有触摸线连接在一起成一条线.

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

第二个想法是我做过程序的递归解决方案,但这似乎不是最好或最简单的想法.我们采用两个元素并且有时输出一个元素或两个元素的想法似乎应该适用于许多情况,例如foldleft.

是否有任何通用的方式或模式或库来解决这个问题？

---

单线位于1维平面上,不是轴,y点.(Int,Int)是1维平面上的起点和终点.

清理触摸的定义.列表中没有任何行重叠,这是一个前提条件,即(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

除了相邻元素触摸时,您可以使用模仿cons()的二元函数foldRight代替:foldLeft::

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
}