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

58

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?

Jörg W. Mittag
quelle
4
Von Interesse: Codieren algebraischer Datentypen in C #
AakashM
3
C # ist OOP-Sprache. Lösen Sie Probleme mit OOP. Versuchen Sie nicht, ein anderes Paradigma zu verwenden.
Euphoric
7
@Euphoric C # ist mit C # 3.0 eine recht brauchbare Funktionssprache geworden. Erstklassige Funktionen, integrierte allgemeine Funktionsfunktionen, Monaden.
Mauricio Scheffer
2
@Euphoric: Einige Domänen sind mit Objekten einfach zu modellieren und mit algebraischen Datentypen schwer zu modellieren, andere sind umgekehrt. Wenn Sie wissen, wie beides funktioniert, können Sie Ihre Domain flexibler modellieren. Und wie gesagt, die Zuordnung algebraischer Datentypen zu typischen OO-Konzepten ist nicht so komplex: Der Datentyp wird zu einer abstrakten Basisklasse (oder einer Schnittstelle oder einem abstrakten Merkmal), die Datenkonstruktoren werden zu konkreten Implementierungsunterklassen. Das gibt Ihnen einen offenen algebraischen Datentyp. Vererbungsbeschränkungen geben Ihnen einen geschlossenen algebraischen Datentyp. Polymorphismus gibt Ihnen Fallunterscheidung.
Jörg W Mittag
3
@Euphoric, Paradigma, Schmaradigma, wen interessiert das? ADTs sind orthogonal zur funktionalen Programmierung (oder OOP oder was auch immer). Das Kodieren eines AST in einer beliebigen Sprache ist ein ziemlicher Schmerz ohne angemessene Unterstützung durch ADTs, und das Kompilieren dieser Sprache ist ein Schmerz ohne ein weiteres paradigmenunabhängiges Merkmal, den Pattern Matching.
SK-logic

Antworten:

42

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

James Iry
quelle
2
Irgendwie wundert es mich nicht, dass Ihr Name hier auftaucht! Danke, ich kannte diese Redewendung nicht.
Jörg W Mittag
4
Als du gesagt hast "Boilerplate Heavy", war ich auf etwas viel Schlimmeres vorbereitet ;-) Java kann mit Boilerplate manchmal ziemlich schlecht sein.
Joachim Sauer
aber das komponiert nicht: es gibt keine
möglichkeit,
Dies scheint leider nicht in der Lage zu sein, komplexere Summentypen abzubilden, z Either. Siehe meine Frage
Zoey Hewll
20

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.

Petr Pudlák
quelle
13

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);
    }
}
Joey Adams
quelle
Ich habe bereits eine Java-Version dieser Technik gesehen, aber Lambdas und benannte Parameter machen sie so gut lesbar. +1!
Doval
1
Ich denke, dass das Problem hier ist, dass Recht über die Art des Fehlers nicht allgemein ist. So etwas wie class Right<R> : Either<Bot,R>:, wobei Entweder in eine Schnittstelle mit kovarianten (out) Typparametern geändert wird und Bot der unterste Typ ist (Subtyp jedes anderen Typs, gegenüber von Object). Ich glaube nicht, dass C # einen Bottom-Typ hat.
Croyd
5

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.

Jan Hudec
quelle
Das Problem dabei nullist, dass es zu allgemein ist: Es repräsentiert das Fehlen von irgendetwas , dh die Leere im Allgemeinen, aber ich möchte das Fehlen von Listenelementen darstellen, dh eine leere Liste im Besonderen. Eine leere Liste und ein leerer Baum sollten unterschiedliche Typen haben. Außerdem muss die leere Liste ein tatsächlicher Wert sein, da sie immer noch ein eigenes Verhalten aufweist und daher über eigene Methoden verfügen muss. Um die Liste [1, 2, 3]zu erstellen, möchte ich sagen Empty.prepend(3).prepend(2).prepend(1)(oder in einer Sprache mit rechtsassoziativen Operatoren 1 :: 2 :: 3 :: Empty), aber ich kann nicht sagen null.prepend ….
Jörg W Mittag
@ JörgWMittag: Die Nullen haben unterschiedliche Typen. Sie können auch einfach eine typisierte Konstante mit dem Wert null für diesen Zweck erstellen. Aber es ist wahr, dass Sie keine Methoden dafür aufrufen können. Ihr Ansatz mit Methoden funktioniert ohnehin nicht ohne elementtypspezifisches Empty.
Jan Hudec
Einige schlauen Erweiterungsmethoden können 'Methoden'-Aufrufe auf Nullen fälschen (natürlich ist alles wirklich statisch)
jk.
Sie können implizite Konvertierungsoperatoren mit Emptyund Empty<>und missbrauchen, um eine recht praktische Simulation zu ermöglichen. Im Wesentlichen verwenden Sie Emptyin Code, aber alle Typensignaturen usw. verwenden nur die generischen Varianten.
Eamon Nerbonne
3

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

Stephen C
quelle
Ich habe kein wirkliches Problem, oder ich hätte dies auf StackOverflow gepostet, nicht hier :-) Eine wichtige Eigenschaft von algebraischen Datentypen ist, dass sie geschlossen werden können , was bedeutet, dass die Anzahl der Fälle behoben ist: in diesem Beispiel Eine Liste ist entweder leer oder nicht. Wenn ich statisch sicherstellen kann, dass dies der Fall ist, dann kann ich dynamische Casts oder dynamische intanceofChecks "pseudotypsicher" machen (dh: Ich weiß, dass es sicher ist, auch wenn der Compiler dies nicht tut), indem ich einfach immer sicherstelle Überprüfen Sie diese beiden Fälle. Wenn jedoch eine andere Person eine neue Unterklasse hinzufügt, kann es zu Laufzeitfehlern kommen, mit denen ich nicht gerechnet habe.
Jörg W Mittag
@ JörgWMittag - Java unterstützt das eindeutig nicht ... in dem starken Sinne, wie Sie es zu wollen scheinen. Natürlich können Sie verschiedene Dinge tun, um unerwünschte Untertypen zur Laufzeit zu blockieren, aber dann erhalten Sie "Laufzeitfehler, die Sie nicht erwarten".
Stephen C
3

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
Jameshfisher
quelle
Interessanter Ansatz, sehr schön! Ich kann die Verbindung zu F # Active Patterns und Scala Extractors sehen (und wahrscheinlich gibt es dort auch einen Link zu Haskell Views, von dem ich leider nichts weiß). Ich hatte nicht daran gedacht, die Verantwortung für den Mustervergleich über die Datenkonstruktoren in die ADT-Instanz selbst zu verlagern.
Jörg W Mittag
2

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.

Peter Taylor
quelle
1
Es wäre nicht komplizierter in C #:Type type = this.GetType(); if (type != typeof(Empty<T>) && type != typeof(ConsCell<T>)) throw new Exception();
Svick
@svick, gut beobachtet. Ich habe nicht berücksichtigt, dass der Basistyp parametrisiert werden würde.
Peter Taylor
Brillant! Ich denke, das ist gut genug für die "manuelle statische Typprüfung". Ich möchte eher ehrliche Programmierfehler als böswillige Absichten beseitigen.
Jörg W Mittag