Wie codieren Sie algebraische Datentypen in einer C # - oder Java-ähnlichen Sprache?

Es gibt einige Probleme, die von algebraischen Datentypen leicht gelöst werden können. Beispielsweise kann ein Listentyp sehr prägnant ausgedrückt werden als:

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

Dieses spezielle Beispiel ist in Haskell enthalten, es ist jedoch in anderen Sprachen ähnlich, da die Unterstützung für algebraische Datentypen nativ ist.

Es stellt sich heraus, dass es eine offensichtliche Zuordnung zur Subtypisierung im OO-Stil gibt: Der Datentyp wird zu einer abstrakten Basisklasse und jeder Datenkonstruktor wird zu einer konkreten Subklasse. Hier ist ein Beispiel 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+)

Das einzige, was über die naive Unterklasse hinaus benötigt wird, ist eine Methode zum Versiegeln von Klassen, dh eine Methode, die das Hinzufügen von Unterklassen zu einer Hierarchie unmöglich macht.

Wie würden Sie dieses Problem in einer Sprache wie C # oder Java angehen? Die beiden Stolpersteine, die ich bei der Verwendung algebraischer Datentypen in C # gefunden habe, waren:

• Ich konnte nicht herausfinden, wie der unterste Typ in C # heißt (dh ich konnte nicht herausfinden, in was ich ihn einfügen soll class Empty : ConsList< ??? >)
• Ich konnte keine Methode zum Versiegeln finden, ConsList sodass der Hierarchie keine Unterklassen hinzugefügt werden können

Was wäre der idiomatischste Weg, um algebraische Datentypen in C # und / oder Java zu implementieren? Oder, wenn es nicht möglich ist, was wäre der idiomatische Ersatz?

Es gibt eine einfache, aber sehr umfangreiche Möglichkeit, Klassen in Java zu versiegeln. Sie fügen einen privaten Konstruktor in die Basisklasse ein und erstellen daraus Unterklassen innerer Klassen.

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

Heften Sie ein Besuchermuster für den Versand an.

Mein Projekt jADT: Java Algebraic DataTypes generiert das gesamte Boilerplate für Sie https://github.com/JamesIry/jADT

Sie können dies erreichen, indem Sie das Besuchermuster verwenden , das den Mustervergleich ergänzt. Zum Beispiel

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

kann in Java als geschrieben werden

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

Die Versiegelung erfolgt durch die VisitorKlasse. Jede ihrer Methoden deklariert, wie eine der Unterklassen dekonstruiert wird. Sie könnten weitere Unterklassen hinzufügen, diese müssten jedoch implementiert acceptund durch Aufrufen einer der visit...Methoden aufgerufen werden, sodass sie sich entweder wie Consoder wie verhalten müssten Nil.

Wenn Sie benannte C # -Parameter missbrauchen (eingeführt in C # 4.0), können Sie algebraische Datentypen erstellen, mit denen Sie leicht übereinstimmen können:

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

Hier ist die Implementierung der EitherKlasse:

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 # können Sie diesen EmptyTyp nicht haben , da die Basistypen aufgrund der Reifizierung für verschiedene Elementtypen unterschiedlich sind. Sie können nur haben Empty<T>; nicht so nützlich.

In Java kann es Empty : ConsListsein, dass der Typ gelöscht wird, aber ich bin mir nicht sicher, ob die Typprüfung nicht irgendwo schreien würde.

Da jedoch beide Sprachen vorhanden sind null, können Sie sich alle Referenztypen als "Whatever | Null" vorstellen. Verwenden Sie also einfach den nullals "Leer", um zu vermeiden, dass Sie angeben müssen, was er ableitet.

Das einzige, was über die naive Unterklasse hinaus benötigt wird, ist eine Methode zum Versiegeln von Klassen, dh eine Methode, die das Hinzufügen von Unterklassen zu einer Hierarchie unmöglich macht.

In Java können Sie nicht. Sie können die Basisklasse jedoch als Paket privat deklarieren. Dies bedeutet, dass alle direkten Unterklassen zu demselben Paket gehören müssen wie die Basisklasse. Wenn Sie dann die Unterklassen als final deklarieren, können sie nicht weiter untergeordnet werden.

Ich weiß nicht, ob dies Ihr eigentliches Problem angehen würde ...

Der Datentyp ConsList<A>kann als Schnittstelle dargestellt werden. Die Schnittstelle stellt eine einzige deconstructMethode zur Verfügung, mit der Sie einen Wert dieses Typs "dekonstruieren" können, dh jeden der möglichen Konstruktoren handhaben können. Aufrufe einer deconstructMethode entsprechen einem case ofFormular in Haskell oder ML.

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

Die deconstructMethode verwendet eine "Rückruffunktion" für jeden Konstruktor im ADT. In unserem Fall wird eine Funktion für den leeren Listenfall und eine weitere Funktion für den Fall "cons cell" verwendet.

Jede Rückruffunktion akzeptiert als Argumente die Werte, die vom Konstruktor akzeptiert werden. Für den Fall "leere Liste" sind also keine Argumente zulässig, für den Fall "cons cell" sind jedoch zwei Argumente zulässig: der Kopf und der Schwanz der Liste.

Wir können diese "Mehrfachargumente" mit TupleKlassen oder mit Currying codieren . In diesem Beispiel habe ich mich für eine einfache PairKlasse entschieden.

Die Schnittstelle wird für jeden Konstruktor einmal implementiert. Zunächst haben wir die Implementierung für die "leere Liste". Die deconstructImplementierung ruft einfach die emptyCaseRückruffunktion auf.

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

Dann implementieren wir den Fall "cons cell" auf ähnliche Weise. Diesmal hat die Klasse Eigenschaften: Kopf und Ende der nicht leeren Liste. In der deconstructImplementierung werden diese Eigenschaften an die consCaseRückruffunktion übergeben.

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

Hier ist ein Beispiel für die Verwendung dieser Codierung von ADTs: Wir können eine reduceFunktion schreiben , bei der es sich um die üblichen Fold-Over-Listen handelt.

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

Dies ist analog zu dieser Implementierung in Haskell:

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

Das einzige, was über die naive Unterklasse hinaus benötigt wird, ist eine Methode zum Versiegeln von Klassen, dh eine Methode, die das Hinzufügen von Unterklassen zu einer Hierarchie unmöglich macht.

Wie würden Sie dieses Problem in einer Sprache wie C # oder Java angehen?

Es gibt keine gute Möglichkeit, dies zu tun, aber wenn Sie bereit sind, mit einem abscheulichen Hack zu leben, können Sie dem Konstruktor der abstrakten Basisklasse eine explizite Typprüfung hinzufügen. In Java wäre dies so etwas wie

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

In C # ist es aufgrund der überarbeiteten Generika komplizierter - der einfachste Ansatz könnte darin bestehen, den Typ in eine Zeichenfolge zu konvertieren, die sich läst.

Beachten Sie, dass in Java sogar dieser Mechanismus theoretisch von jemandem umgangen werden kann, der über das Serialisierungsmodell oder wirklich möchte sun.misc.Unsafe.