Abstract Generic Collections: PFDS Section 2.1 Redux
At the end of my last post, I mentioned that I ended up reusing Scala’s build-in List collection to implement the exercises instead of writing a generic abstract Stack and sample implementations of those. Since then, I’ve spent some time learning about how to implement generic collections in Scala. I came up with a Stack trait, a la Okasaki’s Stack signature, and three implementations: the first two are straightforward translations of the SML structures given in the book, and the third is a more Scala-idiomatic implementation.
On an organizational note, I’ve also started a PFDScala repository on GitHub for this blog series, so I can have a centralized place to put all of the code I write for the exercises and examples. I’ll still put the relevant snippets in gists so I can embed them here.
Scala traits are very powerful. They’re basically like mixin classes from Ruby, in that your class can extend from multiple traits without having the troubles that plague C++-style multiple inheritance.
Abstract traits can be used like Java interfaces. This is just what we need to write a generic interface for Stacks:
For those of you unfamiliar with Scala, this is similar to a Java interface or a SML signature: we’re defining a type-parameterized trait/interface/signature with a bunch of method signatures that classes which extend this trait must implement themselves. What’s up with the weird type annotations, though?
In Scala, annotating a type parameter with
+ marks it as a covariant type
parameter. This means that if we have a type
C[+T], a type with a single
covariant type parameter, and if type
A is a subtype of type
B, then type
C[A] is a subtype of
C[B]. We can similarly annotate a type parameter with
- for the opposite effect.
>: type operator is the supertype relationship: the type on the left of
it has to be a supertype of the type on the right of it.
So why do we need to annotate our types like this here? In Scala, by default,
types are invariant in their type parameters. This means if we had a
List's type parameter was invariant, then that list
would not be a subtype of a
List[Number], even though it seems like it would
be fine because a
Integers is just a specialized
Numbers. The same thing goes for our
Stack type, so we mark its type
parameter up as covariant.
However, to keep compile-time type checking sound, Scala has to impose some
restrictions on the types of methods in classes with covariant type parameters,
due to the problem of mutability: a mutable array of type
T is actually
contravariant in its type parameter, because if you had an
Array of type
Any, updating one of its cells to be a subtype of
String is not
always legal. So, in our
Stack example, we can no longer simply say
def cons(x: T) : Stack[T]
x is appearing in a contravariant position, meaning that it has
the potential to mutate state in a way that could break type safety.
Luckily, we can get around this problem of contraviariant position by imposing a bound on the type of cons’s parameter: we say
def cons(x: U >: T) : Stack[U]
to ensure that the input type of cons is a supertype of the stack’s type. This
prevents any type safety issues caused by the potential contravariance of the
formal parameter, and allows users to generalize the type of a
Stack by consing
a more general type onto it. For example, one could cons a String onto a
Stack[Int] and get out a
This class uses the builtin List implementation to provide the underlying
storage for the
Stack. It also uses Scala’s companion object feature to
provide a static factory method for creating new
This class uses a custom implementation of
List as the backing store. It’s
the same idea as the first one, except we use a set of case classes to match on
instead of just wrapping
This shows off Scala’s case classes a little bit: they’re just like datatypes
in SML, except a bit more verbose to specify. The abstract class
LIST is like
the name of the datatype, and the case classes that inherit from it are like
the datatype’s constructors. Making
LIST sealed restricts classes from
extending it unless they’re in the same file: this allows the compiler to detect
This implementation is a bit different from the other two: instead of storing
Stack data as a data member inside of a single
this puts the implementation inside of case classes that extend the
implementation class, which is made abstract.
This strategy seems the most idiomatic of the implementations I wrote. It
defines its own internal datatype like the custom
without the mess of having to match on each of the cases of the custom
every time it’s necessary to operate on the data. I think it produces the most
compact and readable code out of all three implementations.
That was a long-winded post for what was just defining a simple custom collection interface and a few simple implementations. Again, all of this code is available in the PFDScala GitHub repo. Next time we’ll proceed with the next section, 2.2. Hopefully it will be easier to implement the examples and exercise solutions with the improved understanding of Scala’s type system that I gathered by writing this post.