Persistente Java Collections?


#1

Um die hier gestellte Frage noch einmal zentraler zu positionieren:

Bestände prinzipielles Interesse an einem kleinen Java-8-Projekt für persistente, immutable Datenstrukturen (List, Set, Map, Tuple, Either)? Ich würde dabei Wert auf eine einfache, durchdachte API legen.


#2

(Hätte auch da nochmal geantwortet, aber ein eigener Thread ist da sicher angebracht)

Vorbehaltlich: Prinzipielles Interesse ja. Ich bin zwar mit den neuen Java8-Features noch nicht so firm, und von den theoretischen Hintergründen persistenter Collections habe ich eigentlich gar keine Ahnung, aber … wenn man immer nur Sachen machen würde, die man schon kann, wär’s ja langweilig :smiley: Und sei es nur eine Gelegenheit, etwas daran zu ändern - unabhängig davon, ob das, was man macht, am Ende auf irgendeiner offiziellen Download-Seite landet.

Die weiteren Vorbehalte: Es gibt da ja schon einiges. Unter http://stackoverflow.com/questions/8575723/whats-a-good-persistent-collections-framework-for-use-in-java sind ein paar aufgelistet/verlinkt. Man sollte (wenn man nicht das “Risiko” eingehen will, dass das NUR eine “akademische Spielerei” im oben angedeuteten, autodidaktischen Sinne wird) eine klare Idee haben, inwieweit sich das Ergebnis von den bestehenden unterscheiden soll. Sicher haben die bestehenden Libs “prinzipbedingt” noch keine ausgefeilte Unterstützung für Java8-Features. Aber das wichtige ist hier das “noch”: Wenn eine der anderen Libs mit wenig Aufwand dahingehend erweitert werden kann, muss man nicht nur damit rechnen, sondern schon fast davon ausgehen, dass das getan wird, und man dann mit etwas, was “from scratch” gestartet wurde gegen eine etabliertere und über Jahre (von Leuten, die Ahnung von der Sache haben) entwickelte Lib antritt. (Aber um das nochmal zu betonen: Etwa 99% von dem, was ich programmiere, ist reiner Selbstzweck. Das würde mich nicht davon abhalten, das zu tun. Das ist nur ein Punkt, den ich erwähnen wollte…)

Die Frage, wie viel Zeit man da investieren könnte/“müßte” ist natürlich auch wichtig, aber darum ging es ja erstmal (noch) nicht.


#3

Eine Sache, die man besser machen kann, ist das Zusammenspiel zwischen den einzelnen Typen. Vielen dieser Bibliotheken fehlen z.B. Tuple, fast allen (mit der Ausnahme von functionaljava) fehlt Either. Aber gerade das gehört meiner Meinung nach zu Collections dazu, solche Sachen wie [inline]List List.flatten(List<Optional> list)[/inline], [inline]List<Pair<A,B>> List.<A,B>zip(List listA, List listB)[/inline] oder [inline]List Either.<A,?>lefts(List<Either<A,?>> list)[/inline] machen das Ganze erst interessant. Die Implementierung selbst halte ich ehrlich gesagt nicht für das Problem, da kann man einerseits erst mal mit möglichst einfachen Versionen beginnen, und sich andererseits durchaus anderswo “inspirieren lassen”.


#4

Hmja, sowas wie https://code.google.com/p/totallylazy/ sieht aber schon ziemlich umfangreich aus (wenn auch besch*** dokumentiert). Ich muss aber auch zugeben, mich mit (händewedel) “~vielem, was damit zu tun hat” noch nicht so beschäftigt habe. Gibt’s die “einigen Implementierungen”, die du im anderen Thread erwähnt hast, irgendwo?


#5

totallylazy sieht nicht schlecht aus, müsste aber auch eine Java-8-Überholung bekommen.

Ich denke, man könnte einiges aus highJ wiederverwenden, wenn man das Typklassen-Zeug rausschmeißt und sich etwas mehr Gedanken über die API macht. Tuple und eine rudimentäre RA-Liste habe ich noch lokal bei mir rumliegen.

Apropos Lazyness: Es wäre natürlich auch noch zu klären, ob man das für die Collections selbst vorsieht, oder das mit dem neuen Stream-Mechanismus abfrühstückt.


