How do you encode Algebraic Data Types in a C#- or Java-like language?

Question

There are some problems which are easily solved by Algebraic Data Types, for example a List type can be very succinctly expressed as:

data ConsList a = Empty | ConsCell a (ConsList a)

consmap f Empty          = Empty
consmap f (ConsCell a b) = ConsCell (f a) (consmap f b)

l = ConsCell 1 (ConsCell 2 (ConsCell 3 Empty))
consmap (+1) l

This particular example is in Haskell, but it would be similar in other languages with native support for Algebraic Data Types.

It turns out that there is an obvious mapping to OO-style subtyping: the datatype becomes an abstract base class and every data constructor becomes a concrete subclass. Here's an example in Scala:

sealed abstract class ConsList[+T] {
  def map[U](f: T => U): ConsList[U]
}

object Empty extends ConsList[Nothing] {
  override def map[U](f: Nothing => U) = this
}

final class ConsCell[T](first: T, rest: ConsList[T]) extends ConsList[T] {
  override def map[U](f: T => U) = new ConsCell(f(first), rest.map(f))
}

val l = (new ConsCell(1, new ConsCell(2, new ConsCell(3, Empty)))
l.map(1+)

The only thing needed beyond naive subclassing is a way to seal classes, i.e. a way to make it impossible to add subclasses to a hierarchy.

How would you approach this problem in a language like C# or Java? The two stumbling blocks I found when trying to use Algebraic Data Types in C# were:

• I couldn't figure out what the bottom type is called in C# (i.e. I couldn't figure out what to put into class Empty : ConsList< ??? >)
• I couldn't figure out a way to seal ConsList so that no subclasses can be added to the hierarchy

What would be the most idiomatic way to implement Algebraic Data Types in C# and/or Java? Or, if it isn't possible, what would be the idiomatic replacement?

Answer 1

There is an easy, but boilerplate heavy way to seal classes in Java. You put a private constructor in the base class then make subclasses inner classes of it.

public abstract class List<A> {

   // private constructor is uncallable by any sublclasses except inner classes
   private List() {
   }

   public static final class Nil<A> extends List<A> {
   }

   public static final class Cons<A> extends List<A> {
      public final A head;
      public final List<A> tail;

      public Cons(A head, List<A> tail) {
         this.head = head;
         this.tail = tail;
      }
   }
}

Tack on a visitor pattern for dispatch.

My project jADT : Java Algebraic DataTypes generates all that boilerplate for you https://github.com/JamesIry/jADT

Answer 2

In C#, you can't have that Empty type, because, due to reification, the base types are different for different member types. You can only have Empty<T>; not that useful.

In Java, you can have Empty : ConsList due to type erasure, but I am not sure whether the type checker wouldn't scream somewhere.

However since both languages have null, you can think of all their reference types as being "Whatever|Null". So you'd just use the null as the "Empty" to avoid having to specify what it derives.

Answer 3

The only thing needed beyond naive subclassing is a way to seal classes, i.e. a way to make it impossible to add subclasses to a hierarchy.

In Java you can't. But you can declare the base class as package private, which means that all direct subclasses have to belong to the same package as the base class. If you then declare the subclasses as final, they can't be subclassed any further.

I don't know if this would address your real problem though ...

Answer 4

The only thing needed beyond naive subclassing is a way to seal classes, i.e. a way to make it impossible to add subclasses to a hierarchy.

How would you approach this problem in a language like C# or Java?

There isn't a good way to do this, but if you're willing to live with a hideous hack then you can add some explicit type checking to the abstract base class' constructor. In Java, this would be something like

protected ConsList() {
    Class<?> clazz = getClass();
    if (clazz != Empty.class && clazz != ConsCell.class) throw new Exception();
}

In C# it's more complicated because of the reified generics - the simplest approach might be to convert the type to a string and mangle that.

Note that in Java even this mechanism can theoretically be bypassed by someone who really wants to via the serialisation model or sun.misc.Unsafe.

Answer 5

You can achieve this by using the visitor pattern, which will supplement pattern matching. For example

data List a = Nil | Cons { value :: a, sublist :: List a }

can be written in Java as

interface List<T> {
    public <R> R accept(Visitor<T,R> visitor);

    public static interface Visitor<T,R> {
        public R visitNil();
        public R visitCons(T value, List<T> sublist);
    }
}

final class Nil<T> implements List<T> {
    public Nil() { }

    public <R> R accept(Visitor<T,R> visitor) {
        return visitor.visitNil();
    }
}
final class Cons<T> implements List<T> {
    public final T value;
    public final List<T> sublist;

    public Cons(T value, List<T> sublist) {
        this.value = value;
        this.sublist = sublist;
    }

    public <R> R accept(Visitor<T,R> visitor) {
        return visitor.visitCons(value, sublist);
    }
}

Sealing is achieved by the Visitor class. Each of its methods declares how to deconstruct one of the subclasses. You could add more subclasses, but it would have to implement accept and by calling one of the visit... methods, so it would either have to behave like Cons or like Nil.