Mathematische Sets in neco4j

Byte-Welt - Projekte / Projects neco4j
1

Auch wenn die grundlegende Diskussion um die List herum noch (oder doch nicht mehr?) im Gange ist, wollte ich mal fragen, welche Gedanken es zu “Set” gibt.

Der Anlass ist, dass ich da schonmal drüber nachgedacht hatte, und eben auf Umwegen wieder drüber gestolpert bin. Damals war meine Intention, etwas zu machen, was einer mathematischen Menge möglichst nahe kommt (aber trotzdem noch einigermaßen vernünftig verwendbar ist). Das ist weitaus schwieriger, als man im ersten Moment meinen würde. Manche Sachen sind straightforward:

public interface MathSet<T>
{
    boolean contains(Object object);
}
// ( ^Das war's dann aber auch schon...)


public interface CartesianProductMathSet<X, Y> extends MathSet<Tuple2<X, Y>>
{
    MathSet<? extends X> getMathSetX();
    MathSet<? extends Y> getMathSetY();
    
}

...

Ein paar nahe liegende Implementierungen dazu…

class DifferenceMathSet<T> implements MathSet<T>
{
   ...
    @Override
    public boolean contains(Object object)
    {
        return s0.contains(object) && !s1.contains(object);
    }
}

class IntegerNumbersRange implements MathSet<Integer>
{
    private final int min;
    private final int max;
    ...
}

Aber das ist natürlich nicht unzureichend. Für eine Interoperation mit java.util.Set bräuchte man zumindest noch eine Implementierung von Iterable. Das funktioniert auch ganz gut…

public interface EnumerableMathSet<T> extends MathSet<T>, Iterable<T>
{
    ...
}
class IntegerNumbersRange implements EnumerableMathSet<Integer> 
{
...
}

Das führt aber irgendwann zur (schon fast “üblichen”) kombinatorischen Explosion von Eigenschaften (ImplicitEnumerableIntersectionMathSet und DefaultEnumerableCartesianProductMathSet poste ich jetzt mal nicht :rolleyes: ).

Die Eigenschaften geeignet und stimmig abzubilden ist ziemlich schwierig. Im speziellen wäre eine size()-Methode eben oft praktisch. Beim IntegerNumbersRange ist sie noch straightforward, beim DoubleNumbersRange schon nicht mehr. Vom size eines DifferenceMathSet oder gar der Frage nach einer geeigneten Implementierung von equals mal ganz abgesehen:

Range.of(0,10).union(Range.of(5,15)).equals(Range.of(0,15));? Nie und nimmer…

Das sind nur erste (alte) Gedanken, die mit neco4j eigentlich nichts zu tun haben. Aber vielleicht ist eine Rechtfertigung dafür, das anzusprechen, ja zumindest die, dass Überlegungen zu “anderen Datenstrukturen als List” auch Einfluss auf List haben könnten…

2

Darüber hatte ich auch schonmal nachgedacht. Deine Definition von MathSet entspricht java.util.Predicate. Aber Iterable sollte es praktischerweise schon sein, und auch size haben.

Eine wichtige Frage ist, wie wir das Hinzufügen oder Entfernen von Elementen realisieren. Eventuell muss sich dazu das unterliegende Set ändern, etwa wenn aus einer Range in der Mitte ein Element entfernt wird.

Über das Problem mit der kombinatorischen Explosion habe ich auch schon nachgedacht, bin aber nicht sehr weit gekommen. Mir schwebte eine Art Baukastensystem von Collections vor, aber dafür scheint mein Gehirn oder Javas Typsystem nicht flexibel genug zu sein.

3

Im Zweifelsfall eher letzteres (bei solchen “abstrakten” Dingen (also allem, was über eine Person-Bean hinausgeht :D) stößt man schon recht schnell an die Grenzen).

Meintest du bei dem “Baukastensystem” sowas ähnliches (!) wie “Traits”?

Tatsächlich gab es DAS java.util.Predicate noch nicht, als ich damit das erste Mal angefangen hatte (ist schon ne Weile her), aber da es damals nicht nur um “MathSets” ging, sondern um allgemeine mathematische Strukturen (enschließlich Predicate, Function & Co) stand eine Ineinanderüberführbarkeit von Mengen und Predicaten aber schon im Raum - sie sind ja “strukturell gleich”.

So ein MathSet sollte aber (“natürlich”) ohnehin unveränderlich sein. Im JavaDoc hatte ich da schon sowas geschrieben wie ~“Eine mathematische Menge ist unveränderlich. Wenn man ein Element aus einer Menge entfernt, ist es einfach nicht mehr dieselbe Menge” (ganz klassisch, immutable, darum ging es hier ja nicht zuletzt). Ich gehe davon aus, dass es vieeele Papers gibt, wo beschrieben ist, wie man sowas ganz geschickt mit Bäumen implementiert. Bisher könnte das Entfernen einzelner Elemente ganz straightforward und “pragmatisch” als