#6

Ich finde das Thema auch sehr interessant. Mit Streams bin ich erst beim Implementieren meines Algorithmus’ für das Pi-Puzzle in Berührung gekommen. Das lässt einige griffige Transformationen zu:
expressionSetForCell.stream().map(Expression::value).collect(Collectors.toSet());

Je nach Zeitaufwand wäre ich auch dabei.


#7

Ich finde bei solchen Vorhaben die Abgrenzung schwierig. Man kann immer weiter verallgemeinern und abstrahieren, und am Ende kommt sowas … nunja, nicht unbedingt alltägliches wie “Functional Java” raus. Aber wenn man eine gute Interoperabilität mit den normalen Collections und eine Einbeziehung der Java8-Strukturen anstrebt, wird man zumindest damit ein bißchen “geerdet” :smiley:


#8

[QUOTE=Marco13;94787]Ich finde bei solchen Vorhaben die Abgrenzung schwierig. Man kann immer weiter verallgemeinern und abstrahieren, und am Ende kommt sowas … nunja, nicht unbedingt alltägliches wie “Functional Java” raus. Aber wenn man eine gute Interoperabilität mit den normalen Collections und eine Einbeziehung der Java8-Strukturen anstrebt, wird man zumindest damit ein bißchen “geerdet” :D[/QUOTE]

Genau deshalb will ich mehrere Meinungen mit einbeziehen und den Umfang schon vorher festlegen. Ich weiß genau, dass ich alleine immer wieder abdrifte (mein lokales Projekt enthält inzwischen Monoide, Linsen und zwei Monaden), und das will ich vermeiden. “Geerdet” trifft es ziemlich gut.

Ich bin mal so frei und mache einen kleinen Plan (korrigiert mich, wenn euch etwas stört oder fehlt):

  1. Name
    Wie wir seit Dilbert wissen, ist ein guter Projektname die halbe Miete (die andere Hälfte ist Glück).

Mein lokales Projekt heißt “neco” (für “new collections”), aber vielleicht fällt euch etwas besseres ein.

  1. Projekt aufsetzen
    Github?

  2. Tuple und Either
    Meiner Meinung nach am einfachsten, relativ unabhängig von Rest, und die anderen Collections können die Klassen dann schon verwenden.
    In diese Gruppe gehört eigentlich auch eine Option-Implementierung, aber ich denke wir sollten mit dem Standard-Java-8-Optional auskommen, auch wenn es nicht perfekt ist.

Ich könnte meinen vorhandenen Code erst mal ins Projekt kippen, und dann können wir ihn ummodeln. Oder wir einigen uns vorher auf ein Design, wie es euch lieber ist.

  1. Collections
    Welche Interfaces wollen wir anbieten, welche Implementierungen?
    Sollen wir auch Gegenstücke zu Guava-Klassen (z.B. Multiset, Multimap) anbieten?
    Wie soll die Integration mit den vorhandenen Collections laufen?
    Wie gehen wir mit Laziness um? Supplier und/oder Stream?

  2. Nice to Have
    Irgendwelche sinnvollen Ergänzungen, die das Bild abrunden würden (etwa Zipper)?


#9

Das klingt doch fast schon nach einem Plan :smiley:

