Support recursive types/schemas

[ex-ratt]

I want to discuss recursion (again) - specifically if this would be a welcome feature in Vulcan and if so, how it should be implemented.

Currently it is somewhat possible to create a recursive codec, but with caveats: You use shapeless's Lazy together with Codec.instance, which is deprecated, and have to supply the schema manually. It would be great if Vulcan would support recursive codecs and data structures out of the box, but I'm not sure everyone would agree.

I created a proof-of-concept for how such a support might look like to see which trade-offs there are. It uses shapeless's Lazy and ideas from avro4s.

• The schema of record codecs and everything that could contain a record cannot be created eagerly, which means that the codec is created even if the schema creation would fail - so it is not guaranteed to have a valid schema if the generated codec isn't a Fail.
• Codec.validate and Codec.Validated aren't possible for the same reason.
• It makes use of WeakTypeTag - TypeTag would be better, but it doesn't work with nested classes. Every type argument needs a WeakTypeTag in the current implementation, otherwise there might be a stack overflow (see vulcan.examples.Tree). I don't currently know how to detect whether there are type arguments in the type, because then we could fail early. I hope that there is a better solution (avro4s doesn't have this problem, because it always uses macros to generate type classes).

1. Should Vulcan support recursive data structures and are the trade-offs worth it? An old issue of the original author seems to dismiss it and I don't know whether it is compatible with the ideas for Vulcan 2.0.
2. How should it be implemented? Specifically, (a) is relying on shapeless a good idea, (b) is there a better solution than what I did by copying ideas of avro4s, and (c) how to circumvent the WeakTypeTag problem mentioned above?

Edit: After seeing section Recursive ADTs of the circe documentation, I experimented with another slightly different proof-of-concept. It turns out that Lazy wasn't quite necessary, because the codecs of fields are lazily evaluated, anyway. But the Tree example then needed Defer, just like in the circe documentation. I like this version a bit better, but it introduces another subtype of Codec.