DEV Community

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

Posted on • Edited on

Recursive Types

#scala #functional #adt

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.

Top comments (0)

Read next

prettysoul2025 profile image

Using Data to Drive Mental Health Outcomes

Pretty Soul -

cicubeteam profile image

Docker Swarm vs Kubernetes - A Deep Technical Analysis

CiCube -

himanshu_mishra_13 profile image

tutorials

Himanshu Mishra -

meetqy profile image

IPalettes - The Ultimate AI Color Palettes Generator

meetqy -