I have this data structure, that I’d like to introduce recursion schemes to in order to attach metadata to nodes:

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

https://scastie.scala-lang.org/HmQyQ4vpSbaOyZzIXboYoA

My naive approach with little experience, looks like this:

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

https://scastie.scala-lang.org/qv3uaisEQvCJbS0qtW7NWw

But unfortunately, I can’t get it to work with the Root[S[_], A](schema: S[A]) encoding.