Соответствует произвольному размеру списка в Scala - PullRequest
Новая
       1

Соответствует произвольному размеру списка в Scala

3 голосов
/ 26 октября 2011

Предположим, у меня есть бесконечный список вещей.В этом списке у меня иногда есть что-то, указывающее, что скрытое сообщение должно начинаться, затем длина сообщения, crc, а затем маркер конца.Затем список продолжается, и где-то появляется новое сообщение: 

a :: b :: start :: 3 :: 1 :: 2 :: 3 :: 4FAA :: end :: x :: y :: z :: ....

Какой самый идиоматичный (с использованием match, я думаю?) Шаблон, сопоставляющий его со структурой, подобной: 

size = 3
payload = 1 :: 2 :: 3
crc = 4FAA

Кроме того, примите во внимание, что токен «start» может появляться внутри полезной нагрузки, поэтому следует полагаться на «полное совпадение».

Ответы [ 3 ]

8 голосов
/ 27 октября 2011

Используйте парсер комбинатор. Точное решение для вас, кажется, разбирает токены, но, для упрощения, я предполагаю, что вы просто читаете строку слов, разделенных пробелами. 

object P extends scala.util.parsing.combinator.RegexParsers {
  def message: Parser[Any] = properMessage | dummy ~> message
  def properMessage = start ~> body <~ end
  def start = "(?i)start".r
  def end = "(?i)end".r
  def body = (size >> payload) ~ crc
  def crc = word
  def size = "\\d+".r ^^ (_.toInt)
  def payload = repN(_: Int, word)
  def word = "\\S+".r
  def dummy = word
}

И, используя его: 

scala> val stream = "a  b  start  3  1  2  3  4FAA  end  x  y  z "
stream: String = "a  b  start  3  1  2  3  4FAA  end  x  y  z "

scala> P.parse(P.message, stream)
res5: P.ParseResult[Any] = [1.35] parsed: (List(1, 2, 3)~4FAA)

Теперь RegexParsers анализирует поток Char. Поскольку у вас есть поток токенов, StandardTokenParsers может быть более подходящим классом. Или вы можете основать его на Parsers и определить Elem в соответствии с вашими потребностями.

2 голосов
/ 27 октября 2011

Я думаю, что есть много разных способов решить эту проблему.Для меня самым лучшим решением было бы следующее рекурсивное решение: 

def filterMessages(l:List[Any]):List[List[Any]] = {
    l match {
      case "start" :: tail => tail.takeWhile(_ != "end") :: filterMessages(tail.dropWhile(_ != "end"))
      case a :: tail => filterMessages(tail)
      case Nil  => Nil
    }
 }

Этот подход вернул бы: 

scala> val l = "a" :: "b" :: "start" :: 2 :: 1 :: 2:: "crc" :: "end" :: "a" :: "x"  ::  "start" :: 3 :: 1 :: 2 ::3 :: "crc" :: "end" :: "x" :: Nil
scala> println(filterMessages(l))
res0: List(List(2, 1, 2, crc), List(3, 1, 2, 3, crc))

Если у вас есть «очень длинный» (бесконечный) список, вы должны составитьэтот алгоритм хвостовой рекурсивен.Хвостово-рекурсивное решение выглядело бы так (дает тот же результат, что и выше): 

import scala.annotation.tailrec
@tailrec def filterMessages(l:List[Any], result:List[List[Any]]):List[List[Any]] = {
    l match {
      case "start" :: tail => filterMessages(tail.dropWhile(_ != "end"), tail.takeWhile(_ != "end") :: result)
      case a :: tail => filterMessages(tail, result)
      case Nil  => result
    }
  }

 scala> println(filterMessages(l, Nil))
 res0: List(List(2, 1, 2, crc), List(3, 1, 2, 3, crc))

В терминах обработки я бы передал функцию, которая обрабатывает сообщение, а не объединяет каждое сообщение в списке.Это решение будет выглядеть так: 

def processMessages(l: List[Any])(process: (List[Any]) => Unit): Unit = {
   l match {
      case "start" :: tail => process(tail.takeWhile(_ != "end")); processMessages(tail.dropWhile(_ != "end"))(process)
      case a :: tail => processMessages(tail)(process)
      case Nil => Nil
    }
}

Использование: 

scala> processMessages(l) { println }
2 голосов
/ 26 октября 2011

Грамматика, которую вы описали, обычный язык .Вероятно, лучше всего определить пользовательский объект экстрактора с помощью метода unapply, который может анализировать ваш список токенов в список ваших структур.

...