Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
3  
Of interest: Encoding algebraic data types in C# –  AakashM Aug 7 '12 at 8:35
1  
C# is OOP language. Solve problems using OOP. Don't try using any other paradigm. –  Euphoric Aug 7 '12 at 14:11
5  
@Euphoric C# has become a quite usable functional language with C# 3.0. First-class functions, built-in common functional operations, monads. –  Mauricio Scheffer Aug 7 '12 at 19:00
1  
@Euphoric: So is Scala. In fact, Scala is probably more purely OO than C#, for example, C# has separate language constructs for first class functions (delegates), whereas in Scala first class functions are just a design pattern (any object which has an apply method is a function), albeit a design pattern with library support and syntactic sugar. You might also notice that the Scala example I gave is not very idiomatic code, precisely because I tried to use only the pure OO subset of Scala. I used only polymorphism, inheritance and encapsulation. –  Jörg W Mittag Aug 8 '12 at 13:50
2  
@TikhonJelvis: Another way to look at it: in Haskell, the empty list is a polymorphic value, as you point out. AFAIK, neither C# nor Java allow polymorphic values, so you simply can't have an empty list of type Empty<T>, it has to be of some concrete type Empty<Something>. Since you want that type to be substitutable for every empty list, it needs to be a subtype of all lists, which can be achieved if Something is a subtype of all types, i.e. a bottom type. –  Jörg W Mittag Aug 8 '12 at 16:23
show 9 more comments

6 Answers

up vote 21 down vote accepted

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

share|improve this answer
    
Somehow I'm not surprised to see your name pop up here! Thanks, I didn't know this idiom. –  Jörg W Mittag Sep 6 '12 at 23:48
1  
When you said "boilerplate heavy" I was prepared for something much worse ;-) Java can be pretty bad with boilerplate, sometimes. –  Joachim Sauer Sep 7 '12 at 9:07
    
but this does not compose : you have no way to specialize type A without having to assert it through a cast (I think) –  nicolas Apr 17 at 14:09
add comment

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.

share|improve this answer
    
The problem with null is that it is too general: it represents the absence of anything, i.e. emptiness in general, but I want to represent the absence of list elements, i.e. an empty list in particular. An empty list and an empty tree should have distinct types. Also, the empty list needs to be an actual value because it still has behavior of its own, so it needs to have its own methods. To construct the list [1, 2, 3], I want to say Empty.prepend(3).prepend(2).prepend(1) (or in a language with right-associative operators 1 :: 2 :: 3 :: Empty), but I can't say null.prepend …. –  Jörg W Mittag Aug 8 '12 at 16:19
    
@JörgWMittag: The nulls do have distinct types. You can also easily create typed constant with value null for the purpose. But it's true you can't call methods on it. Your approach with methods does not work without element-type-specific Empty anyway. –  Jan Hudec Aug 9 '12 at 7:42
    
some crafty extension methods can fake 'method' calls on nulls (of course its all really static) –  jk. Oct 25 '12 at 12:52
add comment

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.

share|improve this answer
add comment

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 ...

share|improve this answer
    
I don't have a real problem, or I would have posted this on StackOverflow, not here :-) An important property of Algebraic Data Types is that they can be closed, which means that the number of cases is fixed: in this example, a list is either empty or it isn't. If I can statically ensure that this is the case, then I can make dynamic casts or dynamic intanceof checks "pseudo-type-safe" (i.e.: I know it's safe, even if the compiler doesn't), by simply ensuring that I always check those two cases. If, however, someone else adds a new subclass, then I can get runtime errors I didn't expect. –  Jörg W Mittag Aug 8 '12 at 14:19
    
@JörgWMittag - Well Java clearly doesn't support that ... in the strong sense that you seem to be wanting. Of course, you can do various things to block unwanted subtyping at runtime, but then you get "runtime errors that you don't expect". –  Stephen C Aug 8 '12 at 23:33
add comment

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.

share|improve this answer
    
It wouldn't be more complicated in C#: Type type = this.GetType(); if (type != typeof(Empty<T>) && type != typeof(ConsCell<T>)) throw new Exception(); –  svick Aug 7 '12 at 17:07
    
@svick, well observed. I wasn't taking into account that the base type would be parameterised. –  Peter Taylor Aug 7 '12 at 19:22
    
Brilliant! I guess this is good enough for doing "manual static type checking". I'm more looking to eliminate honest programming errors rather than malicious intent. –  Jörg W Mittag Aug 8 '12 at 16:13
add comment

If you abuse C# named parameters (introduced in C# 4.0), you can make algebraic data types that are easy to match on:

Either<string, string> e = MonthName(2);

// Match with no return value.
e.Match
(
    Left: err => { Console.WriteLine("Could not convert month: {0}", err); },
    Right: name => { Console.WriteLine("The month is {0}", name); }
);

// Match with a return value.
string monthName =
    e.Match
    (
        Left: err => null,
        Right: name => name
    );
Console.WriteLine("monthName: {0}", monthName);

Here is the implementation of the Either class:

public abstract class Either<L, R>
{
    // Subclass implementation calls the appropriate continuation.
    public abstract T Match<T>(Func<L, T> Left, Func<R, T> Right);

    // Convenience wrapper for when the caller doesn't want to return a value
    // from the match expression.
    public void Match(Action<L> Left, Action<R> Right)
    {
        this.Match<int>(
            Left: x => { Left(x); return 0; },
            Right: x => { Right(x); return 0; }
        );
    }
}

public class Left<L, R> : Either<L, R>
{
    L Value {get; set;}

    public Left(L Value)
    {
        this.Value = Value;
    }

    public override T Match<T>(Func<L, T> Left, Func<R, T> Right)
    {
        return Left(Value);
    }
}

public class Right<L, R> : Either<L, R>
{
    R Value { get; set; }

    public Right(R Value)
    {
        this.Value = Value;
    }

    public override T Match<T>(Func<L, T> Left, Func<R, T> Right)
    {
        return Right(Value);
    }
}
share|improve this answer
    
I've seen a Java version of this technique before, but lambdas and named parameters make it so much readable. +1! –  Doval Feb 7 at 18:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.