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

Question

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.

oh. do you mean that the predicate defines "things that begin a new sub-list"? — Rob Starling, Feb 15 '14 at 21:05
@Rob Starling that's right, the predicate defines the lower bound of each sub-list. — elm, Feb 15 '14 at 21:10
what are you looking for in the case that the input doesn't contain (or doesn't begin with) elements that satisfy the predicate? — Rob Starling, Feb 15 '14 at 21:29
@Rob Starling `List span` proves a simpler, well-defined case, as depicted by @Kevin Wright; a `multiSpan` method is quested here, ideally callable from a list instance more than as a separate method with list and predicate as arguments. — elm, Feb 15 '14 at 21:38
@user3189923 - Okay, I showed how to do that as well in my answer — Kevin Wright, Feb 16 '14 at 10:15

score 6 · Accepted Answer · edited Jun 20 '20 at 09:12

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])

It wouldn't be the first time I've had to tackle this problem :) — Kevin Wright, Feb 16 '14 at 13:29

score 0 · Answer 2 · answered Feb 15 '14 at 17:36

0

Why couldn't you use partition method from the standard API?

example:

scala> val l = List(3,5,4,6)
l: List[Int] = List(3, 5, 4, 6)

scala> 

scala> val (odd,even) = l.partition(_ %2 ==1)
odd: List[Int] = List(3, 5)
even: List[Int] = List(4, 6)

For your example:

scala> val (typeA,typeB) = myList.partition(_.isInstanceOf[TypeA])
typeA: List[Product with Serializable with Item] = List(TypeA(1), TypeA(2), TypeA(3))
typeB: List[Product with Serializable with Item] = List(TypeB(11), TypeB(12), TypeB(21), TypeB(31))

answered Feb 15 '14 at 17:36

Ashalynd

12,363
2
34
37

Many Thanks for the idea; partition would bisect the initial list into two; in this case we would need multiple sublists, the lower bound of each is defined by a condition... – elm Feb 15 '14 at 17:40
Do you mean that you want to get more than two sublists? Then you would probably have to write a macro for that, or use map + match + groupBy – Ashalynd Feb 15 '14 at 17:42
Wish a similar answer as in this question http://stackoverflow.com/q/21787505/3189923 where class `List` gets equipped with a `sum` method for a specialised set of numbers. – elm Feb 15 '14 at 17:48

score 0 · Answer 3 · answered Feb 15 '14 at 21:01

Aren't you looking for filter, which works (almost) without any tweaks for your examples?

$ sbt console
scala> trait Item
scala> case class TypeA(i: Int) extends Item
scala> case class TypeB(i: Int) extends Item
scala> val myList = List(TypeA(1), TypeB(11), TypeB(12), 
                         TypeA(2), TypeB(21), 
                         TypeA(3), TypeB(31))
myList: List[Product with Serializable with Item] = List(TypeA(1), TypeB(11), TypeB(12), TypeA(2), TypeB(21), TypeA(3), TypeB(31))

your first works unaltered:

scala> myList.filter { x => x.isInstanceOf[TypeA] }
res0: List[Product with Serializable with Item] = List(TypeA(1), TypeA(2), TypeA(3))

your second requires a default case:

scala> myList.filter { case TypeA(x) => x < 10; case _ => false }
res2: List[Product with Serializable with Item] = List(TypeA(1(3))

See also collect, which takes a partial function instead of a boolean predicate:

scala> myList.collect { case z @ TypeA(x) if x < 10 => z }
res3: List[TypeA] = List(TypeA(1), TypeA(2), TypeA(3))

and can transform as well:

scala> myList.collect { case TypeA(x) if x < 10 => x }
res4: List[Int] = List(1, 2, 3)

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

3 Answers3

Linked