scala – 将组合解析器的列表/序列转换为单个解析器

parsers.foldLeft(success(Nil)){case (ps,p) => rs ~ p ^^ {case xs ~ x => x ::xs}} ^^ (_.reverse)

您正在描述的内容(以及您在使用foldLeft和?的实现中或多或少地重新创建的内容)本质上是Haskell的 sequence for monad(实际上您只需要一个应用程序仿函数,但这在此处无关紧要). sequence获取monadic值列表并返回monadic值列表.解析器是一个monad,因此Parser的序列会将List [Parser [A]]更改为Parser [List [A]].

Scalaz给出了序列,但是我不知道是否有一种很好的方法可以获得Parser所需的Applicative实例.幸运的是,你可以轻松地自己滚动(我直接翻译the Haskell definition)：

import scala.util.parsing.combinator._

object parser extends RegexParsers {
  val integer = """d+""".r

  val counts = List(1,3)
  val parsers = counts.map(repN(_,integer))

  val line = parsers.foldRight(success(Nil: List[List[String]])) {
    (m,n) => for { x <- m ; xs <- n } yield (x :: xs)
  }

  def apply(s: String) = parseAll(line,s)
}

根据需要,这给出了解析器(“1 2 3 4 5 6”)的List(List(1),List(2,3),List(4,5,6)).

(请注意,我在这里使用RegexParsers作为一个方便的完整示例,但该方法更常用.)

如果我们厌倦了理解,那么发生的事情可能会更清楚一些：

val line = parsers.foldRight(success(Nil: List[List[String]])) {
  (current,acc) => current.flatMap(x => acc.map(x :: _))
}

我们可以将flatMap写成并映射为^^：

val line = parsers.foldRight(success(Nil: List[List[String]])) {
  (current,acc) => current into (x => acc ^^ (x :: _))
}

这与你的配方相差不远,除了我们使用正确的折叠而不是倒转,并没有建立和打破~s.

关于效率：我们的两个实现都会导致令人不快的调用堆栈.根据我的经验,这只是Scala解析器组合器的生活现实.引用another Stack Overflow answer,例如：

Scala’s parser combinators aren’t very efficient. They weren’t
designed to be. They’re good for doing small tasks with relatively
small inputs.

我的序列方法解决了问题中“更具可读性”的部分,几乎可以肯定是使用Scala解析器组合器解决问题的最简洁方法.它的效率略高于您的实施,对于几千个左右的团体来说应该没问题.如果您需要处理更多,则必须在scala.util.parsing.combinator之外查看.我建议如下：

def parse(counts: Seq[Int],input: String): Option[Seq[Seq[Int]]] = {
  val parsed = try {
    Some(input.split(" ").map(_.toInt))
  } catch {
    case _ : java.lang.NumberFormatException => None
  }

  parsed.flatMap { ints =>
    if (ints.length != counts.sum) None
    else Some(counts.foldLeft((Seq.empty[Seq[Int]],ints)) {
      case ((collected,remaining),count) => {
        val (m,n) = remaining.splitAt(count)
        (m.toSeq +: collected,n)
      }
    }._1.reverse)
  }
}

没有保证,但在我的系统上,它不会在具有100k整数组的行上溢出.