Defining a type in a recursive way in Dotty

Question
1

I want my List’s type parameters to be a mixture of a String, List[String], List[List[String]]…and so on.

With dotty’s union types I could defined List[String | List[String] | List[List[String]]...]. But then I will not be able to represent up to an infinite depth.

The following code gives illegal cyclic reference error

type Elem = String | List[Elem] //illegal cyclic reference error

def foo: List[Elem] = ???

Is it possible to represent such a type using the type system?

Edit

Examples of the list :

List("foo")
List("foo", List("foo", "baz"), "quux", List("qewrty", List("azerty")))
List(List(List(List("foo"))))
2

In scala 2 you can define something like

  sealed trait Elem
  final case class S(s:String) extends Elem
  final case class L(l: List[Elem]) extends Elem
3

true, you can do something similar using Enums in dotty as well. But I wanted to know if this can be directly using types.

4

An ADT defines types…

But I get your point, maybe it works using a type lambda?

However, note that union-types do not work to overcome erasure.
For example List[Int] | List[String] would erase to just List so it won’t work, for this kind of things an ADT is the best solution.

5

Just an idea, haven’t thought it through, may be nonsense… If this kind of data structure is central to your project(s), you might consider re-imagining List for this specific structure, something like (Scala 2):

sealed trait Nested[+T]
case object NNil extends Nested[Nothing]
case class Base[+T](value: T, link: Nested[T]) extends Nested[T]
case class Rec[+T](nested: Nested[T], link: Nested[T]) extends Nested[T]

This way you could avoid having both a List cons and an ADT instance per node, and it’d probably be easier to implement functionality dor traversal, folding, etc. on top. But this certainly would be considerable initial overhead and, again, I’m not really sure this makes sense at all…

1 Like
6

It wouldn’t surprise me if the answer is simple “no” – this sounds a bit problematic. But the one way I can think of it maybe working is with Match Types, which allow you to do non-trivial computation (including recursive computation) at compile time.

That said: is the shape of the objects known at compile time? That is, do you know at compile time that this specific val is a List[List[List[String]]], as opposed to merely a List[String]? If you only know that at runtime (which is more common for questions like this), then I believe the answer is a hard “no”, since Types are about compile-time knowledge, not runtime knowledge…

2 Likes
7

No, at compile time we do not know the type.

types are about compile-time knowledge, not runtime knowledge…

But then we are able to define it using and ADT.

8

I’ve found a weird workaround: https://scastie.scala-lang.org/AWO8pKQkSUSPgWmgSBp4gg

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

This is actually equivalent to

// illegal cyclic reference
type Rec[F[_], A] = A | F[Rec[F, A]]

But for some reason once you put it in a match type with at least 1 concrete case dotty suddenly stops complaining.

I guess there has to be a bug here somewhere. I think either both or neither should compile.

By the way you can also leave out F and only do List. That doesn’t change anything.

2 Likes
9

Wow, very interesting. In REPL, I get this

type Rec[F[_], A] = A match {
     |   case String => String | F[Rec[F, String]]
     |   case _ => A | F[Rec[F, A]]
     | }

scala> val a: Rec[List, String] = List("foo", List("goo", "zoo"), "baz")
val a: String | List[LazyRef(Rec[List, String])] = List(foo, List(goo, zoo), baz)

Notice the LazyRef in the type of a. I think that is what allows it to compile.

10

Does the puzzlers maintainer take scala3 puzzlers yet?

More seriously, maybe that warrants a bug report.

1 Like
11

Agreed https://github.com/lampepfl/dotty/issues/10136

1 Like