Divide list into n parts in scala The problem is to divide a list into n parts according to a predicate. I found recursive solution but I am sure that a more elegant solution also exists.

def repeatedSpan[T](col: Iterable[T], pred: T =&gt; Boolean): List[Iterable[T]] = {
  if (col.isEmpty) Nil
  else {
    val (a, b) = col.span(pred)
    if (a.isEmpty) b.take(1) :: repeatedSpan(b.tail, pred)
    else a :: repeatedSpan(b, pred)
  }
}

scala&gt; repeatedSpan(List(1, 2, 3, 1, 4, 5, 6, 1, 7), (a: Int) =&gt; a != 1)
res9: List[Iterable[Int]] = List(List(1), List(2, 3), List(1), List(4, 5, 6), List(1), List(7))
I found about 5 things that can be improved, or maybe it's more accurate to say that I did 5 passes over the code in my efforts to improve it. Here's the changes I would recommend, in the order that I encountered them.

Better Names

The first change was mostly cosmetic, but it was very helpful laying the groundwork for more changes later.

def repeatedSpan[T](iterable: Iterable[T], pred: T =&gt; Boolean): List[Iterable[T]] = {
  if (iterable.isEmpty) Nil
  else {
    val (matches, rest) = iterable.span(pred)
    if (matches.isEmpty) rest.take(1) :: repeatedSpan(rest.tail, pred)
    else matches :: repeatedSpan(rest, pred)
  }
}


Naming is hard, particularly as rest is really the element that failed the predicate, and everything past that point.

Multiple Parameter Lists

This change was partially a help for the compiler, and partially to enable a bit of syntax that I'm partial to.

def repeatedSpan[T](col: Iterable[T])(pred: T =&gt; Boolean): List[Iterable[T]] = {
  if (col.isEmpty) Nil
  else {
    val (a, b) = col.span(pred)
    if (a.isEmpty) b.take(1) :: repeatedSpan(b.tail)(pred)
    else a :: repeatedSpan(b)(pred)
  }
}


By switching to a signature with multiple parameters, the compiler can infer types more easily, and as an additional bonus users can now use the shortened function literal syntax. 

repeatedSpan(basicList, (a:Int) =&gt; a != 1) # Not bad to type
repeatedSpan(basicList)(_ != 1)            # Much nicer!


Pattern Matching

The next change moved from if () else to pattern matching. I did this for two reasons. The first is that it allowed better naming that rest and generally made the logic a bit more clear. The second was that it paves the way for one of the other changes that I had my eye on.

def repeatedSpan[T](iterable: Iterable[T])(pred: T =&gt; Boolean): List[Iterable[T]] =
  iterable.span(pred) match {
    case (Nil, doesNotMatch :: unTested) =&gt;
      List(doesNotMatch) :: repeatedSpan(unTested)(pred)
    case (matchingPrefix, doesNotMatch :: unTested) =&gt;
      matchingPrefix :: List(doesNotMatch) :: repeatedSpan(unTested)(pred)
    case (matchingPrefix, Nil) =&gt; List(matchingPrefix)
  }


This had the added bonus of eliminating a level of nesting, but the big gain was being able to easily decompose the results into matchingPrefix, doesNotMatch, and unTested.

Tail Recursion

One of the big remaining issues is that this will blow the stack on large lists. So the next step, facilitated by the simplification we gained by switching to pattern matching, was to rework it into a tail recursive version.

def repeatedSpan[T](iterable: Iterable[T])(pred: T =&gt; Boolean): List[Iterable[T]] = {
  @tailrec
  def loop(accum: List[Iterable[T]], rest: Iterable[T]): List[Iterable[T]] =
    rest.span(pred) match {
      case (Nil, doesNotMatch :: unTested) =&gt;
        loop(List(doesNotMatch) :: accum, unTested)
      case (matchingPrefix, doesNotMatch :: unTested) =&gt;
        loop(List(doesNotMatch) :: matchingPrefix :: accum, unTested)
      case (matchingPrefix, Nil) =&gt; List(matchingPrefix)
        matchingPrefix :: accum
    }
  loop(Nil, iterable).reverse
}


This has a major weakness. Tail recursion lets us work with large Iterables, but a List is a singly linked list, and they do not append well. To fix this, I created the list in reverse, then at the end reversed the result. I was not particularly happy with adding this complexity, but it was necessary to gain access to tail-call optimization and avoid blowing the stack with larger lists.

Program to the Interface

The best way to remove the unnecessary complexity introduced in the last step was to switch data structures. This would be more difficult if this had a bunch of code that called it, but it was simple to modify the signature and use a Vector instead, which has excellent append performance.

def repeatedSpan[T](iterable: Iterable[T])(pred: T =&gt; Boolean): Iterable[Iterable[T]] = {
  @tailrec
  def loop(accum: Vector[Iterable[T]], rest: Iterable[T]): Iterable[Iterable[T]] =
    rest.span(pred) match {
      case (Nil, doesNotMatch :: unTested) =&gt; loop(accum :+ List(doesNotMatch), unTested)
      case (matches, doesNotMatch :: unTested) =&gt; loop(accum :+ matches :+ List(doesNotMatch), unTested)
      case (matches, Nil) =&gt; accum :+ matches
    }
  loop(Vector(), iterable)
}


Now that we are using a more appropriate data structure, we have regained the simplicity we had before, and don't run out of stack space.