{a,b,c} - a = {a,b,c} \ { a } = DifferenceMathSet

abgebildet werden.

Ingesamt kann man da schon sehr viel auf sehr elementare Funktionen runterbrechen. Aber wenn man nur so ein “minimales Erzeugendensystem” bereitstellt, kann das ziemlich unbequem zu verwenden sein, und ggf. ist der tatsächliche Nutzen dann nicht so hoch. Als plakative Analogie: ++ reicht. Damit kann man + nachbauen. Und damit dann *. Und damit dann Math.pow (das hätte mit den Sets zumindest gemein, dass es schreeecklich ineffizient wäre).

“Iterable” und “Size” könnten/sollten zwei voneinander unabhängige Dinge sein. Gerechtfertigt wird das gerade bei mathematischen Mengen ja durch die Eigenschaften endlich, abzählbar unendlich und überabzählbar unendlich. Es spricht nichts dagegen, eine MathSet<Long> für die natürlichen Zahlen zu erstellen, die zwar keine sinnvolle (!) size hat, aber Iterable ist. Der schmerzvoll-pragmatische Ansatz, das aufzudröseln in

interface MathSet<T> { boolean contains(Object t); }
interface FiniteMathSet<T> ... { int getSize(); }
interface EnumerableMathSet<T> ... { Iterator<T> iterator(); }

bringt ja nichts. Ich hatte jetzt zuletzt gedacht, dass man einfach alles ins MathSet packt und Optional macht (obwohl ich dem Optional bisher etwas skeptisch gegenüberstand, weil es das Potential hat, als ein "unübersichtliches null" überstrapaziert zu werden - aber in DIESEM Fall könnte es ganz gut passen).

Auch kann es schnell philosophisch werden: Je nachdem, wie “mächtig” das ganze werden soll, landet man schnell an Punkten, die nichts mehr mit der Implementierung einer praktischen Bibliothek zu tun haben, aber trotzdem (!) noch so unbehaglich weit weg sind von dem, was man mit Bleistift und Papier einfach so hinschreiben kann. Die Frage, wie man equals implementieren soll, hatte ich schon angedeutet, aber darüber hinaus gibt es eben einige Operationen, die schwierig sind, wenn man die Mengen nicht “explizit” konstruiert und als Set vorhält - andererseits fand ich aber gerade diesen Gedanken des “nicht-explizit-konstruieren-müssens” besonders reizvoll.

Und das alles noch abgesehen von Details…

MathSet<BigInteger> primes = MathSets.fromPredicate(BigInteger::isPrime);
MathSet<BigInteger> range = Range.of(1, 10);

MathSet<BigInteger> a = primes.intersect(range);
a.contains(someVeryLargeBigInteger); // Prüft erst "isPrime" und dann "range.contains" - dauert Minuten

MathSet<BigInteger> b = range.intersect(primes);
b.contains(someVeryLargeBigInteger); // Prüft erst "range.contains" und gibt 'false' zurück - dauert Mikrosekunden...

… über die ich mir (noch?) keine Gedanken mache(n will).

Man könnte viele der Fragen auf ein Abwägen zwischem “praktischem Nutzen” und “theoretischer Schönheit” oder “weitest-möglicher Abstraktion” runterbrechen. (Ich sehe FunctionalJava als so ein Beispiel, das irgendwie halt cool und interessant ist, aber dann doch ziemlich akademisch und “praxisfern”). Aber so formuliert greift das zu kurz. Es geht ja nicht zuletzt auch um die Frage, inwieweit die neuen Sprachmittel es ermöglichen, einen “praktischen Nutzen” aus Dinge zu ziehen, die bisher noch “akademisch” erschienen.

4

Intervalle als Erzeuger einer Menge sind abgesehen von den ganzen Zahlen wohl ziemlich kritisch zu betrachten.
Und oberflächlich betrachtet macht auch „abzählbar unendlich“ und „überabzählbar unendlich“ in Java keinen Unterschied, weil sich überabzählbar unendliche Mengen (genannt sei einfach mal R) nicht von dicht darin liegenden, abzählbar unendlichen Mengen (genannt sei Q) unterscheiden können. Dazu wäre eine unendlich hohe Genauigkeit erforderlich. Es ließe sich also nur über ein Flag realisieren. Und einen praktischen Nutzen sehe ich da nicht :wink: Zumal der Unterschied selbst auf dem Papier nicht konkret darstellbar ist.

