То, что вы описываете (и то, что вы более или менее заново изобрели в своей реализации с помощью foldLeft и ~), по сути является sequence для Хаскелла для монад (на самом деле вам нужен толькоаппликативный функтор, но это не имеет значения здесь).sequence принимает список монадических значений и возвращает монадический список значений.Parser - это монада, поэтому sequence для Parser изменит List[Parser[A]] на Parser[List[A]].
Scalaz даст вам sequence, но вне пределаЯ не знаю, есть ли хороший способ получить необходимый экземпляр Applicative для Parser.К счастью, вы можете довольно легко бросить свой собственный (я прямо перевожу определение Haskell ):
import scala.util.parsing.combinator._
object parser extends RegexParsers {
val integer = """\d+""".r
val counts = List(1, 2, 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)
}
Это дает нам List(List(1), List(2, 3), List(4, 5, 6)) для parser("1 2 3 4 5 6"), по желанию.
(Обратите внимание, что я использую RegexParsers здесь в качестве удобного законченного примера, но подход работает в более общем плане.)
То, что происходит, может быть немного яснее, если мы десугар forпонимание:
val line = parsers.foldRight(success(Nil: List[List[String]])) {
(current, acc) => current.flatMap(x => acc.map(x :: _))
}
Мы можем написать flatMap как into и map как ^^:
val line = parsers.foldRight(success(Nil: List[List[String]])) {
(current, acc) => current into (x => acc ^^ (x :: _))
}
Это не слишком далеко от вашей формулировки, кромечто мы используем правильное сгибание вместо реверса и не накапливаем и не разбиваем ~ s.
Об эффективности: Обе наши реализации приведут к неприятным стекам вызовов,По моему опыту, это просто факт жизни с комбинаторами парсера Scala.Процитируем другой ответ о переполнении стека, например:
Комбинаторы парсера Scala не очень эффективны.Они не были предназначены для.Они хороши для выполнения небольших задач с относительно небольшими входными данными.
Мой sequence -й подход решает «более читаемую» часть вашего вопроса и почти наверняка является самым чистым способом решенияпроблема с синтаксическим анализатором 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.