CODEWITHSUNDEEP
scala
mushroom
mushroom

Reputation: 6289

How should an invariant List be implemented in Scala?

I want to implement a linked list in Scala where the type parameter is invariant, unlike the standard library List.

Here is an attempt:

sealed trait InvariantList[T]
case object Nil extends InvariantList[_]
case class Cons[T](head : T, tail : InvariantList[T]) extends InvariantList[T]

object InvariantList {
  def map[A, B](xs : InvariantList[A])(f : A => B) : InvariantList[B] = {
    xs match {
      case Nil => Nil[B]
      case Cons(head, tail) => Cons(f(head), map(tail)(f))
    }
  }
}

object Example {
  val xs = Cons(7, Cons(5, Nil[Int]))
  InvariantList.map(xs)(_ + 1)
}

This is pretty close to what I want, but it is annoying to have to specify the type parameter of Nil in the implementation of map and in the example use.

I also tried using case class Nil[T]() extends InvariantList[T], but this is also ugly because I have to put the parens all over the place.

What is the recommended way of defining Nil in an invariant linked list implementation? I think the question applies more generally to any invariant data structure that has cases with empty constructors. I would like it to be as convenient to use as the standard library List (convenient in that I don't have to specify the type parameter or add parens).

Upvotes: 2

Views: 178

Answers (1)

Michael Zajac
Michael Zajac

Reputation: 55569

The standard library doesn't have a Nil element for its invariant collections. For example, Set and ListBuffer are invariant, but they do not have Nil sub-type. They require you to say Set.empty[A] or ListBuffer.empty[A].

scala> val l : ListBuffer[Int] = Nil
<console>:11: error: type mismatch;
 found   : scala.collection.immutable.Nil.type
 required: scala.collection.mutable.ListBuffer[Int]
       val l : ListBuffer[Int] = Nil
                                 ^

scala> val set: Set[Int] = Nil
<console>:11: error: type mismatch;
 found   : scala.collection.immutable.Nil.type
 required: Set[Int]
       val set: Set[Int] = Nil
                           ^

Having a single case object Nil extends InvariantList[_] won't work because of invariance. Every list type would require it's own empty representation. Because an empty List[Dog] would not be the same as an empty List[Animal], if Dog <: Animal, etc.

What you're essentially asking for is a singleton symbol Nil to be treated like many different types. I think you're on the right track with a case class, because that will allow you one Nil[A] per list type. Unfortunately that will never allow you to pattern-match on Nil, only Nil(), because you need an extractor with parameters and not one for a singleton (which your Nil is not). If you want the convenience of not writing the type parameter and parentheses, you can write a method like this in the same package:

def nil[A] = Nil[A]()

It's not ideal, but it will partially solve your problem. Putting it all together:

sealed trait InvariantList[A]

case class Nil[A]() extends InvariantList[A]

case class Cons[A](head : A, tail : InvariantList[A]) extends InvariantList[A]

object InvariantList {

  def map[A, B](xs : InvariantList[A])(f : A => B) : InvariantList[B] = {
    xs match {
      case Nil() => nil
      case Cons(head, tail) => Cons(f(head), map(tail)(f))
    }
  }

}

scala> val xs = Cons(7, Cons(5, nil))
xs: Cons[Int] = Cons(7,Cons(5,Nil()))

scala> InvariantList.map(xs)(_ + 1)
res0: InvariantList[Int] = Cons(8,Cons(6,Nil()))

Upvotes: 3

Related Questions