(“Natürlich” werde ich gerade in den nächsten Tagen besonders wenig Zeit haben, aber… :rolleyes: )

  1. Neco - abgesehen von der Nähe zu “necro” zumindest kurz und griffig. Wie zu erwarten wird es mit 4-buchstabigen Namen und der Endung “.org” aber eng. “necoll.org” würde gehen. Sowas wie “FunColl” wäre aber auch was: “The Fun(ctional) Collections” :smiley:

  2. Gegen GitHub spricht eigentlich nichts. (Ich persönlich entwickle zwar nicht bzw. ungern “öffentlich”, aber … ja)

  3. Es gibt sicher einige Dinge die “einfach” sind ( http://www.javatuples.org/ : “javatuples is one of the simplest java libraries ever made”). Die Herausforderung besteht eher darin, die einfachen Dinge gut und griffig in den Rest einzubetten.

3a) (Ein IMHO wichtiger Punkt) : Bestehenden Code “ummodeln” oder “from scratch” designen? Ich persönlich (und vermutlich die meisten) finden letzteres angenehmer, aber die Grenze ist natürlich fließend: Kopiert man das Projekt, ein Package, eine Klasse, eine Methode…? Das geht auch direkt über (bzw. hängt ab von) …

  1. Da habe ich nicht so den Überblick. Ich denke, es gibt einige Must-Haves: List, Set, Map… Gegen spätere Erweiterungen spricht ja nichts, aber die nachher “schön” in die bestehenden Strukturen einzubetten könnte schwieriger sein, als sie von Anfang an einzuplanen. (Für mich sollte eine API ja eigentlich final sein, wenn sie veröffentlicht wird, aber … mir ist klar, dass das in so einem Fall anders sein muss…)

  2. Auch wieder subjektiv: Ich finde, wenn man Tuples und alles Funktional macht, kommt man um Zipper kaum drumrum…


#10
  1. Wie wäre “neco4j”? Außer der phonetischen Nähe zu neo4j sehe ich keine Probleme damit.

  2. BitBucket wäre eine private Alternative, die 5 Nutzer sollten ausreichen. Releasen kann man dann ja immer noch irgendwann auf GitHub oder so.

3a) Von mir aus auch gerne “from scratch”.

Spielen wir das doch mal an [inline]Either[/inline] als Einzelklasse durch. Meine Gedanken dazu:

[inline]Either<A,B>[/inline] soll alternativ einen Wert der Klasse [inline]A[/inline] oder [inline]B[/inline] halten können. Dazu gibt es die Unterklassen [inline]Left[/inline] für Typ [inline]A[/inline] und [inline]Right[/inline] für Typ [inline]B[/inline].

Die Benennung ist konsistent in Haskell und Scala und sollte demnach beibehalten werden.

Die Unterklassen [inline]Left[/inline] und [inline]Right[/inline] sollten vor dem Nutzer nicht versteckt werden (IMHO ein Fehler in Javas [inline]Optional[/inline]), so dass problemlos [inline]instanceof[/inline]-Prüfungen und auch Spezialisierungen von Typparametern (z.B. für [inline]Foo<X extends Either<String, Long>[/inline] die Unterklasse [inline]LeftFoo extends Foo<Left<String, Long>>[/inline]) möglich sind.

Die Instantiierung würde ich über statische Methoden erledigen. Null-Werte sollten dabei verboten werden.
Zum Extrahieren sollte es zum einen [inline]boolean isLeft()[/inline] und [inline]A getLeft()[/inline] (mit eventuellem Fehler), [inline]A getLeftOrElse(A defaultValue)[/inline] wie auch [inline]Optional getLeftOpt()[/inline] geben, analog für [inline]Right[/inline].
Nützlich zum Extrahieren ist auch die Methode [inline]C either(Function<A,C> leftFn, Function<B,C> rightFn)[/inline], die alles in einen Wert “kollabiert” (für Theoretiker: ein Katamorphismus)
Zur Transformation könnte man [inline]map[/inline]-Methoden anbieten.
Eine [inline]swap[/inline]-Methode zum Umdrehen wäre nett.
Eventuell könnte man noch eine Lazy-Initialisierung mit Suppliern vorsehen.

Ungefähr so:

public abstract class Either<A,B> {
    Either(){} //package scope
    public static <A,B> Left<A,B>left(A a) {...}
    public static <A,B> Left<A,B>right(B b) {...}
    public static <A,B> Left<A,B>lazyLeft(Supplier<A> supA) {...}
    public static <A,B> Left<A,B>lazyRight(Supplier<B> supB) {...}
    public abstract boolean isLeft();
    public abstract boolean isRight();
    public abstract A getLeft() throws NoSuchElementException;
    public abstract B getRight() throws NoSuchElementException;
    public abstract A getLeftOrElse(A defaultValue);
    public abstract B getRightOrElse(B defaultValue);
    public abstract Optional<A> getLeftOpt();
    public abstract Optional<B> getRightOpt();
    public abstract <A1> Either<A1,B> mapLeft(Function<A,A1> fn);   
    public abstract <B1> Either<A,B1> mapRight(Function<B,B1> fn);   
    public abstract <A1,B1> Either<A1,B1> bimap(Function<A,A1> fnA,Function<B,B1> fnB);
    public abstract <C> C either(Function<A,C> fnA,Function<B,C> fnB);
    public abstract Either<B,A> swap();
}

