Define your own Scala reference class (recursive class)

Question

How to define this class in scala

data NestedList a = Elem a | List [NestedList a]

This in Haskell means that a NestedList is a type that can contain either an Elem or another NestedList. Is it possible to make such recursive definitions in scala?

This is actually what I'm trying to achieve

Note Issue 7 here on this page.

Update ....
Follwing answers below, I created the NestedList Trait and case classes for Elem and NList . Trying to implement flatten , I'm stuck here.

 def flatten[T](xs: NestedList[T]): List[T] = xs match{ case Elem(xs) => List(xs) //case NList //have to fill this case } 

Answer 1

Haskell's algebraic data types are idiomatically translated into sealed class hierarchies in Scala.

For instance:

 sealed abstract class List[+A] case class Nil extends List[Nothing] case class Elem[T](head: T, tail: List[T]) extends List[T] 

UPDATE

Thomas's answer shows a recursive type definition. However, it is interesting that you cannot make the NList case class. A type error is reported for the synthesized sameElements method used by equals . It looks like: https://lampsvn.epfl.ch/trac/scala/ticket/2867

It works, duplicate parameters are replaced by Seq :

 sealed trait NestedList[A] case class Elem[A](e : A) extends NestedList[A] case class NList[A](val e : Seq[NestedList[A]]) extends NestedList[A] 

Answer 2

That should work.

 sealed trait NestedList[A] case class Elem[A](val e : A) extends NestedList[A] case class NList[A](val e : Seq[NestedList[A]]) extends NestedList[A] def flatten[T](xs: NestedList[T]): Seq[T] = xs match{ case Elem(x) => List(x) case NList(xs) => xs flatMap (flatten(_)) } 

Answer 3

See 99 issues in Scala for Scala issue versions.

Related solution from this site:

 def flatten(ls: List[Any]): List[Any] = ls flatMap { case ms: List[_] => flatten(ms) case e => List(e) } 

Answer 4

 sealed abstract class NestedList[A] { def flatten: NList[A] } case class Elem[A](e: A) extends NestedList[A] { override def flatten = NList(Elem(e)) } case class NList[A](es: NestedList[A]*) extends NestedList[A] { override def flatten = NList(es flatMap (_.flatten.es): _*) }