Collapse subsequence of matching elements in a Scala sequence

Question

Given a Scala sequence...

val sequence: Seq = List( 3, 1, 4, 1, 5, 9, 2, 6, 5 )

...say that I want to find all subsequences matching certain criteria, e.g. strings of odd numbers, and replace those with the result of some operation on that subsequence, say its length, producing a new sequence:

val sequence2: Seq = List( 2, 4, 3, 2, 6, 1 )

(Yes, this is a fairly contrived example, but it's concise.)

So far the best I've been able to do is this ugly imperative hack:

val sequence: Seq[Int] = List( 3, 1, 4, 1, 5, 9, 2, 6, 5 )

var sequence2 = List[Int]()   // this is going to be our result
var subsequence = List[Int]()

for (s <- sequence) {
  if (s % 2 == 0) {
    if (!subsequence.isEmpty) {
      sequence2 = sequence2 :+ subsequence.length
      subsequence = List[Int]()
    }
    sequence2 = sequence2 :+ s
  } else {
    subsequence = subsequence :+ s
  }
}

if (!subsequence.isEmpty) {
  sequence2 = sequence2 :+ subsequence.length
}

Is there an elegant (/ functional) way to do this?

score 3 · Accepted Answer · edited May 23 '17 at 12:20

Using multiSpan for spanning a list into sublists by given criteria, consider this solution for the problem depicted above,

sequence.multiSpan( _ % 2 == 0 ).flatMap {
   case h :: xs if h % 2 != 0 => List( (h::xs).length)
   case h :: Nil => List(h) 
   case h :: xs => List(h, xs.length) }

Note that

sequence.multiSpan( _ % 2 == 0 )
List(List(3, 1), List(4, 1, 5, 9), List(2), List(6, 5))

and hence we flatMap these nested lists by considering three cases: whether the condition does not hold and so we apply a function; whether it is a singleton list (the condition holds); or else whether the first element holds and the rest needs be applied a function.

score 2 · Answer 2 · edited May 23 '17 at 11:57

What you're looking for is a fold:

sequence.foldLeft(List(0)) { (soFar, next) =>
    if(next % 2 == 0) soFar :+ next :+ 0 else soFar.init :+ (soFar.last + 1) 
}.filter(_ != 0)

Or in a different style:

(List(0) /: sequence) { 
    case(soFar, next) if next % 2 == 0 => soFar :+ next :+ 0
    case(soFar, _) => soFar.init :+ (soFar.last + 1)
}.filter(_ != 0)

Or with a foldRight instead, which is sometimes more performant:

(sequence :\ List(0)) { 
    case(next, soFar) if next % 2 == 0 => 0 :: next :: soFar
    case(_, hd::tl) => (hd + 1)::tl
}.filter(_ != 0).reverse

You can read more about fold, foldLeft, foldRight, and other useful functions here and here.

I originally thought you were asking for all subsequences of a sequence. That might be useful in similar situations, so I'll leave this here. You can use inits and tails together to get all subsequences, and then use filter and map for your purposes:

val sequence = List( 3, 1, 4, 1, 5, 9, 2, 6, 5 )
val subsequences = sequence.tails.flatMap(_.inits).toList.distinct
subsequences.filter(_.forall(_ % 2 == 1)).map(_.length)

That gets me `List(2, 1, 0, 1, 3, 2, 2, 1, 1)`. I think "all subsequences" is more combinatorial than what I need. — David Moles, Feb 19 '15 at 00:36
I totally misunderstood your question. I get it now. Give me a minute. — Ben Reich, Feb 19 '15 at 01:12

score 1 · Answer 3 · answered Feb 19 '15 at 02:02

Here is my attempt at a recursive implementation

def subSequenceApply(list: List[Int], predicate: (Int)=> Boolean, func: (List[Int]) => Int):List[Int] = list match {
  case Nil => Nil
  case h :: t if !predicate(h) => h :: subSequenceApply(t, predicate, func)
  case _ =>
    val (matchSeq,nonMatch) = list.span(predicate)
    func(matchSeq) :: subSequenceApply(nonMatch, predicate, func)
}

So given sequence in your example. You could run it as

subSequenceApply(sequence, _ % 2 != 0, _.length)

Collapse subsequence of matching elements in a Scala sequence

3 Answers3