Map-Basierte Collections?

Hier ein Vorschlag, an dem ich schon eine Weile herumüberlege (und der sicher noch nicht ausgegoren ist), aber dazu dienen könnte, unsere Collections sehr zu vereinheitlichen, und (im Gegensatz zu Java-Collections) schon auf der obersten Ebene ein vernünftiges Arbeiten zu erlauben: Angenommen, unser Ober-Interface hätte eine map-artige Signatur NecoCollection<K,V>. Die K-Werte sind dabei wie die Schlüssel einer Map immer duplikatfrei, die V-Werte können Duplikate enthalten. Die Ordnung (oder deren Abwesenheit) hängt ebenfalls stets an den K-Werten. Wir hätten:

  • NecoMap<K,V> extends NecoCollection<K,V>
  • NecoIndexedList<V> extends NecoCollection<Integer,V>
  • NecoLinkedList<V> extends NecoCollection<Cons<V>,V> - basierend auf der Object-Identität von Cons<V>, wie bei einer IdentityHashMap
  • NecoSet<K> extends NecoCollection<K,Void>
  • NecoMultiSet<K> extends NecoCollection<K,Integer>
  • NecoMultiMap<K,V> extends NecoCollection<K,NecoList<V>>

Dazu noch Interfaces für die Anordnung der K-Werte (chaotisch, Einfügereihenfolge, sortiert).

Meinungen? Ist das zu abgespaced? Erst man Code anschauen?

Oh, ich hatte deinen Beitrag gelesen, aber vergessen dazu was zu sagen.
Den Gedanken finde ich eigentlich ziemlich interessant. Wohin das führt, ist für mich bisher aber noch schwer absehbar.
HashSet aus java.util.collections basiert übrigens auch auf HashMap - der Ansatz ist also vom Prinzip her gar nicht soo abwegig.

Ja, ich hatte es auch schon gelesen, aber meine Gedanken dazu noch nicht geordnet (und) niedergeschrieben.

