A Trivial Display of How Scala's Type System Beats Java's

This article shows that Scala lets you add methods to objects, depending on their generic types. In Scheme, and other lisps and languages influenced by lisp, there is a construct called a cons, which is a pair of values. Linked lists can be built up by 'consing' pairs together. The first part of a cons can be called the 'car' (if used as a list, this is the head), and the second the 'cdr' (if used as a list, this is the tail). So if you have a cons with a cons as its second element, you can think of that as a compound data structure with three elements. E.g.:

(cons 1 (cons 2 3))

The first value of the second part of that, 2, the head of the tail, the car of the cdr, is known as the cadr. Let's write a Cons class in Java and Scala and then look at how to add the cadr.

Consider this Java code:

class Cons<A,D>
{
    public final A car;
    public final D cdr;

    public Cons(A car,D cdr)
    {
        this.car=car;
        this.cdr=cdr;
    }
}

equivalent to this Scala:

case class Cons[A,D](car: A,cdr: D)

(yes, that's all)

Now let's think about cadr. If a Cons has a car of type A and a cdr of type D, what type is the cadr? It's the type of the car of the cdr, which we haven't got a type parameter for. We could try this:

class Cons<A,D extends Cons<E,F>> but there's a recursion problem here -- F must extend Cons<E,F>>, not going to work. Plus, even if that worked, we could no longer use Cons for simple pairs.

We can make a static method elsewhere:

public static <A,D,E> D cadr(Cons<A,Cons<D,E>> cons)
{
    return cons.cdr.car;
}

That works fine, but it makes cadr somewhat a second-class citizen. It's a shame we can't do pair.cadr. In steps Scala.

implicit def addCadr[A,D,E](cons: Cons[A,Cons[D,E]])=new { def cadr=cons.cdr.car }

Cons(1,Cons(2,3)).cadr gives 2

addCadr, when in scope (it can be imported if it's not written where we need it) defines an implicit conversion from Cons[A,Cons[D,E]] to an anonymous class that implements cadr. So any time we ask for cadr the compiler (not the runtime) looks at our Cons type, doesn't see cadr and looks for any implicit conversions that result in a type that implements cadr. In this case it finds one.

The above is probably not a very practical use, let's think of some. You can make a List[Char] have the same methods as a String, for convenience. You can make a List[Double] have a total method.

(The worst thing about Java generics is how annoying they are to type in blogger!)