What's Scala's idiomatic way to split a List by separator?

Question

If I have a List of type String,

scala> val items = List("Apple","Banana","Orange","Tomato","Grapes","BREAK","Salt","Pepper","BREAK","Fish","Chicken","Beef")
items: List[java.lang.String] = List(Apple, Banana, Orange, Tomato, Grapes, BREAK, Salt, Pepper, BREAK, Fish, Chicken, Beef)

how can I split it into n separate lists based on a certain string/pattern ("BREAK", in this case).

I've thought about finding the position of "BREAK" with indexOf, and split up the list that way, or using a similar approach with takeWhile (i => i != "BREAK") but I'm wondering if there's a better way?

If it helps, I know there will only ever be 3 sets of items in the items list (thus 2 "BREAK" markers).

`splitAt` may be more appropriate, but the annoying thing is that `BREAK` still remains and you need to manually remove it. — Kane, Jan 30 '13 at 21:23
This question is similar, though not exactly the same: http://stackoverflow.com/q/7293617/770361 — Luigi Plinge, Jan 30 '13 at 22:39
+1 to Luigi for finding an answer from Martin Odersky himself :) — jbnunn, Jan 30 '13 at 22:42

score 11 · Accepted Answer · edited Dec 06 '20 at 17:03

def splitBySeparator[T](l: List[T], sep: T): List[List[T]] = {
  l.span( _ != sep ) match {
    case (hd, _ :: tl) => hd :: splitBySeparator(tl, sep)
    case (hd, _) => List(hd)
  }
}

val items = List("Apple","Banana","Orange","Tomato","Grapes","BREAK","Salt","Pepper","BREAK","Fish","Chicken","Beef")
splitBySeparator(items, "BREAK")

Result:

res1: List[List[String]] = List(List(Apple, Banana, Orange, Tomato, Grapes), List(Salt, Pepper), List(Fish, Chicken, Beef))

