How to extend a Scala list to enable slicing not by explicit position but by given predicate/condition

collections, list, scala, slice

Solution

`List` already has a `slice` method - it takes a subset of elements between a start and end index. What you're looking for is repeated application of the `span` method:

def span(p: (A) ⇒ Boolean): (List[A], List[A])

Which is documented as:

Splits this list into a prefix/suffix pair according to a predicate.

Note: c span p is equivalent to (but possibly more efficient than) (c takeWhile p, c dropWhile p), provided the evaluation of the predicate p does not cause any side-effects.

returns: a pair consisting of the longest prefix of this list whose elements all satisfy p, and the rest of this list.

You can get what you need by repeatedly using this method with an inverse predicate, and an extra bit of logic to ensure that none of the returned Lists are empty.

import annotation.tailrec

def multiSpan[A](xs: List[A])(splitOn: (A) => Boolean): List[List[A]] = {
  @tailrec
  def loop(xs: List[A], acc: List[List[A]]) : List[List[A]] = xs match {
    case Nil => acc

    case x :: Nil => List(x) :: acc

    case h :: t =>
      val (pre,post) = t.span(!splitOn(_))
      loop(post, (h :: pre) :: acc)
  }
  loop(xs, Nil).reverse
}

UPDATE

As requested in comments on the original post, here's a version that enriches list instead of being a standalone method:

implicit class AddMultispanToList[A](val list: List[A]) extends AnyVal {
  def multiSpan(splitOn: (A) => Boolean): List[List[A]] = {
    @tailrec
    def loop(xs: List[A], acc: List[List[A]]) : List[List[A]] = xs match {
      case Nil => acc

      case x :: Nil => List(x) :: acc

      case h :: t =>
        val (pre,post) = t.span(!splitOn(_))
        loop(post, (h :: pre) :: acc)
    }
    loop(list, Nil).reverse
  }
}

Use as:

myList.multiSpan(_.isInstanceOf[TypeA])

Problem

For ``` trait Item case class TypeA(i: Int) extends Item case class TypeB(i: Int) extends Item ``` consider a Scala list of items such as ``` val myList = List(TypeA(1), TypeB(11), TypeB(12), TypeA(2), TypeB(21), TypeA(3), TypeB(31)) ``` The goal is to define a new `slice` method that can be applied onto `myList` and which takes a predicate or condition as argument; for instance ``` myList.slice { x => x.isInstanceOf[TypeA] } ``` would deliver ``` List(List(TypeA(1), TypeB(11), TypeB(12)), List(TypeA(2), TypeB(21)), List(TypeA(3), TypeB(31))) ``` In this example, an identical result would be achieved by ``` myList.slice { case TypeA(x) => x < 10 } ``` Many Thanks.

Original source