Tupel

Byte-Welt - Projekte / Projects neco4j
1

Tuple fehlen leider immer noch in Java (wenn man von Krücken wie Map.Entry oder javafx.util.Pair einmal absieht), haben aber gerade im Collection-Umfeld viele potentielle Anwendungsmöglichkeiten, etwa:

[ul]
[li] interface Map<A,B> extends Iterable<Pair<A,B>>{...}[/li][li] static List<Pair<A,B>> zip(List<A> listA, List<B> listB){...}[/li][li] static Pair<List<A>,List<A>> partition(List<A> listA, Predicate<A> pred){...}[/li][/ul]

Mir fallen folgende Fragen dazu ein:
[ul]
[li] Interface und Implementierung, oder nur Implementierung?[/li][li] Natürliche Namen (“Pair”, “Triple”) oder durchnummeriert (“T2”,“T3”)?[/li][li] Welche Stelligkeiten? Brauchen wir z.B. Quintuple? Brauchen wir auch Wrapper für Einzelwerte, oder sogar einen “nullstelligen” Typ (analog Scalas Unit als vernünftige Alternative zu Void)?[/li][li] Soll es eine gemeinsame Oberklasse geben? Oder eine (potentiell beliebig erweiterbare) Implementierung über HListen? (ich denke, beides eher nicht)[/li][li] Sollen die Klassen (wie in der javatuple-Bibliothek) Iterable<Object> implementieren? (meiner Meinung nach eine schlechte Idee)[/li][/ul]

Als Diskussionsgrundlage poste ich mal die API meiner existierenden Pair-Klasse:

public abstract class Pair<A, B> {

    private Pair(){}

    public static <A, B> Pair<A, B> of(A a, B b) {...}

    public static <A, B> Pair<A, B> lazyOf(Supplier<A> supplierA, Supplier<B> supplierB) {...}

    public abstract A get1();

    public abstract B get2();

    public <A1> Pair<A1, B> with1(A$ a) {...}

    public <B1> Pair<A, B1> with2(B$ b) {...}

    public <A1> Pair<A1, B> map1(Function<A, A1> fn) {...}

    public <B1> Pair<A, B1> map2(Function<B, B1> fn) {...}

    public <A1,B1> Pair<A1,B1> bimap(Function<A, A1> fnA, Function<B, B1> fnB) {...}

    public <C> C collapse(BiFunction<A,B,C> fn) {...}

    public Pair<B, A> swap() {...}

    @Override
    public String toString() {
        return String.format("(%s,%s)", get1(), get2());
    }

    public int hashCode() {...}

    public boolean equals(Object o) {...}

    public <A1, A2, B1, B2> Pair<A2, B2> merge(Pair<A1, B1> that, BiFunction<A, A1, A2> fnA, BiFunction<B, B1, B2> fnB) {...}
}
2

Da bin ich mir auch nicht ganz sicher, aber ich würde glaube ich eine Lösung mit Interfaces, privaten Implementierungen und einer zentralen Factory à la Tuples favorisieren.

Natürliche Namen finde ich deutlich besser.

Tupel dritter Ordnung sollten vorerst ausreichen. Maximal vielleicht noch vierter Ordnung. Was darüber hinausgeht wird dann eher unübersichtlich und man sollte eine explizit für den Anwendungsfall entworfene Klasse verwenden. Auf 1- und 0-Tupel sollten wir vorerst mMn auch verzichten.

Denke ich auch nicht. Eine gemeinsame Oberklasse könnte bei sprechend bezeichneten Methoden nur ein Markerinterface oder eine generische (meine hier nicht im Sinne von Generics) Klasse, die nur der Container für eine beliebige Anzahl Werte ist.

Weniger ist mehr. Ich hatte mir die javatuple-Bibliothek auch mal angesehen, sie aber nicht verwendet, weil da meiner Meinung nach viel zu viel Overhead drin ist.

Da stecken schon einige interessante Ansätze drin. Ob das alles enthalten sein sollte, weiß ich noch nicht. Vieles könnte man auch in eine Utilityklasse packen. Ob das sinnvoll ist, muss man nochmal überlegen.

*** Edit ***