public final class Left<A,B> extends Either<A,B> { 
   ...
}

public final class Right<A,B> extends Either<A,B> { 
   ...
}

Im Zusammenhang mit Listen und Sets wären eventuell noch ein paar statische Methoden sinnvoll. Außerdem wären noch statische Methoden zum “Flachklopfen” geschachtelter Eithers denkbar wie [inline]static <A,B> Either<A,B> joinLeft(Either<Either<A,B>,B> nested)[/inline], aber da wird es langsam zu speziell.

Wie gesagt, alles nur eine grobe Skizze.


#11
  1. Ich finde neco4j bisher am besten. necoll hört sich nach einem Frauennamen an, FunColl hört sich nicht ernst zu nehmen an. Und dafür, dass es nur ein Buchstabe Unterschied zu neo4j ist, liegen die Namen phonetisch eigentlich gar nicht mal soo dicht beieinander.
    Allerdings birgt das “new” im Namen die Problematik, dass es irgendwann nicht mehr “new” ist.

3a. From scratch finde ich auch besser. Unabhängig davon kann man sich ja vom bestehenden Code inspirieren lassen. Aber das ins selbe Repo zu packen finde ich nicht so gut.

  1. Ich nutze die guava-Collections sehr intensiv (insbesondere auch die Table), daher fände ich eine Unterstützung gut.

Abgesehen von 2 kleinen C&P-Fehlern in Zeile 5 und 7 sieht der Either-Entwurf ja schon einmal ziemlich umfangreich aus.
Die lazy-Initializer würde ich aber auch “left” und “right” nennen, eben mit einem Supplier als Parameter.
/* EDIT: Je nachdem, ob es noch andere “left” und “right” geben wird, könnte man dann aber Probleme mit lambdas bekommen. Allerdings sehe ich keinen Bedarf für weitere Initializer. */

Ich glaube nicht, dass man sich mit kleinen Hilfsmethoden wie swap und lazy-Initializern sonderlich weh tut und würde so etwas mit reinnehmen.

Was mir nur auffällt: es fehlt mir offensichtlich einiges an Know-How in diesem Bereich.


#12

[QUOTE=cmrudolph;94795]Die lazy-Initializer würde ich aber auch “left” und “right” nennen, eben mit einem Supplier als Parameter.[/QUOTE]

Ich weiß, dass das schöner aussieht, aber ich bin mit sowas schon in Probleme gerannt. Was ist, wenn wirklich jemand einen [inline]Either<Supplier,Supplier>[/inline] haben will?

zu 5. Nice to have

Mir ist gerade auf der Hollywoodschaukel ein lustiger Gedanke gekommen, den ich für [I]sehr [/I]“nice to have” halte - allerding muss ich erst noch sehen, ob das wirklich so geht, wie ich mir das vorstelle. Wie wäre ein DSL ähnlich Scalas [inline]match[/inline]? Das wäre auf jeden Fall praktisch für Either, Tuples, Optional und Listen, eventuell für mehr. Ich stelle mir das so vor:

Optional<Integer> opt = ...
String s = match(opt).cases(
  none(() -> "leer"),
  some(42, () -> "die Antwort!"),
  some(a -> "gerade").when(a -> a % 2 == 0),  
  defaultValue(x -> "nix gefunden: " + x.toString())
);

Das wäre auch etwas, das ich in anderen Frameworks noch nicht gesehen habe, und es passt sehr gut zu unserem “Kerngebiet”.

Ich teste das mal…

*** Edit ***

Ja, es funktioniert mit einigen Änderungen so. Hier der Code, der [inline]Optional[/inline] abdeckt:

import java.util.Optional;

public interface Case<T,R> {
    Optional<R> accept(T value);
}
import java.util.Optional;
import java.util.function.Function;
import java.util.function.Supplier;

import static java.util.Optional.of;

public final class Matcher {

    private Matcher() {}