Um sinnvoll damit arbeiten zu können, könnte man vielleicht „Intervall-Sets“ einführen, bei denen die enthaltenen Werte nur implizit vorhanden sind.
Potenzmengen sind auch eine Sache, die man wegen des Wachstums wahrscheinlich besser implizit speichert (so wie in #3 ja auch beschrieben).

Um ein equals zu implementieren, müsste man wahrscheinlich eine Normalform entwerfen, die man dann vergleichen kann. Ansonsten ginge das ja nur explizit.

Das sind nur ein paar ungeordnete Gedanken zu dem Thema…

*** Edit ***

Achso, zum size noch: soll das die Mächtigkeit angeben? Die ist bei Intervallen aber ziemlich schnell Integer.MAX_VALUE oder wie auch immer man [tex]\infty[/tex] darstellen möchte.

5

Ja, einige der Punkte wurden ja schon angedeutet (aber eine Lösung erscheint mir ziemlich weit weg).

Zwischen “abzählbar unendlich” und “überabzählbar unendlich” zu unterscheiden macht IMHO schon einen Unterschied. Das Intervall LongRange.startingAt(0) ist unendlich groß, und man kann einen Iterator erstellen, der einfach longs hochzählt - unendlich lange. Das Intervall DoubleRange.of(0.0, 1.0) ist auch unendlich groß, aber man kann nicht sinnvoll drüberiterieren. (Ich hatte zwar schon an Math.ulp gedacht, aber DAS ist dann endgültig Praxisfern). Dass bestimmte Unzulänglichkeiten schon durch das mapping von mathematischen Strukturen auf den Rechner entstehen, muss man wohl antizipieren (gemeint ist hier, dass R und Q beide (!) durch double nicht wirklich sinnvoll repräsentiert werden können. Dem Q könnte man zwar mit einem Quotienten aus zwei BigIntegers etwas näher kommen, aber da müßte man noch an anderen Stellen nachbessern). Nebenbei: Für viele dieser Punkte speziell bezogen auf Ranges könnte man sich bei https://code.google.com/p/guava-libraries/wiki/RangesExplained Inspiration holen.

6

Theoretisch ist es richtig, dass der Unterschied zwischen abzählbar unendlich und überabzählbar unendlich darin liegt, dass man über eine abzählbare Menge iterieren kann.
Praktisch ist es aber nur in Spezialfällen möglich, wenn die Werte weit genug voneinander weg liegen und man ein nächstgrößeres Element bestimmen kann. Über Q wird man auch theoretisch betrachtet nicht sinnvoll iterieren können, weil es keine “nächstgrößere” Zahl gibt – es gibt immer eine weitere Zahl, die dichter an der letzten liegt, als die, die man bereits gefunden hat.
Dass die Menge abzählbar ist, kann man ja beweisen, indem man eine Iterationsreihenfolge festlegt (z. B. Cantors erstes Diagonalargument). Diese Reihenfolge entspricht aber nicht der Ordnung der Menge und ist daher IMHO unbrauchbar, denn wozu möchte man über eine unendlich große Menge in einer weitgehend zufälligen Reihenfolge iterieren?

7

Ja, ich dachte in diesem Moment nur an diese Aufzählreihenfolge für die Rationalen Zahlen. Aber auch allgemein kann das sinnvoll sein. Schließlich ist die Reihenfolge bei einer HashSet ja auch ““zufällig””. Implizit hast du aber einen weiteren Punkt angesprochen, der (neben Predicates, Functions und Sets) bei meinen ursprünglichen Überlegungen wichtig war, und zumindest auch für viele (theoretisch vorstellbare :D) praktische Anwendungen solcher Sets wichtig ist: Eine Reihenfolge bzw. eine Ordnung. Einerseits kann man ganz pragmatisch irgendwo einen Comparator dazuklatschen. Der ist aber definitiv nicht etwas, was direkt zur Menge gehört. Wenn man sklavisch den Definitionen folgt ( http://de.wikipedia.org/wiki/Ordnungsrelation ) könnte man zwar sagen

interface OrderedSet<T> // NICHT "extends MathSet<T>" !!!
{
    MathSet<T> getSet();
    Comparator<T> getOrder();
}

wobei man da erstens gleich wieder weiter fragen könnte, wie etwa ob die “Ordnungsrelation” nicht eine MathSet<Tuple2<T>> sein sollte, aber wichtiger: Oft will/muss man das Minimum und Maximum der Menge kennen (oder das Infimum und Supremum? Tja… :rolleyes: ). Und wenn man die Menge nicht aufzählen kann, kann man das nicht ausrechnen, sondern muss es festlegen. Sollten also

T getMinimum();
T getMaximum();

mit ins MathSet-Interface? Nee. Vielleicht ins OrderedSet-Interface? Naja. Aber wenn, dann beide natürlich wieder nur Optional… (Fragen über Fragen… ich werd’ da ggf. in der nächsten Zeit noch weiterbasteln, und mal ausprobieren, wie sich verschiedene Ansätze “anfühlen”. Nochmal: Das hat nicht direkt was mit neco4j zu tun. Aber über diese Fragen schonmal nachgedacht zu haben, kann sicher nicht schaden…)