how to define new type including itself?

Question

In scala I am wondering if there is a way I can define a new type including itself For example

type A = Tuple(e1: Int, e2: A)

Ofcourse type A = List[A] is illegal so is there another way to do this?

I tried doing this with type Any and Option but it didn't go well, and I am not sure this is a right way to do this

Answer 1

You can try

sealed trait A
case class Tuple(e1: Int, e2: A) extends A

Now there is no way to construct a value of type A (not using null) so you should add a "leaf" besides the "fork" Tuple.

Infinite recursive type type A = Tuple[Int, A] is forbidden

case class Tuple[A, B](e1: A, e2: B)

type A = Tuple[Int, A] // doesn't compile
//A is already defined as type A

For recursive calculations on types you can use type projections

trait AddOneLevel[A] {
  type Out = Tuple[Int, A]
}

type X[A] = AddOneLevel[AddOneLevel[AddOneLevel[A]#Out]#Out]#Out

type A
implicitly[X[A] =:= Tuple[Int, Tuple[Int, Tuple[Int, A]]]] // compiles

and

sealed trait Nat {
  type This <: Nat
  type ++ = Succ[This]
  type AddNLevels[A]
}
class Succ[N <: Nat] extends Nat {
  type This = Succ[N]
  type AddNLevels[A] = Tuple[Int, N# AddNLevels [A]]
}
object Zero extends Nat {
  type This = Zero
  type AddNLevels[A] = A
}
type Zero  = Zero.type
type One   = Succ[Zero]
type Two   = Succ[One]
type Three = Succ[Two]

implicitly[Three# AddNLevels [String] =:= Tuple[Int, Tuple[Int, Tuple[Int, String]]]] // compiles

Another option is type classes

import shapeless.Lazy

trait AddOneLevel[A] {
  type Out
}
object AddOneLevel {
  type Aux[A, Out0] = AddOneLevel[A] {type Out = Out0}

  implicit def recurse[A, B](implicit
    aol: /*=>*/ Lazy[AddOneLevel.Aux[A, B]]
  ): Aux[A, Tuple[Int, B /*aol.value.Out*/]] = null

  implicit def base[A]: Aux[A, Tuple[Int, A]] = null
}

implicitly[AddOneLevel.Aux[String, Tuple[Int, String]]] // compiles
implicitly[AddOneLevel.Aux[String, Tuple[Int, Tuple[Int, String]]]] // compiles
implicitly[AddOneLevel.Aux[String, Tuple[Int, Tuple[Int, Tuple[Int, String]]]]] // compiles

(For some reason Scala 2.13 by-name implicits => and path-dependent type aol.value.Out do not work in 2.13.10: 1 2).

In Scala 3 you can use match types and compile-time operations

import scala.compiletime.ops.int.-

type AddNLevels[A, N <: Int] = N match {
  case 0 => A
  case _ => Tuple[Int, AddNLevels[A, N - 1]]
}

summon[AddNLevels[String, 3] =:= Tuple[Int, Tuple[Int, Tuple[Int, String]]]] // compiles

Answer 2

The problem seems to be a confusion between types and classes. The original example is not a valid type declaration, and looks much more like a class declaration.

The closest (invalid) type declaration would be

type A = Tuple2[Int, A]

The class declaration would look like this:

class A(e1: Int, e2: A)

This is valid but not particularly useful as you need an instance of A to create an A and have to resort to null to get started.