# Divide list into n parts in scala [closed]

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 => 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> repeatedSpan(List(1, 2, 3, 1, 4, 5, 6, 1, 7), (a: Int) => a != 1)
res9: List[Iterable[Int]] = List(List(1), List(2, 3), List(1), List(4, 5, 6), List(1), List(7))

• Is it intentional that repeatedSpan(List(1, 1, 2), a => a != 1) gives List(List(1), List(1), List(2)) instead of List(List(1, 1), List(2)) ? Commented Nov 29, 2015 at 0:07
• It doesn't matter specifically in my case. Both variants are acceptable. Commented Nov 29, 2015 at 9:50
• I don't see a more elegant approach. Commented Nov 30, 2015 at 18:47
• @chessman It should matter. The output of a function should be unambiguous, not subject to change depending on the implementation. Commented Dec 29, 2015 at 12:27
• What Janos has found is probably a bug (in which case your code needs to be fixed before this is truly suitable for review). Either that or you need to be more clear about the requirements and constraints of the problem. As it stands, the function is useless; no useful meaning can be given to its output. I'm not sure it would be useful even if clarified. Commented Jan 3, 2016 at 13:00

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 => 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 => 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) => 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 => Boolean): List[Iterable[T]] =
iterable.span(pred) match {
case (Nil, doesNotMatch :: unTested) =>
List(doesNotMatch) :: repeatedSpan(unTested)(pred)
case (matchingPrefix, doesNotMatch :: unTested) =>
matchingPrefix :: List(doesNotMatch) :: repeatedSpan(unTested)(pred)
case (matchingPrefix, Nil) => 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 => 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) =>
loop(List(doesNotMatch) :: accum, unTested)
case (matchingPrefix, doesNotMatch :: unTested) =>
loop(List(doesNotMatch) :: matchingPrefix :: accum, unTested)
case (matchingPrefix, Nil) => 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 => 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) => loop(accum :+ List(doesNotMatch), unTested)
case (matches, doesNotMatch :: unTested) => loop(accum :+ matches :+ List(doesNotMatch), unTested)
case (matches, Nil) => 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.

• But even after those improvements, repeatedSpan(List(1, 2, 3, 1, 4, 5, 6, 1, 7), (a: Int) => a != 1) and repeatedSpan(List(1, 2, 3, 1, 4, 5, 6, 1, 7), (a: Int) => a == 1) still return the same output ;-) Commented Jan 3, 2016 at 22:13
• @itsbruce True, but now that it's been cleaned up a bit that should be easier to address. I tend to approach refactoring under the assumption that it should preserve the original behavior (quirks and all), as that's what holds most often when I am doing this at work. I agree that is an example of very poor behavior, and when clarification comes in of what better behavior is desired, I'll likely update with a fixed version. Commented Jan 4, 2016 at 0:05

# Meaningless output

Your function as written does not seem useful. There is no way to assign meaning to its output for two principal reasons.

## 1. Non-matching sequences reduced to single item lists

As @janos pointed out in his comments, any sequence of items which fail the predicate will be transformed into a sequence of single-item lists in the function's output. While this does mean that any list in the output with size > 2 will contain only matching items, there is no way to tell whether a list of size 1 contains matching items or non-matching ones (without reapplying the predicate to each).

If this were fixed so that non-matching sequences were not broken down, then the output would be alternating matching/non-matching sequences, which would be marginally more useful. Except that...

## 2. Nil in (Nil, _) output from span is discarded

If span returns (Nil, _) - showing that not even the first element satisfies the predicate - you discard that Nil. This means we cannot know whether the first list in the output matches the predicate (without reapplying the predicate). This means that, regardless of whether the problem in point 1 were fixed, repeatedSpan(List(1, 2, 3, 1, 4, 5, 6, 1, 7), (a: Int) => a != 1) gives the same output as repeatedSpan(List(1, 2, 3, 1, 4, 5, 6, 1, 7), (a: Int) => a == 1)

# Possible Improvements

## Minor: still returning List[Iterable[T]]

If we stick to your basic design, returning List[Iterable[T]], but

1. Do not break down non-matching sequences but preserve them
2. Do not discard an initial Nil

then we have a function which will return one of the following:

• Nil (if the input was Nil)
• A list containing the original iterable (if all members satisfied the predicate)
• A list containing alternating passing/failing iterables, where the first passes (although may be Nil).

This does fix the issue of both { _ != 1 } and { _ == 1} returning the same result. It also allows us to be sure whether an iterable contains passing or failing elements but only if we keep careful track of whether we're looking at even or odd indices in the list. That makes it difficult to fold or recur over the list or to perform other higher order functions (filtering, mapping etc.) which take into account whether iterables contain passing or failing elements.

## More Functional: List[Either[Iterable[T], Iterable[T]]]

2. Do discard an initial Nil (as in your code)
3. Wrap failing iterables in Left and passing iterables in Right