Einerseits erscheint es sinnvoll und nahe liegend. An einigen Stellen hatte ich schon die “Dualität” ausgenutzt, die man erahnen kann, z.B. mit einer `Map<Integer, T> asMap(List list)[/inlne].

Andererseits stellen sich dabei einige Fragen, auf verschiedenen Ebenen.

Auf der obersten Ebene steht die Frage, die ich schonmal im anderen Forum unter der Überschrift “Abstraktions-Overkill” gestellt hatte (und der etwas reißerisch oder potentiell negativ klingende Titel soll hier keine Wertung sein ;)). Damals hatte ich angedeutet, dass man praktisch alles, was man schreibt, auf Function und Set zurückführen kann. Wie schon in http://forum.byte-welt.net/threads/12534-Mathematische-Sets-in-neco4j angedeutet ist eine Mathematische Menge ja gleichwertig mit einem Prädikat, nämlich dem, das aussagt, ob ein Element in der Menge ist oder nicht. Und ein Prädikat ist eine Function (von T auf boolean). Wenn man die Vereinigung zweier Mengen beschreiben will, kann man das mit einem Operator, der so gesehen auch nur eine Function<Tuple2<Set<T>, Set<T>>, Set<T>> ist. Mir ist nicht klar, an welcher Stelle man mit der Abstraktion aufhören soll…

Im krassen Gegensatz zu dieser (übergeordnet-philosophischen) Frage (die ohnehin nie oder zumindest nicht objektiv) beantwortet werden kann, könnte man jetzt gleich die Frage nach der Performance stellen, wenn man immer (z.B. für indizierten Zugriff) aufs Auto(un)boxing zwischen int und Integer vertrauen muss - aber sei das erstmal zweitrangig (die JVMs der Zukunft werden das schon richten ;))

Dazwischen liegt aber noch die (erstmal wichtigere) Frage nach der “Konsistenz”, bzw. der Einhaltung des “Principle of Least Astonishment”. Die bezieht sich speziell auf den indizierten Zugriff: Eine NecoIndexedList<V> extendet NecoCollection<Integer,V>.

NecoIndexedList<V> list = createListWithSize(3);
V v0 = list.get(0);
V v1 = list.get(1);
V v2 = list.get(2);

NecoIndexedList<V> modifiedList = list.remove(1);

// Welche der folgenden Zeilen liefert eine NoSuchElementException?
V mv0 = modifiedList.get(0);
V mv1 = modifiedList.get(1);
V mv2 = modifiedList.get(2);

// (Unabhängig davon: )

// Welcher der folgenden Ausdrücke ergibt "true"?
boolean b0 = (v0 == mv0);
boolean b1 = (v1 == mv1);
boolean b2 = (v2 == mv2);

boolean b3 = (v2 == mv1); // !?

Nicht, dass man sie nicht beantworten könnte, aber es gibt viele Details, die man da berücksichtigen muss…

was sind denn die vielen Details und die 20 Zeilen Code klingen auch hochtrabend,
aber sollte das nicht ein Test sein der mit beliebig austauschbarer Liste, auch ArrayList, genauso funktioniert?

natürlich muss (doch sicherlich) bei einem remove alles um einen Index aufrücken, wie in jeder Liste,
alles andere wäre doch nicht nutzbar, das Verhalten der Liste muss klar sein, die Implementation richtet sich danach,
bisschen viel für diese eine kleine Frage


im übrigen, zuvor habe ich mir das verkniffen:

in ‘Neco’ fehlt ein r :wink:

Welche der folgenden Zeilen liefert eine NoSuchElementException?

Keine. Der letzte Aufruf liefert eineIndexOutOfBoundsException.

Welcher der folgenden Ausdrücke ergibt “true”?

Wir können ein V nicht klonen oder erzeugen, also nur kopieren. Also 17. true, 18. true, 19. gibts nicht, 21. abhangig davon, ob der zweite und dritte Eintrag in der Liste das gleiche Objekt ist.

NecoCollection ist keine Map und erst reicht keine Map-Implementierung, es ist erst einmal nur ein “kleinster gemeinsamer Nenner” zwischen den Collections, der durch die Key-Value-Semantik vielleicht etwas nützlicher und vielseitiger ist als java.util.Collection (das ja durch sein Design das Map-Interface zu etwas Seperatem macht, obwohl diese z.B. viele Gemeinsamkeiten mit Set hat).

OK, das ist so gesehen legitim. Wenn man eine Methode hat wie

void doSomething(NecoCollection<Integer,V> c)
{
   V value = createValue();
   c = c.add(345, value);
   c = c.remove(344); 
   V result = c.get(344); // Was passiert hier?
...

weiß man erstmal nicht, was da genau passiert oder passieren kann, weil man nicht weiß, ob das Ding, das man da bekommt, Map-Semantik oder List-Semantik hat, aber … das ist ja analog zu Collection

so gesprochen und danach nicht widersprochen,
sehe ich nun alles falsch oder müsste nicht 18. abhängig sein und 21. in jedem Fall true?

es rückt doch alles (bzw. das einzige dritte Element) auf, mv1 ist das ehemalige v2?

Ach ja, irgendwie war ich auf dem Trichter, dass das letzte Element entfernt wurde. Sollte halt nicht zwischen Tür und Angel antworten…

[QUOTE=SlaterB][…]
es rückt doch alles (bzw. das einzige dritte Element) auf, mv1 ist das ehemalige v2?[/QUOTE]

Bei der vorgeschlagenen NecoIndexedList sollte gar nichts aufrücken. Eigentlich ist das ein Array und sollte auch so heissen, NecoVector oder ähnlich. Arrays sind prinzipiell Dictionaries wobei die Schlüssel aus einem vorgegebenen, kontinuierlichen Bereich der Ganzzahlen stammen. Clojure z.B. definiert einen Haufen Interfaces zur Strukturierung der ganzen Datenstrukturen, vll. könnt ihr euch ja davon inspirieren lassen.

Was soll dann in der entstandenen “Lücke” stehen? null? Halte ich für keine gute Idee.

Clojure als dynamisch getypte Sprache ist kein gutes Vorbild. Interfaces außerhalb einer Hierarchie sind unpraktisch, und zuviele Stufen innerhalb der Hierarchie auch. Schaut man auf die Java-Collections, hätte man z.B. Collection.add, clear, remove u.s.w. in ein Unter-Interface ModifyableCollection packen können. Hat man bewusst nicht getan, weil dann Collection selbst kaum noch nützlich gewesen wäre. Lieber nimmt man hier in diesen Methoden UnsupportedOperationExceptions in Kauf, als Collection-Rückgabewerte in ModifyableCollections casten zu müssen (ein Problem, das man in Clojure natürlich nicht hat). Das ist alles Folge des fehlenden Self-Types in Java (und wie ich schon irgendwo geschrieben hatte, hilft hier auch das CRTP nicht weiter, an einigen Stellen wie map und flatMap ist echter Higher-Order-Polymorphismus nötig).

Null würde aber mehr dem “Java-Sinn” bei assoziativen Datenstrukturen entsprechen. Der Inhalt hinter den Keys soll sich ja nicht ändern nur, weil ein Key “entfernt” wird, was aber das Ergebnis wäre wenn alles aufrückt. Und Clojure macht das so feingranular über die vielen Schnittstellen damit den Datenstrukturen relativ differenziert das entsprechende Verhalten gegeben werden kann. Aber du hast mit deiner Argumentation schon recht, ich hatte bei meinem Beitrag die eigentliche Listen-Semantik “vergessen” und war irgendwie auf Array-Semantik aus, bzw. wohl etwas durch “remove”-verwirrt und wie es interpretiert werden soll.