Search code examples
scalatypess-expression

Idiomatic way to define s-expr in Scala

How does Scala "want" me to define s-expr? In English, we define s-expr recursively, like this: "An s-expr is either an atom or a list of s-exprs." How do you say that in Scala?

I'm pretty sure this is wrong:

// Scala 2.11.2
trait Sexpr

case class Atom(text: String) extends Sexpr

type List[Sexpr] = Sexpr  // To my amazement, the compiler accepts this!

val blah = Atom("blah")

def matchtest(sexpr: Sexpr): Unit = sexpr match  {
  case blah :: Nil => println(blah)  // But the compiler won't accept this
  case _ => println("no match")
}

matchtest(List(Atom("blah")))

Either is probably not a good fit for this, either, since then I'd have to distinguish between Left and Right, which is beside the point.

How do you make a recursive class definition like this so that it works nicely with the rest of Scala?

Solution

  • The problem is type List[Sexpr] = Sexpr is not what you think it means. List is a type alias that you have defined with a type parameter, and not the List class. So when you attempt to pattern match it as a List (the class), it fails. It would be no different to write type L[Sexpr] = Sexpr

    You need to define your own list type. Using scala.collection.immutable.List isn't correct, though. According to the wikipedia definition:

    an s-expression is classically defined[1] inductively as

    1. an atom, or
    2. an expression of the form (x . y) where x and y are s-expressions.

    In a Scala List, x is not a List (in x :: y), which does not fit the above definition. An S-expression is more general than a linked list, and is a type of binary tree. A Scala List is a particular type of S-expression where the first ordinate of each pair is an atom, but not all S-expressions fit into a List.

    It should look more like this:

    sealed trait SExpr[+A]

case object NilAtom extends SExpr[Nothing]

case class Atom[+A](a: A) extends SExpr[A]

case class Pair[+A](a1: SExpr[A], a2: SExpr[A]) extends SExpr[A]

def matchTest[A](sexpr: SExpr[A]): Unit = sexpr match  {
  case Pair(a1, a2) => println("Not an Atom")
  case _ => println("Atom")
}

    Usage:

    scala> matchTest(Pair(Atom("Test"), NilAtom))
Not an Atom

scala> matchTest(Atom("Test"))
Atom