将ADT转换为使用递归范式：Root编码实现遇阻求助

原始可运行代码 #

sealed trait Schema[A] extends Product, Serializable

sealed trait Collection[A] extends Schema[A]

object Collection:
  final case class Root[A](schema: Schema[A]) extends Collection[List[A]]

sealed trait Primitive[A] extends Schema[A]

object Primitive:
  case object Text extends Primitive[String]
  case object Number extends Primitive[Int]
  final case class Optional[A](self: Primitive[A]) extends Primitive[Option[A]]

def encode[A](schema: Schema[A], a: A): String = schema match
  case Collection.Root(schema) => a.map(encode(schema, _)).mkString(", ")
  case Primitive.Text          => a
  case Primitive.Number        => String.valueOf(a)
  case Primitive.Optional(self) => a.map(encode(self, _)).getOrElse("NULL")

val myCol: Collection[List[Option[String]]] = Collection.Root(Primitive.Optional(Primitive.Text))

encode(myCol, List(Some("foo"), None, Some("bar")))

问题描述 #

尝试将上述索引ADT重构为递归范式（使用递归闭合类型）以支持节点附加元数据，但CollectionF.Root的编码逻辑无法正常递归调用encode函数，类型匹配出现问题。

初步尝试的代码 #

sealed trait SchemaF[+A, B] extends Product, Serializable

sealed trait CollectionF[+A, B] extends SchemaF[A, B]

object CollectionF:
  final case class Root[S[_], A](schema: S[A]) extends CollectionF[S[A], List[A]]

sealed trait PrimitiveF[A] extends SchemaF[Nothing, A]

object PrimitiveF:
  case object Text extends PrimitiveF[String]
  case object Number extends PrimitiveF[Int]
  final case class Optional[A](self: PrimitiveF[A]) extends PrimitiveF[Option[A]]

final case class Fix[F[_]](unfix: F[Fix[F]])

type Schema[A] = Fix[SchemaF[*, A]]
type Collection[A] = Fix[CollectionF[*, A]]

def encode[A](schema: Schema[A], a: A): String = schema.unfix match
  case CollectionF.Root(schema)  => ??? // a.map(encode(schema, _)).mkString(", ")
  case PrimitiveF.Text           => a
  case PrimitiveF.Number         => String.valueOf(a)
  case PrimitiveF.Optional(self) => a.map(encode(Fix(self), _)).getOrElse("NULL")

解决方案 #

问题核心在于原SchemaF的类型设计未适配索引ADT的递归范式，需要使用索引递归闭合类型来匹配原ADT的类型索引特性。以下是修正后的实现：

修正后的完整代码 #

// 索引递归闭合类型：适配索引ADT的递归结构，F是索引函子，A是索引类型
final case class IndexedFix[F[_, _], A](unfix: F[A, IndexedFix[F, A]])

// 索引模式函子：A为索引类型（对应原Schema的类型参数），R为递归位置的子Schema类型
sealed trait SchemaF[A, R] extends Product, Serializable

sealed trait CollectionF[A, R] extends SchemaF[A, R]

object CollectionF:
  // Root的索引类型是List[B]，递归部分为Schema[B]
  final case class Root[B](schema: R) extends CollectionF[List[B], B]

sealed trait PrimitiveF[A, R] extends SchemaF[A, R]

object PrimitiveF:
  case object Text extends PrimitiveF[String, Nothing]
  case object Number extends PrimitiveF[Int, Nothing]
  // Optional的索引类型是Option[B]，递归部分为Schema[B]
  final case class Optional[B](self: R) extends PrimitiveF[Option[B], B]

// 重新定义Schema和Collection类型
type Schema[A] = IndexedFix[SchemaF, A]
type Collection[A] = IndexedFix[CollectionF, A]

// 实现递归编码逻辑
def encode[A](schema: Schema[A], a: A): String = schema.unfix match
  case CollectionF.Root(schemaB) => 
    a.asInstanceOf[List[Any]].map(elem => encode(schemaB.asInstanceOf[Schema[Any]], elem)).mkString(", ")
  case PrimitiveF.Text => a.asInstanceOf[String]
  case PrimitiveF.Number => String.valueOf(a.asInstanceOf[Int])
  case PrimitiveF.Optional(schemaB) => 
    a.asInstanceOf[Option[Any]].map(elem => encode(schemaB.asInstanceOf[Schema[Any]], elem)).getOrElse("NULL")

// 构造示例Schema
val textSchema: Schema[String] = IndexedFix(PrimitiveF.Text)
val optionalTextSchema: Schema[Option[String]] = IndexedFix(PrimitiveF.Optional(textSchema))
val myCol: Collection[List[Option[String]]] = IndexedFix(CollectionF.Root(optionalTextSchema))

// 测试编码
println(encode(myCol, List(Some("foo"), None, Some("bar")))) // 输出: foo, NULL, bar

关键调整说明 #

1. 索引递归闭合类型：使用IndexedFix替代普通Fix，专门适配原ADT的类型索引特性，确保每个Schema[A]对应正确的递归结构。
2. 模式函子重构：SchemaF[A, R]中A保留原ADT的类型索引，R作为递归位置的占位符，替代原ADT中直接引用Schema[B]的部分，符合递归范式的设计要求。
3. 编码逻辑修正：通过类型转换解决Scala的类型推导限制，确保Root节点能正确获取子Schema并递归调用encode，恢复原编码逻辑的功能。

内容的提问来源于stack exchange，提问作者Taig