用类型别名描述递归文法

Question

如何用类型别名来描述这个递归语法：

type FieldValue = Seq[String] :+: String :+: Int :+: Long :+: CNil
type FieldLeaf = FieldValue :+: SubField :+: CNil
type SubField = Seq[Field]
type Field = (String, FieldLeaf)

就目前而言，Scala 编译器 (2.12.1) 给我：

Error:(14, 25) illegal cyclic reference involving type FieldLeaf
  type Field = (String, FieldLeaf)

PS 上下文是用 fastparse.

解析递归文法

编辑（回应下面@OlivierBlanvillain 的回答）

这个答案真是太棒了，正是我一直在寻找的东西，我会记住它以备将来使用。

但是，由于其他原因，在这种特殊情况下，我不得不改用这些定义：

  case class Field(name: String, leaf: FieldLeaf)
  sealed trait FieldLeaf
  sealed trait FieldValue extends FieldLeaf
  case class StringsFieldValue(value: Seq[String]) extends FieldValue
  case class StringFieldValue(value: String) extends FieldValue
  case class IntFieldValue(value: Int) extends FieldValue
  case class LongFieldValue(value: Long) extends FieldValue
  case class SubField(value: Seq[Field]) extends FieldLeaf

另请参阅： Instantiate types from recursive type grammar

Answer 1

使用定点类型。例如：

case class Fix[F[_]](out: F[Fix[F]])

让你写：

type FieldValue = Seq[String] :+: String :+: Int :+: Long :+: CNil
type FieldLeaf[F] = FieldValue :+: SubField[F] :+: CNil
type SubField[F] = Seq[F]
type Field0[F] = (String, FieldLeaf[F])

type Field = Fix[Field0]

用类型别名描述递归文法

Describe recursive grammar with type aliases

scala

recursive-descent

recursive-datastructures

type-alias

fastparse