在 Scala 中定义 s-expr 的惯用方式

Question

Scala "want" 我如何定义 s-expr？在英语中，我们递归地定义 s-expr，像这样："An s-expr is either an atom or a list of s-exprs." How do you say that in Scala?

我很确定这是错误的：

// 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 可能也不适合这个，从那时起我必须区分 Left 和 Right，这是题外话。

如何创建这样的递归 class 定义，以便它与 Scala 的其余部分很好地协同工作？

Answer 1

可能是这样的

 trait Sexpr
 case class Atom(text: String) extends Sexpr
 case class SList(list: Iterable[Sexpr]) extends Sexpr

 def matchtest(sexpr: Sexpr): Unit = sexpr match {
    case SList(blah :: Nil) => println(blah)
    case _ => println("no match")
 }

Answer 2

问题是type List[Sexpr] = Sexpr不是你想的那个意思。 List 是您使用类型参数定义的类型别名，不是 List class。因此，当您尝试将其模式匹配为 List（class）时，它会失败。写 type L[Sexpr] = Sexpr

也没什么不同

您需要定义自己的列表类型。但是，使用 scala.collection.immutable.List 是不正确的。根据维基百科定义：

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

an atom, or

an expression of the form (x . y) where x and y are s-expressions.

在 Scala List 中，x 不是 List（在 x :: y 中），这不符合上述定义。 S-expression 比链表更通用，是二叉树的一种。 Scala List 是 S-expression 的 特定类型 ，其中每对的第一个纵坐标是一个原子，但并非所有 S-expression 都适合List.

它应该看起来更像这样：

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")
}

用法：

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

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

Answer 3

此 link 以下列形式描述了 S-expresions 的 Scala 解析器：

abstract class SExp
case class SInt(val value : Int) extends SExp { ... }
case class SSymbol(val value : String) extends SExp { ...}
case class STrue() extends SExp { ... }
case class SFalse() extends SExp { ... }
case class SCons(val car : SExp, val cdr : SExp) extends SExp { ... }
case class SNil() extends SExp { ... }

正如另一个答案所观察到的，看起来像列表的东西实际上是二叉树的一种形式，正如显式 SNil 和 SCons 所显示的那样，它们采用 SExp 类型的参数。

在 Scala 中定义 s-expr 的惯用方式

Idiomatic way to define s-expr in Scala

scala

types

s-expression