Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Pattern match end/middle of list in Scala

Can someone give me a simpler solution to the following code (which is unfolding a list of integers given a structure 0xFC :: len :: payload :: ... :: 0x0A :: 0x0D):

object Payload {
  def unapply(z: List[Int]): Option[List[Int]] = if (z.length == z.head + 1) Some(z tail) else None
}

object EndToken {
  def unapply(z: List[Int]): Option[List[Int]] = z.reverse match {
    case 0x0D :: 0x0A :: tail => Some(tail.reverse)
    case _ => None
  }
}

object Message {
  def unapply(z: List[Int]): Option[List[Int]] = z match {
    case 0xFC :: EndToken(x) => Some(x)
    case _ => None
  }
}

object Main extends App {
  val x = List(0xFC, 0x03, 0x01, 0x02, 0x03, 0x0A, 0x0D)

  x match {
    case Message(Payload(payload)) => println (payload)
    case _ => println("No match")
  }
}

Something like:

object Message {
  def unapply(z: List[Int]): Option[List[Int]] = z match {
    case 0xFC :: Payload(x) :: 0x0A :: 0x0D => Some(x)
    case _ => None
  }
}

But, of course, :: is expecting elements, not lists, so it doesn't work...

like image 624
Hugo Sereno Ferreira Avatar asked Oct 27 '11 12:10

Hugo Sereno Ferreira


3 Answers

Here is my solution (though on re-reading I think it's like Daniel's solution). It is based on a infix operation pattern where the pattern op(p, q) is the same p op q.

The operator starts with : to have same precedece as :: and ends with : to associate to the right. (len, payload) :!: tail is the same as :!:((len, payload), tail). The implementation of the payload extraction based on length is a bit more complex but mostly because I wanted to traverse the list only once.

object :!: {
  type LengthPayload = (Int, List[Int]) // (len, payload)
  // returns ((len, payload), unparsed)
  def unapply(z: List[Int]): Option[(LengthPayload, List[Int])] = {
    if (z == Nil) None 
    else {
      val len = z.head
      // use ListBuffer to traverse the list only once
      val buf = collection.mutable.ListBuffer[Int]()
      def take(l: Int, list: List[Int]): Option[(LengthPayload, List[Int])] = {
        list match {
          case Nil if l > 0 => None
          case _ if l == 0 => Some((len, buf.toList), list)
          case _ => buf += list.head; take(l - 1, list.tail)
        }
      }
      take(len, z.tail)
    }
  }
}

Then message becomes simpler (visually):

object Message {
  def unapply(z: List[Int]): Option[List[Int]] = z match {
    case 0xFC :: (len, payload) :!: 0x0A :: 0x0D :: Nil => Some(payload)
    case _ => None
  }
}

The result:

val x = List(0xFC, 0x03, 0x01, 0x02, 0x03, 0x0A, 0x0D)
x match {
  case Message(payload) => println(payload)
  case _ => println("No match")
}
// List(1, 2, 3)
like image 172
huynhjl Avatar answered Sep 23 '22 05:09

huynhjl


Pattern matching on the end of a sequence is now supported in Scala using the ':+' library object. I'm not sure when this functionality was added, but I read about it in the 2nd edition of Programming Scala by Dean Wampler and Alex Payne. Here is a simple example of retrieving a string of the last element in a list:

def stringOfLastElement[T](list: List[T]): String = list match {
    case prefix :+ end => end.toString
    case Nil => "Nil"
}
like image 29
Dylan Grald Avatar answered Sep 24 '22 05:09

Dylan Grald


You can take advantage of a bit of syntactic sugar for pattern matching here:

case a Pattern b => ... 

is the same as:

case Pattern(a, b) => ...

So if you modify your EndToke extractor like so:

object EndToken {
  def unapply(xs: List[Int]): Option[(List[Int], List[Int])] =
    (xs takeRight 2) match {
        case suffix @ (_ :: _ :: Nil) => Some((xs dropRight 2, suffix))
        case _ => None
    }
}

You can use it in patterns like:

case 1 :: 2 :: (payload EndToken (0xFF :: OxCC :: Nil)) => ...

(Sorry, I don't remember the precedence rules off hand so some of those parens may be unnecessary.)

like image 33
David Winslow Avatar answered Sep 23 '22 05:09

David Winslow