Um die Sinnhaftigkeit der einzelnen Punkte zu beurteilen, ist es vielleicht sinnvoll, das Zielanwendungsfeld abzustecken.
Am häufigsten braucht man Tupel wohl, wenn man mehrere Rückgabewerte in einer Methode hat und dort typsicher arbeiten möchte.
Welche Anwendungsfelder seht ihr noch?

3

[QUOTE=cmrudolph]
Um die Sinnhaftigkeit der einzelnen Punkte zu beurteilen, ist es vielleicht sinnvoll, das Zielanwendungsfeld abzustecken.
Am häufigsten braucht man Tupel wohl, wenn man mehrere Rückgabewerte in einer Methode hat und dort typsicher arbeiten möchte.
Welche Anwendungsfelder seht ihr noch?[/QUOTE]

  • „zippen“ von Listen u.s.w.
  • Zusammenfassen von Parametern, z.B. wenn eine API nur eine Function und keine BiFunction vorsieht, als Function<Pair<A,B>,C>
  • wenn wir Laziness unterstützen, kann das auch an manchen Stellen praktisch sein. Obwohl man natürlich genauso gut auch Supplier in eine normale Implementierung stopfen könnte, nur ist das etwas unbequemer

*** Edit ***

Ich habe noch mal über alles meditiert und stimme weitgehend überein.

Nur…

Was sollen die Interfaces bringen? Sind clientseitige Implementierungen sinnvoll? functionaljava hat keine Interfaces, und javatuples hat nur Marker-Interfaces für die einzelnen „Stellen“.

4

Ich sehe den Vorteil, dass man sauber mit einer Factory Tuples arbeiten kann. Eine Factory, deren Methoden eine konkrete Klasse als Rückgabewert haben, finde ich etwas … ungewohnt. Die konkreten Klassen könnten privat oder zumindest package private sein. Und da ich keinen Nachteil in den Interfaces sehe, erachte ich diese Vorgehensweise für sinnvoll.

5

Allgemein habe ich die Tendenz zu sagen: Erstmal ALLES als Interfaces. Konkret werden kann man später immernoch. Abstrakt werden nicht.

Nebenbei… es gibt Leute, die die Existenzberechtigung von abstrakten Klassen allgemein hinterfragen… und IMHO zu Recht, man braucht sie extrem selten, und mit den default methods sollte man sie noch seltener brauchen. Die einzige “echte” Begründung für eine abstrakte Klasse sehe ich jetzt eigentlich nur noch in der Sichtbarkeit (public abstract class mit protected abstract oder protected final methoden)

Aaaaber das “Pair” (das ich nebenbei gesagt schon häufiger schmerzlich vermisst habe…) war da bei mir bisher eine Ausnahme. Das war dann meistens eine finale (!) Klasse. Bei einer Verallgemeinerung hatte ich dann z.B. auch mal die Namen “Tuple2” und “Tuple3” verwendet. Über Namen kann man lange streiten, ich fand da die “Regelmäßigkeit” schön, (wie würde es bei JavaTuples mit “17” heißen? “Septadecimupl…” äh - “Tuple16” und fertig :D)

Eine Kleinigkeit zum geposteten: Mir ist nicht alles ganz klar (A$? Was macht “merge”?), aber die Factorymethode sah bei mir dann immer so aus

public static <A, AA extends A, B, BB extends B> Pair<A, B> of(AA a, AB b) {...}

Damit gingen solche Dinge wie

Pair<Number, Number> p = Pair.of(someInteger, someInteger);

