DEV Community

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

Posted on • Updated 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

lukehinds profile image

Contributing Minder to the OpenSSF, out of a deep belief in the power of the open source community

Luke Hinds -

eidivandi profile image

Personal Use of AWS Organizations Using CDK

Omid Eidivandi -

shafayeat profile image

Building a Self-Evolving Codebase: JavaScript’s AST Manipulation and Dynamic Compilation

Shafayet Hossain -

ahmed_shah_bca0d5a0c41485 profile image

DIY Leather Jacket Customization Ideas for Men

Ahmed Shah -