CODEWITHSUNDEEP
scalatypes
jedesah
jedesah

Reputation: 3033

Is it possible to express the following in Scala "type test = Either[List[test], T]"

Is it possible to express recursive type definitions like the following in Scala?

type test = Either[List[test], Int]

UPDATE

My intention is to express a function like the following:

def flatten[T](list: List[Either[List[T], T]]): List[T] = list flatMap {
    case Left(list)         => list
    case Right(element) => List(element)
}

but that accepts a similar structure of arbitrary depth

Upvotes: 2

Views: 190

Answers (2)

Petr
Petr

Reputation: 63409

You cannot have a recursive type alias like that. But if you create a separate class, it's no problem:

case class Test[+T](value: Either[List[Test[T]], T]) {
  def flatten: List[T] = value match {
    case Left(list)         => list.flatMap(_.flatten);
    case Right(element)     => List(element);
  }
}

(Most interesting classes in programming are actually recursive.)

The reason why you cannot have a recursive type alias like yours is that the compiler needs to expand type aliases in order to tell if something has the type or not. But a recursive type alias like 

type test = Either[List[test], Int]

expands to infinity:

Either[List[test], Int]
Either[List[Either[List[test], Int]], Int]
Either[List[Either[List[Either[List[test], Int]], Int]], Int]
...

With classes, this doesn't happen, because the class "wraps" recursive values into something with a well defined type (like Test[T] in this example). The "expansion" of types only happens if you reference something that's inside (value in this case).

Upvotes: 1

Luigi Plinge
Luigi Plinge

Reputation: 51109

Well, you can do this:

type test[T <: test[T]] = Either[List[T], Int]

scala> val x: test[Nothing] = Right(1)
x: test[Nothing] = Right(1)

scala> val y: test[test[Nothing]] = Left(List(x))
y: test[test[Nothing]] = Left(List(Right(1)))

scala> val z: test[_] = y
z: test[_] = Left(List(Right(1)))

Not sure why you'd want this though.

Upvotes: 3

Related Questions