How do you encode Algebraic Data Types in a C#- or Java-like language?
- by Jörg W Mittag
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?