(was sonst nur mit “Pair.<Number, Number>of(…)” möglich war… (oder hat sich das mit der neuen Target-Typinferenz bei Java8 jetzt erledigt?)

Und… auch auf die Gefahr hin, da jetzt ein zuuuu großes Fass aufzumachen: Sollen da auch Projektionen unterstützt werden?

Triple<A,B,C> triple = ...
Pair<A,C> pair = triple.project(0,2);

(SO natürlich nicht, nur um die Frage zu verdeutlichen…). Oder wird das sowieso schon durch eine der “Standardoperationen” abgedeckt?

6

Die merge-Methode kann man z.B. zur Berechnung einer Vektoraddition benutzen. Das ist eine der Methoden, die ich standardmäßig nicht unbedingt mit aufnehmen würde, weil sie doch recht speziell ist.

Die Projektion ist in allgemeiner Form durch die collapse-Methode abgebildet. Gerade bei größeren n-Tupeln wäre es äußerst mühselig, sämtliche Projektionsfunktionen im Voraus zu definieren. Die allgemeine Form gefällt mir eigentlich ganz gut.

Die of-Methode mit AA extends A etc. ist eine sinnvolle Erweiterung. Das sollte man so machen.

7

Ich weiß ja, dass man normalerweise nicht versuchen sollte, die Benutzer vor sich selbst zu schützen, aber Interfaces laden natürlich zu eigenen Implementierungen ein. Das ist normalerweise nicht schlimm, insbesondere da es ja jetzt Default-Methoden gibt.

Das Problem in unserem Fall ist aber, dass keine Default-Implementierungen von Object-Methoden wie equals, hashcode und toString erlaubt sind. Das finde ich besonders kritisch, da Pair für eine Verwendung als Map-Key oder ähnliches geradezu prädestiniert ist (noch ein Anwendungsfall, der auf der Liste fehlt). Die Gefahr, funktionierenden Code durch eine fehlerhafte Pair-Implementierung zu torpedieren, ist durchaus real (gerade weil es so “einfach” aussieht, so etwas zu implementieren).

Auch der Fall, dass man eine vorhandene Klasse aus Bequemlichkeit Pair implementieren lässt, erscheint mir nicht sonderlich erstrebenswert.

Deshalb würde ich hier (wie schon bei Left und Right) lieber auf abstrakte, quasi-finale Klassen ausweichen.

Aus theoretischer Sicht gebe ich dir mit den Interfaces bei Factories für “normale” Objekte recht, aber Tuple gehören zusammen mit Optional, Either, List und Bäumen zu den Algebraischen Datentypen, für die normalerweise eine abgeschlossene Typhierarchie angestrebt wird (Scala realisiert das z.B. über das sealed-Schlüssenwort, aber auch Optional in Java ist final und bietet kein Interface an). Als “Bausteine” für kompliziertere Typen wird von ihnen normalerweise ein genau definiertes, “solides” Verhalten statt Flexibilität verlangt, was sich schlecht mit unkontrollierter clientseitiger Vererbung realisieren lässt.

8

Ahja, das “merge” hätte ich nur mal etwas genauer lesen müssen.
Aber wie die Projektion im “collapse” stecken soll, erschließt sich mir nicht (für 2D->1D ja, aber für höhere Dimensionalitäten ja nicht, oder…?)
Aber vermutlich muss ich da auch nochmal drüberlesen, wenn ich nicht gerade so kaputt bin, wie jetzt… :rolleyes:

Interface/Abstract: Es spräche ja nichts gegen ein “AbstractPair implements Pair”, wo die genannten kritischen Methoden schon (final!) implementiert sind. Und natürlich sollte man (in Anlehnung an eine meiner “Lieblingspräsentationen”, http://www.infoq.com/presentations/effective-api-design ) dafür sorgen, dass es leicht ist, die API zu verwenden, aber es schwer ist, sie falsch zu verwenden. Ob “etwas als Klasse schreiben, damit es kein implementierbares interface ist” da dazugehört, weiß ich nicht, aber das sollte kein “harter” Einwand sein - nochmal drüber schlafen…

9

Wäre es dann nicht sinnvoll, echt finale Klassen zu verwenden? Bei Left und Right bräuchte man dann eine Instanzvariable und könnte dann keine anonyme Klasse erzeugen. Im übrigen fand ich das Konstrukt den Rückgabewert durch Erweiterung der abstrakten Klassen zu definieren auch etwas ungewohnt. Hat das spezielle Vorteile?
Je nachdem kann man bei Tupeln natürlich auch mit anonymen Klassen arbeiten.

*** Edit ***

Beispiel zum collapse, der Einfachheit halber gehe ich mal davon aus, dass es einen Typ Unit gibt: C wäre Unit<A> im Fall des Pair. Bei einem Triple wäre es Pair<A, B>, Pair<A, C> oder sogar Unit<B>.
Das geht natürlich dann nicht mit einer BiFunction.

10

[QUOTE=cmrudolph]Wäre es dann nicht sinnvoll, echt finale Klassen zu verwenden? Bei Left und Right bräuchte man dann eine Instanzvariable und könnte dann keine anonyme Klasse erzeugen. Im übrigen fand ich das Konstrukt den Rückgabewert durch Erweiterung der abstrakten Klassen zu definieren auch etwas ungewohnt. Hat das spezielle Vorteile?
[/quote]
Das hat nur den Vorteil, dass man Left und Right sowohl mit Werten wie auch mit Suppliern (oder etwas anderen) „befüllen“ kann. Wenn wir ganz auf die Lazy-Variante verzichten, spricht nichts gegen finale Klassen.

Beispiel zum collapse, der Einfachheit halber gehe ich mal davon aus, dass es einen Typ Unit gibt: C wäre Unit<A> im Fall des Pair. Bei einem Triple wäre es Pair<A, B>, Pair<A, C> oder sogar Unit<B>.
Das geht natürlich dann nicht mit einer BiFunction.

collapse sollte meiner Meinung nach einen einzigen Wert liefern, wir bräuchten also hier eine „TriFunction“. Natürlich könnten wir (gepriesen sei Curry!) auch tricksen und eine Function<A,Function<B,Function<C,D>>> verwenden, was dann als Lambda a -> b -> c -> ... geschrieben werden müsste - aber das ist wohl etwas zu subtil. Vielleicht sollten wir die Funktion bei Tripeln auch ganz weglassen.

11

Die collapse Methode ist meiner Meinung nach ziemlich mächtig. Solange wir uns bei der Kardinalität der Tupel auf maximal vielleicht vier beschränken, sollte es kein Problem sein, ein TriFunction und QuadFunctionInterface umzusetzen.
Currying zu verwenden finde ich auch etwas zu sperrig. Man sieht bei den verschachtelten Generics nicht mehr so gut, was eigentlich passieren soll.

12

Hmmm, die könnten auch sonst im richtigen Leben nützlich sein. Dann füge ich die schon mal hinzu (die Implementierung sollte ja mit Function und BiFunction als Vorlage relativ unstrittig sein).

*** Edit ***

Wie ist die Meinung bezüglich Laziness? Sollen Tupel und Either bei der Initialisierung auch Unterstützung für Supplier bieten? Oder soll sich der Nutzer da selber drum kümmern?

Ich neige inzwischen zu letzterem, weil es so konsistent mit Optional ist, weil das handgeklöppelte Supplier-Schachteln nicht soooo kompliziert ist, und weil wir dann die entsprechenden Klassen final machen könnten. Außerdem gäbe es eine kombinatorische Explosion, wenn der Nutzer nur teilweise lazy sein will, etwa der mittlere Wert in einem Tripel lazy sein soll. In Eigenregie kann er einfach ein Tuple<String, Supplier<Integer>, Integer> verwenden, ohne dass wir irgend etwas dazu tun müssten.

13

Gemäß Interfacedoku

kann ein Supplier auch verwendet werden, um beispielsweise eindeutige IDs zu generieren. Im Gegenteil: es wird angenommen, dass bei jedem Aufruf ein anderer Wert herauskommt, auch wenn es zulässig ist, dass jedes mal derselbe Wert zurückgegeben wird.

Man kann in einem Either derzeit nur idempotente Supplier verwenden, ansonsten verhält sich Either unerwartet.

Prinzipiell finde ich eine lazy-Initialisierung sinnvoll. Allerdings müsste man dafür eine Instanzvariable in Either / Left / Right einführen. Außerdem muss man prüfen, ob der Supplier null ausgegeben hat und dann ggf. eine Exception werfen, da ansonsten zu diesem Zeitpunkt die Klassenconstraints nicht eingehalten werden (Left#left und Right#right liefern immer nonnull zurück).

In Anbetracht der zusätzlichen Komplexität müssen wir noch einmal abwägen, ob die Vorteile der lazy-Initialisierung die Nachteile überwiegen.
Fakt ist: derzeit ist die Either-Implementierung nicht optimal.

14

Nach etwas Meditation bin ich dafür, Laziness hier wegzulassen. Wer will, kann ja selber Typen wie Either<Supplier<String>,Integer> verwenden. Left wäre so immer idempotent, weil es stets den gleichen Supplier zurückgibt (der dann selbst idempotent sein kann oder nicht). Insgesamt fände ich es gut, wenn Either sich möglichst ähnlich wie Optional “anfühlt”.

*** Edit ***

Hier geht’s mit Either weiter…

15

Habe mal eine einfache Pair-Klasse ähnlich wie oben committed. Klasse ist sehr einfach, final und hat eine statische Factory. merge habe ich weggelassen. Theoretisch brauchte man auch die with-Methoden (als Äquivalente zu Settern) nicht, statt pair.with1(42) kann ja einfache pair.map1(x -> 42) schreiben.

Zu Projektionen habe ich mir noch keine Meinung gebildet, aber wie schon gesagt wurde, kann man selbige mit collapse leicht selber basteln: triple.collapse((x,y,z) -> Pair.of(x,z))

Javatuples hat noch diverse Methoden zum “Anfügen”, also aus einem Pair und einem Wert ein Triple oder aus zwei Pairs ein Quadrupel usw. Sehe ich nicht als Muß an. Auch hier hülfe collapse: pair.collapse((x,y) -> Triple.of(x,42,y))

16

Die with-Methoden finde ich nicht so schön. Wie du ja schon sagtest, braucht man die eigentlich auch gar nicht, sondern kann auch mit map arbeiten.
Die Anzahl an Methoden wächst explosionsartig, wenn man Anfügeoperationen hinzufügt. Das spielte sich hier zwar noch in etwas kleinerem Rahmen ab (je nachdem, wie groß die größten Tupel dann schlussendlich werden), bläst das API aber unnötig auf.

*** Edit ***

Ansonsten sieht das Pair schon gut aus - bis auf ein fehlendes @Override beim hashCode.

17

Bei with bin ich mir nicht sicher, mal horchen, was Marco dazu sagt.

Ich werde dann mal Triple hinterherwerfen…

18

Sorry, bin gerade nicht ganz da, und bei dem “with” weiß ich nicht genau, was ich sagen soll (ich gehe aber davon aus, dass meine pragmatische lösung mit “Pair.of(a,null)” oder “Pair.of(null,b)” dafür sorgen würde, dass null-Feinden das Blut aus den augen spritzt :D).

Das collapse erschließt sich mir noch nicht ganz. D.h. man könnte collapse nur bei N-Tupeln anwenden, für die es auch eine N-äre Function gibt? Und es würde (entgegen dessen, was man anhand des Namens erwarten würde), auch ein “expandetes” Tuple zurückgeben können? Hm. Hoffentlich hab’ ich nächste Woche mehr Zeit, den Diskussionen (und dem Code!) mehr zu folgen…

19

Das collapse erschließt sich mir noch nicht ganz. D.h. man könnte collapse nur bei N-Tupeln anwenden, für die es auch eine N-äre Function gibt?

Ja. Oder den oben erwähnten Curry-Trick, der aber verwirrend und hässlich ist.

Und es würde (entgegen dessen, was man anhand des Namens erwarten würde), auch ein „expandetes“ Tuple zurückgeben können?

Na ja, die Methode „kollabiert“ alle Werte in einem Tupel zu einem einzigen Wert, und wenn dieser halt ein anderes Tupel ist, ist das eben so. Wobei wir uns auch einen besseren Name suchen können.

Theoretisch gesehen handelt es sich dabei um einen Katamorphismus, genau wie Either.either(), List.fold und Varianten oder Optional.map().orElse().

Vielleicht wäre der Methoden-Name fold in Pair und Either „neutraler“ und vor allem konsistenter.

20

Ich hab mir die Wikipediaartikel zu fold und Katamorphismus mal durchgelesen (habe mit funktionaler Programmierung (Haskell) nur ein Semester lang zu tun gehabt). Auf die collapse-Methode passt das aber glaube ich nicht so ganz. Aber trotzdem wäre eine Umbenennung vielleicht nicht verkehrt. Und für die Liste sollten wir sowohl foldl und foldr anbieten.