Tilde-class in parser combinators

#1

Hi all,

I like to understand the tilde-class that is used in the parser combinator library. For example the Programming in Scala book gives

case class ~[+A, +B](x: A, y: B) {
override def toString = “(”+ x +"~"+ y +")"
}

to be able to use pattern matching like case x ~ y ~ z, instead of ((x, y), z).

Unfortunately, I am unable to replicate this in my own code for my own parser combinators. I used so far for the following abstract parser class and the sequence parser code:

abstract class Parser[I, T](implicit ev: I => Seq[_]) {
def parse(ts: I): Set[(T, I)]

def parse_all(ts: I) : Set[T] =
for ((head, tail) <- parse(ts); if (tail.isEmpty)) yield head
}

class SeqParser[I, T, S](p: => Parser[I, T],
q: => Parser[I, S])(implicit ev: I => Seq[_]) extends Parser[I, (T, S)] {
def parse(sb: I) =
for ((head1, tail1) <- p.parse(sb);
(head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2)
}

I added the ~-class above, and then modified the return type of the Parser to be of the form
Parser[I, ~[T, S]]. But then how do I have to change the code for what to return in the yield
expression? Both, ~(head1, head2) and head1 ~ head2, give errors.

My question is how do I have to do this properly such that I can later use x ~ y ~ z for pattern-matching parser results.

Thanks a lot!
Christian

#2

Not sure why exactly, but due to the “tilde”(~) name, the case class’ #apply() doesn’t seem to be accessible/recognized by the compiler - you’ll have to use new. (parser-combinators does the same internally.)

// type is '~[~[Int, String], Double]', or short: 'Int ~ String ~ Double'
new ~(new ~(42, "x"), 3.14)
#3

Oh great! Thanks so much!
I would have never figured this one out on my own.
What you suggest works perfectly.

Christian

#4

That’s the darndest thing. Does anyone here offhand know if that’s a bug in the implementation, if so, if there is a report for it, and if this is as specced, where and why it’s specced like that?

#5

It’s because the compiler transforms ~(x, y) to (x, y).unary_~. Unfortunately that transformation conflicts with methods, or objects with an apply method, named ~. It probably already happens in the parser which makes this hard to fix, if it would require fixing.