    @SafeVarargs
    public static <T,R> R match(T value, Case<T,R> ... cases) throws MatchException {
        for(Case<T,R> c : cases) {
            Optional<R> result = c.accept(value);
            if (result.isPresent()) {
                return result.get();
            }
        }
        throw new MatchException();
    }


    public static <T,R> Case<T,R> Default(Supplier<R> supplier) {
        return value -> of(supplier.get());
    }
    public static <T,R> Case<T,R> Default(Function<T, R> fn) {
        return value -> of(fn.apply(value));
    }
}
public class MatchException extends RuntimeException {

    public MatchException() {}

    public MatchException(String message) {
        super(message);
    }

    public MatchException(String message, Throwable cause) {
        super(message, cause);
    }

    public MatchException(Throwable cause) {
        super(cause);
    }
}
import java.util.Optional;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.function.Supplier;

import static java.util.Optional.of;

public final class OptionalCases {
    private OptionalCases(){}

    public static <T,R> Case<Optional<T>,R> None(Supplier<R> supplier) {
        return t -> t.isPresent()
                ? Optional.<R>empty()
                : of(supplier.get());
    }

    public static <T,R> Case<Optional<T>,R> Some(T value, Supplier<R> supplier) {
        return t -> t.isPresent() && t.get().equals(value)
                ? of(supplier.get())
                : Optional.<R>empty();
    }

    public static <T,R> Case<Optional<T>,R> some(Function<T,R> fn) {
        return t -> t.isPresent()
                ? of(fn.apply(t.get()))
                : Optional.<R>empty();
    }

    public static <T,R> Case<Optional<T>,R> SomeIf(Function<T, R> fn, Predicate<T> predicate) {
        return t -> t.isPresent() && predicate.test(t.get())
                ? of(fn.apply(t.get()))
                : Optional.<R>empty();
    }
}
import java.util.Optional;

import static net.neco.core.matcher.Matcher.*;
import static net.neco.core.matcher.OptionalCases.*;

public class Test {

    public static void main(String[] args) {
        test(Optional.empty());
        test(Optional.of(42));
        test(Optional.of(12));
        test(Optional.of(13));
    }

    private static void test(Optional<Integer> opt) {
        String s = match(opt,
                None(() -> "leer"),
                Some(42, () -> "die Antwort!"),
                SomeIf(a -> "gerade", a -> a % 2 == 0),
                Default(x -> "nix gefunden: " + x.toString())
        );
        System.out.println(s);
    }
}

Sorry für die Großschreibung, so sieht es aber fast wie Scala aus :slight_smile:

*** Edit ***

Ich habe mal auf bitbucket.org ein 5-Mann-Projekt neco4j (ID neco4j angelegt). PW per PN.


#13

Wie soll die Kommunikation zum Projekt stattfinden? Dieser einzelne Thread hier wird wohl nicht ausreichen.
Klassisch per Mailinglist? Ein Unterforum hier?


#14

Ich wäre für ein Unterforum. Eine Mailingliste können wir immer noch aufsetzen, wenn es wirklich nötig werden sollte.

*** Edit ***

Ich habe Eagle um ein Unterforum gebeten.

Übrigens ist schon jemand auf die Idee mit dem Pattern-Matching gekommen (auch wenn ich es ganz bestimmt nicht so kompliziert machen will): http://kerflyn.wordpress.com/2012/05/09/towards-pattern-matching-in-java/

Aber ich spiele damit erst mal nur herum - es muss erst mal geklärt werden, ob wir das überhaupt mit aufnehmen.


#15

Bekanntlich ist ja neco4j den Heldentod gestorben, und nachdem JavaSlang so ziemlich alles macht, was wir ursprünglich angepeilt hatten, will ich es auch nicht in der alten Form wiederbeleben.

Aber ich spiele zur Zeit mit ein paar verrückten Collection-Ideen herum, und würde das Projekt gern dafür umbiegen, falls niemand andere Pläne hat. Alles als Ein-Mann-Show, ohne neue Projektseite hier u.s.w.


#16

Tu dir keinen Zwang an :wink:


#17

Kein Problem. Aber … spricht was dagegen, diese Ideen hier etwas breitzutreten?


