In Scala, how to foldleft when sometimes two elements should not turn into one element?

Question

I have a list of Pair's which represent lines with a start index and end index. The type is (Int,Int) being a tuple of two integers.

Now I wish to join together any lines which are touching each other, for example.

List( (1,5),(6,10),(12,20) ) should transform into List( (1,10), (12,20) ) because line (1,5) touches line (6,10). Only touching lines are joined together into a single line.

My first thought was to use foldleft on the list, the problem is that foldleft needs to transform two elements into one and would eventually end up with just one (Int,Int) outputted at the end.

Second thought is a recursive solution which I did program but this doesn't seem like the best or simplest idea. The idea that we are taking two elements and sometimes outputting one element or two elements seems like something which should be applied to many cases, like foldleft does.

Is there any common way or pattern or library to solve this problem?

---

A single line is on the 1 dimensional plane, its not a x,y point. The (Int,Int) is a start and end point on the 1 dimensional plane.

To clear up the definition of touching. None of the lines in the list overlap, this is a pre-condition, that is (1, 3) and (2, 4) cannot exist in a list because they overlap.

(1,3), (4,5) could exist in a list because they do not overlap.

(1,3), (4,5) does touch because 3 and 4 have exactly a distance of 1 between them.

For the list as given in the questions ((1, 5), (6, 10), (6, 12), (13, 15)), this is an invalid list because (6, 10), (6, 12) overlaps.

---

For your info, this is my working code before I wrote this question here, you can see its not great. I was just using my knowledge of building recursive function which builds up a result and returns the result.

  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

You can use foldRight instead of foldLeft with a binary function that mimicks cons (::) except when adjacent elements touch:

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

It's simple to perform this with foldLeft, but it's even simpler if you take out the part that rules when we're overlapping or touching:

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

Then you can decide when you want to just append and when you want to extend the last pair:

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