16 Jan 2008 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.

notation for what is really an existential type.  This should be
straightforward then.

--

lift, the secure, simple, powerful web framework http://liftweb.net