Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
4  
Of interest: Encoding algebraic data types in C# – AakashM Aug 7 '12 at 8:35
2  
C# is OOP language. Solve problems using OOP. Don't try using any other paradigm. – Euphoric Aug 7 '12 at 14:11
7  
@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
2  
@Euphoric: some domains are easy to model with objects and hard to model with algebraic data types, some are the opposite. Knowing how to do both gives you more flexibility in modeling your domain. And like I said, mapping algebraic data types to typical OO concepts is not that complex: the data type becomes an abstract base class (or an interface, or an abstract trait), the data constructors become concrete implementation subclasses. That gives you an open algebraic data type. Restrictions on inheritance give you a closed algebraic data type. Polymorphism gives you case discrimination. – Jörg W Mittag Aug 8 '12 at 14:14
3  
@Euphoric, paradigm, schmaradigm, who cares? ADTs are orthogonal to the functional programming (or OOP or whatever else). Encoding an AST of any language is quite a pain without decent ADTs support, and compiling that language is a pain without another paradigm-agnostic feature, pattern matching. – SK-logic Sep 7 '12 at 17:53
up vote 33 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
2  
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
3  
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 '14 at 14:09

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

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 '14 at 18:37
1  
I think the problem here is that Right isn't generic over the type of error. Something like: class Right<R> : Either<Bot,R>, where Either is changed to an interface with covariant (out) type parameters, and Bot is the bottom type (subtype of every other type, opposite of Object). I don't think C# has a bottom type. – croyd Feb 24 '15 at 16:33

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
    
You can have an Empty and an Empty<> and abuse implicit conversion operators to allow a fairly practical simulation, if you want. Essentially, you use Empty in code, but all type signatures etc only use the generic variants. – Eamon Nerbonne May 28 '14 at 10:51

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

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

The data type ConsList<A> can be represented as an interface. The interface exposes a single deconstruct method which allows you to "deconstruct" a value of that type - that is, to handle each of the possible constructors. Calls to a deconstruct method are analogous to a case of form in Haskell or ML.

interface ConsList<A> {
  <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  );
}

The deconstruct method takes a "callback" function for each constructor in the ADT. In our case, it takes a function for the empty list case, and another function for the "cons cell" case.

Each callback function accepts as arguments the values which are accepted by the constructor. So the "empty list" case takes no arguments, but the "cons cell" case takes two arguments: the head and the tail of the list.

We can encode these "multiple arguments" using Tuple classes, or using currying. In this example, I chose to use a simple Pair class.

The interface is implemented once for each constructor. First, we have the implementation for the "empty list". The deconstruct implementation simply calls the emptyCase callback function.

class ConsListEmpty<A> implements ConsList<A> {
  public ConsListEmpty() {}

  public <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  ) {
    return emptyCase.apply(new Unit());
  }
}

Then we implement the "cons cell" case similarly. This time the class has properties: the head and tail of the non-empty list. In the deconstruct implementation, those properties are passed to the consCase callback function.

class ConsListConsCell<A> implements ConsList<A> {
  private A head;
  private ConsList<A> tail;

  public ConsListCons(A head, ConsList<A> tail) {
    this.head = head;
    this.tail = tail;
  }

  public <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  ) {
    return consCase.apply(new Pair<A,ConsList<A>>(this.head, this.tail));
  }
}

Here is an example of using this encoding of ADTs: we can write a reduce function which is the usual fold over lists.

<T> T reduce(Function<Pair<T,A>,T> reducer, T initial, ConsList<T> l) {
  return l.deconstruct(
    ((unit) -> initial),
    ((t) -> reduce(reducer, reducer.apply(initial, t.v1), t.v2))
  );
}

This is analogous to this implementation in Haskell:

reduce reducer initial l = case l of
  Empty -> initial
  Cons t_v1 t_v2  -> reduce reducer (reducer initial t_v1) t_v2
share|improve this answer
    
Interesting approach, very nice! I can see the connection to F# Active Patterns and Scala Extractors (and there's probably a link there to Haskell Views as well, which I know nothing about, unfortunately). I hadn't thought of moving the responsibility for pattern matching over the data constructors into the ADT instance itself. – Jörg W Mittag Oct 18 '15 at 17:07

protected by gnat Oct 17 '15 at 20:53

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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