Scala - increasing prefix of a sequence

Question

I was wondering what is the most elegant way of getting the increasing prefix of a given sequence. My idea is as follows, but it is not purely functional or any elegant:

val sequence = Seq(1,2,3,1,2,3,4,5,6)
var currentElement = sequence.head - 1
val increasingPrefix = sequence.takeWhile(e =>
            if (e > currentElement) {
                currentElement = e
                true
            } else
                false)

The result of the above is:

List(1,2,3)

Answer 1

You can take your solution, @Samlik, and effectively zip in the currentElement variable, but then map it out when you're done with it.

sequence.take(1) ++ sequence.zip(sequence.drop(1)).
    takeWhile({case (a, b) => a < b}).map({case (a, b) => b})

Also works with infinite sequences:

val sequence = Seq(1, 2, 3).toStream ++ Stream.from(1)

sequence is now an infinite Stream, but we can peek at the first 10 items:

scala> sequence.take(10).toList
res: List[Int] = List(1, 2, 3, 1, 2, 3, 4, 5, 6, 7)

Now, using the above snippet:

val prefix = sequence.take(1) ++ sequence.zip(sequence.drop(1)).
    takeWhile({case (a, b) => a < b}).map({case (a, b) => b})

Again, prefix is a Stream, but not infinite.

scala> prefix.toList
res: List[Int] = List(1, 2, 3)

N.b.: This does not handle the cases when sequence is empty, or when the prefix is also infinite.

Answer 2

If by elegant you mean concise and self-explanatory, it's probably something like the following:

sequence.inits.dropWhile(xs => xs != xs.sorted).next

inits gives us an iterator that returns the prefixes longest-first. We drop all the ones that aren't sorted and take the next one.

If you don't want to do all that sorting, you can write something like this:

sequence.scanLeft(Some(Int.MinValue): Option[Int]) {
  case (Some(last), i) if i > last => Some(i)
  case _ => None
}.tail.flatten

If the performance of this operation is really important, though (it probably isn't), you'll want to use something more imperative, since this solution still traverses the entire collection (twice).

Answer 3

And, another way to skin the cat:

 val sequence = Seq(1,2,3,1,2,3,4,5,6)
 sequence.head :: sequence
                  .sliding(2)
                  .takeWhile{case List(a,b) => a <= b}
                  .map(_(1)).toList
// List[Int] = List(1, 2, 3)