Scala how to get elements with equal list value in sublists
case class E(timestamp: Long, value: Double)
I have a list of instances E. The items in the list are ordered by timestamp. I would like to group a slice of items with 0 value in the sublists and drop the non-null ones. For example,
val xs = List(E1, E2, E3, E4, E5, E6, E7, E8, E9, E10)
where E2, E3, E4, E7, E8, E10
is 0
result = List(List(E2, E3, E4), List(E7, E8), List(E10))
What's the best way to do this in Scala? Thank!
source to share
Here's a generic method that will give you what you're looking for:
def splitBy[A](l: List[A])(pred: A => Boolean): List[List[A]] = {
l match {
case Nil => Nil
case _ =>
val res = l.dropWhile(a => !pred(a))
val (acc, r) = res.span(pred)
acc :: splitBy(r)(pred)
}
}
Here's a general example:
val E1 = E(1, 1)
val E2 = E(2, 0)
val E3 = E(3, 0)
val E4 = E(4, 0)
val E5 = E(5, 1)
val E6 = E(6, 1)
val E7 = E(7, 0)
val E8 = E(8, 0)
val E9 = E(9, 1)
val E10 = E(10, 0)
val xs = List(E1, E2, E3, E4, E5, E6, E7, E8, E9, E10)
println(splitBy(xs)(_.value == 0.0))
//prints List(List(E(2,0.0), E(3,0.0), E(4,0.0)), List(E(7,0.0), E(8,0.0)), List(E(10,0.0)))
Note that this is mostly foldRight
list-based and not stack-compatible, for example it will result in a stack overflow println(splitBy(List.fill(10000)(xs).flatten)(_.value == 0.0))
.
Here's a safe version of the stack:
@tailrec
def splitBy[A](l: List[A], accum:List[List[A]] = Nil)(pred: A => Boolean): List[List[A]] = {
l match {
case Nil => accum.reverse
case _ =>
val res = l.dropWhile(a => !pred(a))
val (acc, r) = res.span(pred)
splitBy(r, acc :: accum)(pred)
}
}
source to share
Here is a one-liner (using the foldLeft + filter):
scala> val l = List(1, 0, 0, 0, 2, 3, 0, 0, 5, 6, 0)
l: List[Int] = List(1, 0, 0, 0, 2, 3, 0, 0, 5, 6, 0)
scala> (l ++ List(1)).foldLeft((List(List[Int]()), List[Int]()))((a, b) => if (b != 0) (a._1 +: a._2, Nil) else (a._1, a._2 +: b))._1.filter(_.nonEmpty)
res26: List[List[Int]] = List(List(0, 0, 0), List(0, 0), List(0))
A more readable version:
def groupByPred[T](l: List[T], predicate: T => Boolean = (x: T) => x == 0) = {
case class Acc(perm: List[List[T]] = Nil, temp: List[T] = Nil)
val raw = l.foldLeft(Acc())((a, b) =>
if (!predicate(b)) Acc(a.perm :+ a.temp, Nil) else Acc(a.perm, a.temp :+ b))
(raw.perm :+ raw.temp).filter(_.nonEmpty)
}
Note that the ": +" concatenation takes O (n), so it's better to use ListBuffer instead of List here.
source to share
Here's a rather idiomatic approach using takeWhile
and dropWhile
.
def subLists[A](xs: List[A], p: A => Boolean):List[List[A]] = xs match{
case List() => List()
case h::t => {
if(p(h)){
xs.takeWhile(p) :: subLists(xs.dropWhile(p), p)
}else{
subLists(t, p)
}
}
}
Ouput.
scala> subLists(xs, isEZero) │
res6: List[List[E]] = List(List(E(3,0.0), E(4,0.0), E(5,0.0)), List(E(7,0.0), E(8,0.0)), List(E(10,0.0)))
Code / data to copy / paste for the following.
def isEZero(e:E) = e.value == 0.0
val E1 = E(1L, 1.0)
val E2 = E(2L, 1.0)
val E3 = E(3L, 0.0)
val E4 = E(4L, 0.0)
val E5 = E(5L, 0.0)
val E6 = E(6L, 1.0)
val E7 = E(7L, 0.0)
val E8 = E(8L, 0.0)
val E9 = E(9L, 1.0)
val E10 = E(10L, 0.0)
val xs = List(E1,E2,E3,E4,E5,E6,E7,E8,E9,E10)
source to share