Search code examples
scalarecursive-datastructuresrecursive-descenttype-aliasfastparse

Describe recursive grammar with type aliases

How can I describe this recursive grammar with type aliases:

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

As it stands, the Scala compiler (2.12.1) gives me:

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

PS the context of this is parsing a recursive grammar with fastparse.

Edit (in response to @OlivierBlanvillain's answer below)

That answer was really a thing of beauty and exactly what I was looking for, I'll remember it for the future.

However, for other reasons, in this particular case I had to go with these definitions instead:

  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

See also: Instantiate types from recursive type grammar

Solution

  • Use a fix point type. For example:

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

    Lets you write:

    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]