Come si codificano i tipi di dati algebrici in un linguaggio C # o simile a Java?

C'è un modo semplice, ma semplice, per sigillare le classi in Java. Metti un costruttore privato nella classe base, quindi crea sottoclassi di classi interne di esso.

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 su un pattern visitatore per la spedizione.

Il mio progetto jADT: Java Algebraic DataTypes genera tutto quel boilerplate per te link

Puoi ottenere ciò utilizzando il modello di visitatore , che supporterà la corrispondenza del modello. Per esempio

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

può essere scritto in Java come

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);
    }
}

La sigillatura è raggiunta dalla classe Visitor . Ciascuno dei suoi metodi dichiara come decostruire una delle sottoclassi. Potresti aggiungere più sottoclassi, ma dovrebbe implementare accept e chiamando uno dei metodi visit... , quindi dovrebbe comportarsi come Cons o come Nil .

Se si abusa di parametri denominati C # (introdotti in C # 4.0), è possibile creare tipi di dati algebrici facili da abbinare:

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);

Ecco l'implementazione della classe Either :

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);
    }
}

In C #, non puoi avere quel tipo di Empty , perché, a causa della reificazione, i tipi di base sono diversi per i diversi tipi di membri. Puoi avere solo Empty<T> ; non è utile.

In Java, puoi avere Empty : ConsList a causa della cancellazione dei caratteri, ma non sono sicuro che il correttore di tipi non urlerebbe da qualche parte.

Tuttavia, poiché entrambi i linguaggi hanno null , puoi pensare a tutti i loro tipi di riferimento come "Whatever | Null". Quindi dovresti semplicemente usare null come "Vuoto" per evitare di dover specificare che cosa deriva.

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 non puoi. Ma puoi dichiarare la classe base come pacchetto privato, il che significa che tutte le sottoclassi dirette devono appartenere allo stesso pacchetto della classe base. Se poi dichiari le sottoclassi come definitive, non possono essere ulteriormente sottoclasse.

Non so se questo potrebbe risolvere il tuo vero problema ...

Il tipo di dati ConsList<A> può essere rappresentato come un'interfaccia. L'interfaccia espone un singolo metodo deconstruct che consente di "decostruire" un valore di quel tipo, ovvero di gestire ciascuno dei possibili costruttori. Le chiamate a un metodo deconstruct sono analoghe a un modulo case of in Haskell o ML.

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

Il metodo deconstruct accetta una funzione di "callback" per ogni costruttore nell'ADT. Nel nostro caso, prende una funzione per il caso di lista vuota e un'altra funzione per il caso "contro cella".

Ogni funzione di callback accetta come argomenti i valori accettati dal costruttore. Quindi il caso "lista vuota" non accetta argomenti, ma il caso "contro cella" prende due argomenti: la testa e la coda della lista.

Possiamo codificare questi "argomenti multipli" usando le classi Tuple o usando il currying. In questo esempio, ho scelto di utilizzare una semplice classe Pair .

L'interfaccia è implementata una volta per ogni costruttore. Innanzitutto, abbiamo l'implementazione per la "lista vuota". L'implementazione deconstruct chiama semplicemente la funzione di callback emptyCase .

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());
  }
}

Quindi implementiamo il caso "contro le cellule" in modo simile. Questa volta la classe ha proprietà: la testa e la coda della lista non vuota. Nell'implementazione deconstruct , tali proprietà vengono passate alla funzione di callback consCase .

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));
  }
}

Ecco un esempio di utilizzo di questa codifica di ADT: possiamo scrivere una funzione reduce che è la solita lista di fold over.

<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))
  );
}

Questo è analogo a questa implementazione in Haskell:

reduce reducer initial l = case l of
  Empty -> initial
  Cons t_v1 t_v2  -> reduce reducer (reducer initial t_v1) t_v2

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?

Non c'è un buon modo per farlo, ma se sei disposto a vivere con un orribile hack, puoi aggiungere un controllo di tipo esplicito al costruttore della classe base astratta. In Java, sarebbe qualcosa di simile a

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

In C # è più complicato a causa dei generici reificati - l'approccio più semplice potrebbe essere quello di convertire il tipo in una stringa e manipolarlo.

Si noti che in Java anche questo meccanismo può teoricamente essere aggirato da qualcuno che vuole davvero tramite il modello di serializzazione o sun.misc.Unsafe .