split list in scala based on diff between neighbouring elements

Question

How do we split list in scala based on difference between neighbouring elements. For example given List(1,3,6,10,12,14) and difference 3, the function would return List(List(1,3),List(6),List(10,12,14)).

Can we user foldLeft to do that? I was trying to create a function

def splitDiff(list:List[Int],diff:Int) = 
     def func(list:List[List[Int]],m:Int):List[List[Int]] = //compare with last element
     list.foldLeft(List(List(0))).foldLeft(func)

But the inner function seems difficult? Any help?

Answer 1

Hmm, I have a solution, but I suspect one can do better:

(test.head :: test).sliding(2).toList.map( (pair: List[Int]) => (pair(1), pair(1) - pair(0)) )
                   .foldLeft(List(List.empty[Int])){ (acc, pair) => 
     if (pair._2 < 3) (pair._1 :: acc.head) :: acc.tail else List(pair._1) :: acc }

Note that this gives results in "doubly-reversed" order:

res3: List[List[Int]] = List(List(14, 12, 10), List(6), List(3, 1))

Which can be corrected by adding .map(_.reverse).reverse to the end of the function.

EDIT - alternate attempt:

def func(is: List[Int], diff: Int): List[List[Int]] = {
  def loop(is: List[Int], prev: Int, acc: List[List[Int]]): List[List[Int]] = is match {
    case Nil => acc
    case h :: t if (h - prev < diff) => loop(t, h, (h :: acc.head) :: acc.tail)
    case h :: t => loop(t, h, List(h) :: acc)
  }

  loop(is, is.head, List(List.empty[Int]))
}

Again, gives solution in doubly-reversed form.

Answer 2

One more solution using foldLeft:

scala> val x = List(1,3,6,10,12,14)
x: List[Int] = List(1, 3, 6, 10, 12, 14)

scala> val y = x.foldLeft((x.head,List[Int](),List[List[Int]]())) 
     ((x,y)=> if((y- x._1) <3) (y,y :: x._2,x._3) else (y,List(y), x._2 :: x._3))
y: (Int, List[Int], List[List[Int]]) = (14,List(14, 12, 10),List(List(6), List(3
, 1)))

scala> val ans = y._2 :: y._3
ans: List[List[Int]] = List(List(14, 12, 10), List(6), List(3, 1))

Answer 3

Pleas keep in mind that this is untested:

  def splitListDiff(li: List[Int], diff: Int): List[Int] =
        {
          li match {
            case hd :: tl => if (hd - tl < diff) hd :: splitListDiff(tl, diff) else return li ++ splitListDiff(tl, diff)
            case _ => return li
          }
        }

But you wanted a solution that leverages foldleft?

Answer 4

The following works without additional reversing. Since the OP didn't say whether the list's elements are always in ascending order, I thought it'd be good to use Math.abs as well:

def splitDiff(diff: Int)(xs: List[Int]): List[List[Int]] = xs match {
  case Nil      => Nil
  case h :: t   =>
    val head = h :: ((xs zip t) takeWhile {
      case (a,b) => Math.abs(b-a) < diff
    } map (_._2))
    head :: splitDiff(diff)(xs drop head.length)
}

The downside of this approach is that the tail gets zipped over and over again. However, this could easily be avoided by encapsulating the match and zipping only once at the beginning.