#18

Es sind hauptsächlich zwei Ideen:

  • Verwendung von Self-Types
  • Integration von Maps, jede Collection hat auch “Keys” für den Zugriff (für wahlfreie Listen ist der Key-Typ z.B. Integer, für Dequeues wäre es ein enum mit FRONT und BACK u.s.w.)

Das Basis-Interface sieht etwa so aus (ohne Gewähr):

public interface Coll<K, V, C extends Coll<K, V, C>> {
    Optional<C> addOpt(K k, V v);
    Optional<V> getOpt(K k);
    Optional<C> removeOpt(K k);
    boolean isEmpty();
    long size();
    default C self() {
        return (C) this; 
    }
}

Natürlich können über Unter-Interfaces jeweils geeignetere Methoden eingeführt werden, z.B. wenn in einer Collection ein add immer gelingt, braucht man kein Optional<C> als Rückgabewert.

Von Iterable wird erst “weiter unten” abgeleitet, weil z.B. nicht jede Collection auch die Keys braucht u.s.w.

Die eigentlichen Implementierungen haben eine ganz normale Signatur wie Stack<V>.


#19

Das self sieht auf den ersten Blick stark nach dem getThis-Trick aus - aber vielleicht habe ich da auch irgendwas noch nicht in der nötigen Tiefe erfasst.


Den Gedanken, List<T> := Map<Integer, T> zu setzen hatte ich auch schon gelegentlich, und auch in anderen Zusammenhängen mal angesetzt. (Das bezog sich aber auf “Records” und “Tables”, aber mit einiger weiteren Infrastruktur für Datenverarbeitung/Modellierung drumherum…). Auf der tiefsten Ebene (d.h. auf Ebene der Collections-API, wo diese Collections “Selbstzweck” sind) weiß ich nicht, ob man so eine Gleichsetzung wirklich gewinnbringend ausnutzen könnte. Sicher würden manche Funktionen vereinheitlicht, aber… um das ganze semantisch stimmig und konsistent zu machen, ist sicher einiges an Hirnschmalz und Überlegungen nötig.

Sponan: Was liefert keySet bei so einer “MapList”? Alle Indizes? Was passiert, wenn man aus diesem KeySet ein Element entfernt? Der Punkt ist: Durch Änderungen an der Liste ändert sich das Key-Value-Mapping! (Derselbe Key zeigt nachher auf eine andere Value!). Aber das sind nur erste Gedanken.


Optional<V> getOpt(K k);

Unabhängig von der Frage, ob diese Optional-Rückgabetypen sinnvoll sind, oder nicht (gehen wir mal davon aus, dass sie es sind) : Der Gedanke, dort ein K für den Key übergeben zu können, ist, gelinde gesagt, optimistisch :slight_smile: Es ist nicht offensichtlich. Und ich habe das (bei meinen Table/Record-Experimenten) zuerst auch versucht, obwohl ich die folgende Aussage von Josh Bloch kannte, aber eben nicht glauben wollte. Aber inzwischen glaube ich sie: Es funktioniert einfach nicht. (Mal sehen, ob du zum gleichen Schluss kommst :smiley: )


#20

Klar, das ist die Java-Version des allseits bekannten und beliebten CRTP.

Erst einmal sind Collections keine Map, und K muss sich demnach nicht wie ein Map-Key verhalten. Eventuell gibt es gar keine Möglichkeit, alle Keys zu listen. Im Fall eine “MapList” wäre vielleicht eine Range der richtige Rückgabetyp.

Natürlich ist es nicht klar, ob so eine Hierarchie wirklich tragfähig ist, aber meines Wissens ist etwas in dieser Form in Java noch nicht versucht worden. Weiterhin wird es immer irgendwelche collectionartigen Datenstrukturen geben, die sich in eine gegebene Collection-Hierarchie nicht sinnvoll einfügen lassen (z.B. bei Java Map, und bei meinem Entwurf Either oder auch bestimmte Lazy-Collections). Der Entwurf hat aber das Potential, deutlich mehr Datenstrukturen abzudecken (um den Preis einer etwas umständlicheren API, was ich aber durch Interfaces mit Default-Methoden abzumildern gedenke).