DEV Community

Cover image for Recursive Types
Montegasppα Cacilhας
Montegasppα Cacilhας

Posted on • Edited on

1 1

Recursive Types

Original post in Kodumaro.


I was around with a cyclic reference issue in Scala: JSON representation.

I was using Gson for serialising and deserialising (ain’t going in details), but how to represent the models inside the language ecosystem?

I could follow the Gson documentation and use pojos (case classes are great for it), but I was in need of something more flexible.

I decided to use language primitives, like integers, strings, big numbers, and so one.

So I created some types for deal with that:

type unroll[+A] = A
type JValue = unroll[_ <: Any]
type JArray = Seq[JValue]
type JObject = String Map JValue
Enter fullscreen mode Exit fullscreen mode

Not bad, I can hold complex objects in JValue variables:

val data: JValue = Map(
  "x" -> 3,
  "y" -> 4,
  "name" -> "test",
  "list" -> Seq("zero", 1, 2, 3, true),
)
Enter fullscreen mode Exit fullscreen mode

But odd things started to happen, like:

val element: JValue = <data>This is an XML node</data>
Enter fullscreen mode Exit fullscreen mode

It should crash! But doesn’t, since NodeSeq is Any’s subclass.

I needed something stricter.

Enter Dotty

Now I’ve tried Scala 3, codename Dotty.

My first unsuccessful attempt was:

type JNull = Unit
type JValue = Int | BigDecimal | String | Boolean | JNull | Seq[JValue] | String Map JValue
Enter fullscreen mode Exit fullscreen mode

And Dotty put a damper on my plans:

Illegal cyclic type reference: alias Map[Int | BigDecimal | String | Boolean | JNull | Seq[JValue] | String, JValue] of type JValue refers back to the type itself.

Then I hit this strange solution:

type Rec[F[_], A] = A match {
  case Int => Int | F[Rec[F, Int]]
  case _ => A | F[Rec[F, A]]
}
Enter fullscreen mode Exit fullscreen mode

Jasper M is suggesting taking advantage of the Scala type erasure to create a runtime LazyRef. So I followed the advice:

type JNull = Unit
type JPrimitive = Int | BigDecimal | String | Boolean | JNull

type Rec[JArray[_], JObject[_], A] = A match
  case JPrimitive => JPrimitive | JArray[Rec[JArray, JObject, JPrimitive]] | JObject[Rec[JArray, JObject, JPrimitive]]
  case _          => A          | JArray[Rec[JArray, JObject, A]]          | JObject[Rec[JArray, JObject, A]]

type JValue = Rec[Seq, [A] =>> String Map A, JPrimitive]
Enter fullscreen mode Exit fullscreen mode

And vois la! It works pretty well!

// Okay, unit represents null
var x: JValue = ()

// Also okay
x = true

// OMG! Still okay!
x = Map(
  "x" -> 3,
  "y" -> 4,
  "name" -> "test",
  "list" -> Seq("zero", 1, 2, 3, true),
)

// It throws an exception
x = <data>nope</data>

// If -Yexplicit-nulls is enabled, it throws an exception too
x = null
Enter fullscreen mode Exit fullscreen mode

Now the JValue is quite stricter, and the WeakRef made the recursive type possible.

👋 One thing before you go

Tired of spending so much on your side projects? 😒

We have created a membership program that helps cap your costs so you can build and experiment for less. And we currently have early-bird pricing which makes it an even better value! 🐥

Just one of many great perks of being part of the network ❤️

Top comments (0)

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay