1

Scala 如何“希望”我定义s-expr？在英语中，我们递归地定义 s-expr，如下所示：“一个 s-expr 要么是一个原子，要么是一个 s-expr 的列表。” 你在 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也可能不适合这个，从那时起我必须区分Leftand Right，这是无关紧要的。

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

4

3 回答 3

2

此链接以下列形式描述了用于 S 表达式的 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 类型的参数。

于 2016-01-15T22:14:43.803 回答
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")
 }
于 2016-01-15T00:18:18.613 回答
0

问题不type List[Sexpr] = Sexpr在于你认为它的意思。List是您使用类型参数而不是类定义的类型别名List。因此，当您尝试将其作为List（类）进行模式匹配时，它会失败。写起来也没什么不同type L[Sexpr] = Sexpr

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

一个 s 表达式被经典地定义 [1] 为

  1. 一个原子，或
  2. (x . y) 形式的表达式，其中 x 和 y 是 s 表达式。

在 ScalaList中，x不是List(in x :: y)，它不符合上述定义。S-表达式比链表更通用，是一种二叉树。ScalaList是一种特殊类型的 S 表达式，其中每对的第一个纵坐标是一个原子，但并非所有 S 表达式都适合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
于 2016-01-15T00:42:27.400 回答