gmane.comp.lang.scala.user

David Pollak | 16 Jan 01:14

Re: Re: unordered stuff in the parser combinator

def _rotate[T](in: List[T]): List[List[T]] = {
    def doIt(in: List[T], cnt: Int): List[List[T]] = (in, cnt) match {
      case (_, 0) => Nil
      case (x :: xs, cnt) => in :: doIt(xs ::: List(x), cnt - 1)
    }
    doIt(in, in.length)
}

def _permute[T](in: List[T]): List[List[T]] = in match {
    case Nil => Nil
    case x :: Nil => List(List(x))
    case xs => _rotate(xs).flatMap{case x :: xs => _permute(xs).map(x :: _) case _ => Nil}
}

def permute[T](p: (=> Parser[T])*): Parser[List[T]] = if (p.isEmpty ) success(Nil)
else {
    def doLine(in: List[(=> Parser[T])]): Parser[List[T]] = in match {
      case Nil => success(Nil)
      case x :: xs => x ~ doLine(xs) ^^ {case ~(x, xs) => x :: xs}
    }

    def doAll(in: List[List[(=> Parser[T])]]): Parser[List[T]] = in match {
      case x :: Nil => doLine(x)
      case x :: xs => doLine(x) | doAll(xs)
    }

    doAll(_permute(p.toList))
}

On 1/15/08, David Pollak <feeder.of.the.bears-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:

I'll have some code in a few minutes

On 1/15/08, Geoffrey Alan Washburn < geoffrey.washburn-p8DiymsW2f8@public.gmane.org > wrote:
Geoffrey Alan Washburn wrote:
> Matt Hellige wrote:
>> It's possible to write a permutation parser combinator in Haskell.
>> Here is the key:
>>   http://citeseer.ist.psu.edu/451549.html
>> It's not complex, but I haven't read the paper in depth, so I don't
>> know if it transfers trivially to Scala.
>
> Skimming the paper indicates that it requires higher-rank polymorphism
> (which *is not* the same as higher-kinded polymorphism, which Scala does
> provide).  So a trivial translation is out of the question.  It may be
> possible, but it will require some cleverness.

Nope, I misread it.  They were just using Haskell's forall quantifier
notation for what is really an existential type.  This should be
straightforward then.

--

lift, the secure, simple, powerful web framework http://liftweb.net
Collaborative Task Management http://much4.us

--
lift, the secure, simple, powerful web framework http://liftweb.net
Collaborative Task Management http://much4.us