General type parameter for nested lists

Question

I'm trying to write a parser which should parse a Prolog list (for example [1,2,3,4]) into the corresponding Scala List. I programmed the parser with Scalas parsing combinators.

My parser looks like this so far:

class PListParser extends JavaTokenParsers{
    def list:Parser[List[Any]] = "[" ~> listArgs <~ "]"
    def listArgs:Parser[List[Any]] = list | repsep(args, ",")
    def args:Parser[String] = "(.)*".r
}

Is there any possibility to turn the type parameters of the first two parsers into something more specific? Like a general parameter for nested lists of arbitrary dimension but the same underling type.

Answer 1

I think it should be trees, that is the proper structure for lists nested to arbitrary depth

sealed trait Tree[A]
case class Leaf[A](value: A) extends Tree[A] {
  override def toString: String = value.toString
}
case class Node[A](items: List[Tree[A]]) extends Tree[A] {
  override def toString: String = "Node(" + items.mkString(", ") + ")"
}

(Do the toString as you like, but I think the default one are rather too verbose)

Then, with minor fixes to your grammar (+ parse method, just to test easily on REPL)

object PrologListParser extends JavaTokenParsers{
    def list:Parser[Tree[String]] = "[" ~> listArgs <~ "]"
    def listArgs:Parser[Tree[String]] = repsep(list | args, ",") ^^ {Node(_)}
    def args:Parser[Tree[String]] = """([^,\[\]])*""".r ^^ {Leaf(_)}
    def parse(s: String): ParseResult[Tree[String]] = parse(list, s)
}


PrologListParser.parse("[a, b, [c, [d, e], f, [g], h], [i, j], k]")

res0: PrologList.ParseResult[Tree[String]] = [1.42] parsed: Node(a, b, Node(c, Node(d, e), f, Node(g), h), Node(i, j), k)