UPDATE: The above version, while concise and effective, has two problems: it does not handle well the edge cases (like List("BREAK") or List("BREAK", "Apple", "BREAK"), and is not tail recursive. So here is another (imperative) version that fixes this:

import collection.mutable.ListBuffer
def splitBySeparator[T](l: Seq[T], sep: T): Seq[Seq[T]] = {
  val b = ListBuffer(ListBuffer[T]())
  l foreach { e =>
    if ( e == sep ) {
      if  ( !b.last.isEmpty ) b += ListBuffer[T]()
    }
    else b.last += e
  }
  b.map(_.toSeq)
}

It internally uses a ListBuffer, much like the implementation of List.span that I used in the first version of splitBySeparator.

this is not tail recursive so use with caution on long lists — stew, Jan 30 '13 at 21:54
stew, good point--my lists will be relatively short so I shouldn't have to worry. — jbnunn, Jan 30 '13 at 21:59
@stew: Indeed. I updated the answer with a version that is tail recursive (along with having a batter hanbdling of edge cases). — Régis Jean-Gilles, Jan 30 '13 at 22:06
And I did run into the `List("BREAK")` edge-case, so thank you for the revise — jbnunn, Jan 30 '13 at 22:36

score 6 · Answer 2 · edited Dec 06 '20 at 18:29

6

Another option:

val l = Seq(1, 2, 3, 4, 5, 9, 1, 2, 3, 4, 5, 9, 1, 2, 3, 4, 5, 9, 1, 2, 3, 4, 5)

l.foldLeft(Seq(Seq.empty[Int])) {
  (acc, i) =>
    if (i == 9) acc :+ Seq.empty
    else acc.init :+ (acc.last :+ i)
}

// produces:
List(List(1, 2, 3, 4, 5), List(1, 2, 3, 4, 5), List(1, 2, 3, 4, 5), List(1, 2, 3, 4, 5))

edited Dec 06 '20 at 18:29

Tomer Shetah

8,413
7
27
35

answered Jan 30 '13 at 22:00

Ryan LeCompte

4,281
1
14
14

It is not efficient to add elements to the end of the `List` – Tomer Shetah Dec 06 '20 at 19:08

Kane · Answer 3 · 2013-01-30T21:49:36.003

How about this: use scan to figure out which section every element in the list belongs to.

val l = List("Apple","Banana","Orange","Tomato","Grapes","BREAK","Salt","Pepper","BREAK","Fish","Chicken","Beef")
val count = l.scanLeft(0) { (n, s) => if (s=="BREAK") n+1 else n } drop(1)
val paired = l zip count
(0 to count.last) map { sec => 
  paired flatMap { case (x, c) => if (c==sec && x!="BREAK") Some(x) else None }  
}
// Vector(List(Apple, Banana, Orange, Tomato, Grapes), List(Salt, Pepper), List(Fish, Chicken, Beef))

score 0 · Answer 4 · edited May 23 '17 at 11:51

This is not tail-recursive either, but it does ok with edge cases:

def splitsies[T](l:List[T], sep:T) : List[List[T]] = l match {
  case head :: tail =>
    if (head != sep)
      splitsies(tail,sep) match {
        case h :: t => (head :: h) :: t
        case Nil => List(List(head))
      }
    else
      List() :: splitsies(tail, sep)
  case Nil => List()
}

The only annoying thing:

scala> splitsies(List("BREAK","Tiger"),"BREAK")
res6: List[List[String]] = List(List(), List(Tiger))

If you want to handle separator-started cases better, look at something not unlike the use of span in Martin's answer (to a slightly different question).

Tomer Shetah · Answer 5 · 2020-12-07T16:35:31.423

Using List.unfold (Scala 2.13 and above):

val p: String => Boolean = _ != "BREAK"

val result: List[List[String]] = List.unfold(items) {
  case Nil =>
    None
  case l if p(l.head) =>
    Some(l.span(p))
  case _ :: tail =>
    Some(tail.span(p))
}

Code run at Scastie.

Using `reverse` + `foldLeft`:

def splitAtElement[T](list: List[T], element: T): List[List[T]] = {
  list.reverse.foldLeft(List(List[T]()))((l, currentElement) => {
    if (currentElement == element) {
      List() :: l
    } else {
      (currentElement :: l.head) :: l.tail
    }
  })
}

Code run at Scastie.

Using `foldRight`:

def splitBySeparator[T](list: List[T], sep: T): List[List[T]] = {
  list.foldRight(List(List[T]()))((s, l) => {
    if (sep == s) {
      List() :: l
    } else {
      (s :: l.head) :: l.tail
    }
  }).filter(_.nonEmpty)
}

Code run at Scastie.

score -1 · Answer 6 · edited Jun 18 '16 at 17:35

val q = items.mkString(",").split("BREAK").map("(^,|,$)".r.replaceAllIn(_, "")).map(_.split(","))

Here "," is a unique separator that does not appear in any of the strings in the items list. We could choose a different separator if needed.

items.mkString(",") combines everything into a string

.split("BREAK") // which we then split using "BREAK" as delimiter to get a list

.map("(^,|,$)".r.replaceAllIn(_, "")) // removes the leading/trailing commas of each element of the list in previous step

.map(_.split(",")) // splits each element using comma as seperator to give a list of lists


scala> val q = items.mkString(",").split("BREAK").map("(^,|,$)".r.replaceAllIn(_, "")).map(_.split(","))
q: Array[Array[String]] = Array(Array(Apple, Banana, Orange, Tomato, Grapes), Array(Salt, Pepper), Array(Fish, Chicken, Beef))

scala> q(0)
res21: Array[String] = Array(Apple, Banana, Orange, Tomato, Grapes)

scala> q(1)
res22: Array[String] = Array(Salt, Pepper)

scala> q(2)
res23: Array[String] = Array(Fish, Chicken, Beef)

What's Scala's idiomatic way to split a List by separator?

6 Answers6

Using List.unfold (Scala 2.13 and above):

Using `reverse` + `foldLeft`:

Using `foldRight`:

Linked

Related

What's Scala's idiomatic way to split a List by separator?

6 Answers6

Using List.unfold (Scala 2.13 and above):

Using reverse + foldLeft:

Using foldRight:

Linked

Related

Using `reverse` + `foldLeft`:

Using `foldRight`: