CODEWITHSUNDEEP
scalapattern-matching
Jens Egholm
Jens Egholm

Reputation: 2710

Matching a sequence within a sequence in scala

I'm looking to match a sequence within a sequence like either in ex 1 or ex 2;

List(1, 2, 3, 4) match {
  case 1 :: List(_*) :: 4 :: tail => // Ex 1
  case 1 :: (seq : List[Int]) :: 4 :: tail => // Ex 2
  case _ => 
}

This is a variant to the fixed length sequence pattern _*. Like the _*, I don't care about the content of the inner pattern, but it is important that the length can vary and that the pattern is surrounded by a prefix (such as the 1 above) and a suffix (like the 4).

My question is if any of you have a trick to do this by some crafty unapply magic or if you'd just iterate the list to search for the sequence manually.

Thanks in advance! :-)

Upvotes: 0

Views: 384

Answers (2)

ernestRC
ernestRC

Reputation: 35

You could do something like this:

List(1,2,3,4) match {
    case 1 :: tail if tail.last == 4 => println("Found it!")
  }

But if you check the implementation of last in LinearSeqOptimized:

  def last: A = {
    if (isEmpty) throw new NoSuchElementException
    var these = this
    var nx = these.tail
    while (!nx.isEmpty) {
      these = nx
      nx = nx.tail
    }
    these.head
  }

It is iterating indeed. This is because List inherits from LinearSeq which are optimized to provide efficient head and tail operations. For what you want to do, it is better to use an IndexedSeq implementation like Vector which has an optimized length operation, used in last:

override /*TraversableLike*/ def last: A = {
    if (isEmpty) throw new UnsupportedOperationException("empty.last")
    apply(length-1)
  }

So you could do something like this:

Vector(1,2,3,4) match {
    case v if v.head == 1 && v.last == 4 => println("Found it!")
  }

Upvotes: 1

Rex Kerr
Rex Kerr

Reputation: 167871

This is really outside the scope of what pattern matching is supposed to be used for. Even if you could finagle a set of custom unapply methods to do what you wanted, it wouldn't be apparent whether matching was greedy or not, etc..

However, if you really want to, you can proceed as follows (for example):

import scala.collection.SeqLike
class Decon[A](a0: A, a1: A) {
  def unapply[C <: SeqLike[A, C]](xs: C with SeqLike[A, C]): Option[(C, C)] = {
     xs.span(_ != a1) match {
       case (a0 +: pre, a1 +: post) => Some((pre,post))
       case _ => None
     }
   }
}
val Dc = new Decon(1,4)

scala> List(1,2,3,4,5) match { case Dc(pre, post) => (pre, post); case _ => (Nil, Nil) }
res1: (List[Int], List[Int]) = (List(2, 3),List(5))

Separating the specification of the fixed elements 1 and 4 from the match is necessary; otherwise the normal algorithm would ask the unapply to return values without any knowledge of what was being sought, and then would test to make sure they were correct.

Upvotes: 2

Related Questions