StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>What you're describing (and what you've more or less reinvented in your implementation with <code>foldLeft</code> and <code>~</code>) is essentially Haskell's <a href="http://haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad.html" rel="nofollow noreferrer"><code>sequence</code></a> for monads (really you only need an applicative functor, but that's irrelevant here). <code>sequence</code> takes a list of monadic values and returns a monadic list of values. <code>Parser</code> is a monad, so <code>sequence</code> for <code>Parser</code> would change a <code>List[Parser[A]]</code> into a <code>Parser[List[A]]</code>.</p> <p><a href="http://code.google.com/p/scalaz/" rel="nofollow noreferrer">Scalaz</a> gives you <code>sequence</code>, but off the top of my head I don't know if there's a nice way to get the necessary <code>Applicative</code> instance for <code>Parser</code>. Fortunately you can roll your own pretty easily (I'm directly translating <a href="http://haskell.org/ghc/docs/latest/html/libraries/base/src/Control-Monad.html#sequence" rel="nofollow noreferrer">the Haskell definition</a>):</p> <pre><code>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) } </code></pre> <p>This gives us <code>List(List(1), List(2, 3), List(4, 5, 6))</code> for <code>parser("1 2 3 4 5 6")</code>, as desired.</p> <p>(Note that I'm using <code>RegexParsers</code> here as a convenient complete example, but the approach works more generally.)</p> <p>What's going on might be a little clearer if we desugar the <code>for</code> comprehension:</p> <pre><code>val line = parsers.foldRight(success(Nil: List[List[String]])) { (current, acc) => current.flatMap(x => acc.map(x :: _)) } </code></pre> <p>We can write <code>flatMap</code> as <code>into</code> and <code>map</code> as <code>^^</code>:</p> <pre><code>val line = parsers.foldRight(success(Nil: List[List[String]])) { (current, acc) => current into (x => acc ^^ (x :: _)) } </code></pre> <p>This isn't too far from your formulation, except that we're using a right fold instead of reversing and aren't building up and breaking down the <code>~</code>s.</p> <hr> <p>About efficiency: Both of our implementations are going to result in unpleasant call stacks. In my experience this is just a fact of life with Scala's parser combinators. To quote <a href="https://stackoverflow.com/questions/6011141/scala-parser-combinators-vs-antlr-java-generated-parser/6011722#6011722">another Stack Overflow answer</a>, for example: </p> <blockquote> <p>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.</p> </blockquote> <p>My <code>sequence</code>-y approach addresses the "more readable" part of your question, and is almost certainly the cleanest way to solve the problem with Scala's parser combinators. It's marginally more efficient than your implementation, and should be fine for a few thousand groups or so. If you need to handle more than that, you'll have to look outside of <code>scala.util.parsing.combinator</code>. I'd recommend something like the following:</p> <pre><code>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) } } </code></pre> <p>No guarantees, but on my system it doesn't overflow on a line with 100k integer groups.</p> <hr>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload