CODEWITHSUNDEEP
scala
gang
gang

Reputation: 55

Scala how to get equal-value elements of List into sublists

case class E(timestamp: Long, value: Double)

I have a list of instance E. The elements in list are ordered by the timestamp. I would like group chunk of elements with 0 value into sublists and drop the none-zero ones. For example,

val xs = List(E1, E2, E3, E4, E5, E6, E7, E8, E9, E10)

where E2, E3, E4, E7, E8, E10 have 0 value

result = List(List(E2, E3, E4), List(E7, E8), List(E10))

What is the best way to do this in Scala? Thanks!

Upvotes: 3

Views: 395

Answers (3)

dk14
dk14

Reputation: 22374

Here is one-liner (using 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))

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 ":+" concatenation takes O(n), so it's better to use ListBuffer instead of List here.

Upvotes: 2

Brian
Brian

Reputation: 20285

Here's a fairly 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 those following along.

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)

Upvotes: 0

Noah
Noah

Reputation: 13959

Here's a generalized 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 I setup:

  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 basically a foldRight over the list and is not not stack friendly, for example this will cause a stack overflow println(splitBy(List.fill(10000)(xs).flatten)(_.value == 0.0)).

Here's a stack safe version:

  @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)
    }
  }

Upvotes: 1

Related Questions