import scala.util.parsing.combinator1.Parsers

/*
The goal is to provide combinators to parse any permutation of a given
set of parsers, in a type-safe way and providing results in a consistent
order. These two requirements are of course related, since type safety 
will require that results are in a predictable order. We can achieve this,
with a couple of major shortcomings. I don't know whether it's possible
to eliminate the shortcomings, but I still hope that it is.

The implementation is a translation of the Haskell version in this paper:
  http://citeseer.ist.psu.edu/451549.html

Here is an example usage:
  [~/test]% scalac PermParsers.scala 
  [~/test]% scala Test '(abc)'
  [1.6] parsed: (a,b,c)
  [~/test]% scala Test '(bca)'
  [1.6] parsed: (a,b,c)

I'll show the sample code first. The implementation follows.
*/
import scala.util.parsing.input.CharArrayReader

object Test extends Parsers with PermParsers {
  type Elem = Char
  def tup3[A,B,C] = (a:A) => (b:B) => (c:C) => (a,b,c)
  def phrase = '(' ~> permute(tup3 ~~ 'a' ~~ 'b' ~~ 'c') <~ ')'
  def parse(s: String) = println(phrase(new CharArrayReader(s.toCharArray)))
  def main(args: Array[String]) = parse(args(0))
}

/*
Now the implementation. We provide these combinators as an option that
can be mixed into the standard Parsers trait.

The main thing to note is that efficiency has *not* been my concern. The
Haskell version will lazily unfold the permutation tree, while this version
constructs it in advance. While it's probably possible to change this in a
fairly non-invasive way, I'm not yet satisfied enough with the approach to
investigate.

The other interesting difference is that we use implicit definitions to 
provide syntactic sugar, since it's not possible to define infix operations
in Scala other than as methods.
*/
trait PermParsers { this: Parsers =>
  /*
  Define the permutation tree. See the original paper for discussion.
  Note that in Scala, we define the map functions more idiomatically as
  methods on the tree. Note also that the existential type, which is 
  part of the Branch declaration in Haskell, is moved into the definition
  of Choice. It's very awkward to try to share an existential across 
  multiple constructor parameters in Scala, and even so I had problems
  getting the existential to work when declared that way. When declared
  like this, it works as expected.
  */
  trait Perms[A] {
    def map[B](f: A => B): Perms[B]
  }
  case class Empty[A](a: A) extends Perms[A] {
    def map[B](f: A => B): Perms[B] = Empty(f(a))
  }
  case class Choice[A](chs: List[Branch[A,X] forSome {type X}])
      extends Perms[A] {
    def map[B](f: A => B): Perms[B] = Choice(chs.map(_.map(f)))
  }
  case class Branch[A,X](sub: Perms[X => A], p: Parser[X]) {
    def map[B](f: A => B): Branch[B,Y] forSome { type Y } =
      Branch(sub.map(f.compose(_)), p)
  }

  /*
  We'll need this standard combinator.
  */
  def flip[A,B,C](f: A => B => C): B => A => C = (b => (a => (f(a)(b))))   

  /*
  Add a parser to a permutation tree. Note that the type annotation on flip
  is necessary. Otherwise it's as in the paper.
  */
  def add[A,B](a: Perms[A=>B], p: Parser[A]): Perms[B] = a match {
    case t @ Empty(a) => Choice(List(Branch(t, p)))
    case t @ Choice(chs) => {
      val first = Branch(t, p)
      def insert[X](br: Branch[A=>B,X]) = br match {
        case Branch(sub, px) => Branch(add(sub.map(flip[X,A,B]), p), px)
      }
      val others = chs.map(insert(_))
      Choice(first :: others)
    }
  }

  /*
  A parser combinator corresponding to applicative functor application. I'm
  surprised this is not in the standard library, but it's more idiomatic
  in Haskell than Scala... In any case, we'll need it.
  */
  def app[A,B](pf: Parser[A=>B], p: Parser[A]): Parser[B] = pf >> (f => p ^^ f)

  /*
  Finally, convert a permutation tree to a parser. This is the *inefficient*
  version from the paper. I can't be bothered to think about efficiency yet,
  and this version is easier to define. In any case, without introducing 
  laziness, I don't think it matters. Again, the type annotation is 
  necessary.
  */
  def permute[A](ps: Perms[A]): Parser[A] = ps match {
    case Empty(a) => success(a)
    case Choice(chs) =>
      val newchs = chs map { case Branch(sub, p) => app(permute(sub), p) }
      (newchs :\ (failure("no valid permutation"):Parser[A])) (_ | _)
  }

  /*
  The following definitions provide the syntactic sugar. Since ~~ is defined
  only on Perms[A=>B], it's not possible to put it directly in Perms. So
  we instead define implicit conversions at the appropriate types.
  */
  class Addable[A,B](ps: Perms[A=>B]) {
    def ~~(p: Parser[A]): Perms[B] = add(ps, p)
  } 
  implicit def functionIsAddable[A,B](f: A=>B): Addable[A,B] =
    new Addable(Empty(f))
  implicit def permsIsAddable[A,B](ps: Perms[A=>B]): Addable[A,B] = 
    new Addable(ps)
}