Funktionale Stream-Klasse

Byte-Welt - Projekte / Projects neco4j
1

OK, ich habe mal ein wenig an der Stream-Klasse gearbeitet, und dafür einen neuen Branch “experimental” aufgemacht. Die Klasse ist hauptsächlich als Beispiel für eine listenartige, lazy Struktur gedacht, um zu sehen, was das für eine Collection-Interface bedeuten würde. Dabei treten z.B. Fragen auf, wie man mit einer (dort fehlenden) size()-Methode umgeht. Der Code selbst ist recht ungehobelt, und der Memoized-Mechanismus gefällt mir noch nicht so richtig (und wird sicher noch einmal überarbeitet) - für Anregungen bin ich dankbar.

Ansonsten scheint es eine Mehrheit für die Öffnung des Projekts zu geben. Es täte mir leid, falls jemand aussteigt, wenn der Code jetzt auf GitHub umziehen würde, aber ich sehe darin die Chance, mehr Feedback zu bekommen. Trotzdem würde ich noch einmal gerne eure Meinung dazu hören, bevor ich das so einfach Kraft meiner Wassersuppe entscheide.

2

Es ist für mich schwierig, alles auf Anhieb zu verstehen, von daher kann ich auch noch keine Verbesserungsvorschläge machen. Für mich ist das ein eher ungewohntes Feld - wenngleich es viele interessante Möglichkeiten bietet.
Was ich noch nicht verstehe ist: wie kann man einen derartigen Stream überhaupt verwenden, wenn man das Ende noch nicht kennt und der Stream rückwärts konstruiert wird? Eigentlich doch nur, indem man mindestens einmal einen tailSupplier verwendet, oder? Und problematisch wird es dann, wenn man einen Stream hat, der weniger als 10 Elemente besitzt und dessen toString()-Methode aufgerufen wird…

3

Fixed. Geht auch viel einfacher.

*** Edit ***

[QUOTE=cmrudolph;104499]Es ist für mich schwierig, alles auf Anhieb zu verstehen, von daher kann ich auch noch keine Verbesserungsvorschläge machen. Für mich ist das ein eher ungewohntes Feld - wenngleich es viele interessante Möglichkeiten bietet.
Was ich noch nicht verstehe ist: wie kann man einen derartigen Stream überhaupt verwenden, wenn man das Ende noch nicht kennt und der Stream rückwärts konstruiert wird? Eigentlich doch nur, indem man mindestens einmal einen tailSupplier verwendet, oder?[/quote]

Genau, irgendwo muss das Ding lazy sein. Es hat kein Ende (solange man nicht in eine Exception oder so rennt)

Und problematisch wird es dann, wenn man einen Stream hat, der weniger als 10 Elemente besitzt und dessen toString()-Methode aufgerufen wird…

Ein Stream besitzt immer unendlich viele Elemente (oder besser gesagt, die Fähigkeit, immer neue Elemente zu berechnen), die Frage ist, wieviele du auswerten willst.

Nehmen wir mal das:

Stream<Integer> s = Streams.unfold(Pair.of(0,1), pair -> Pair.of(Pair.of(pair.get2(), pair.get1() + pair.get2()), pair.get1()));

Das ist ein Stream der Fibonacci-Zahlen, und wenn wir BigInteger verwendet hätten, **aller **Fibonacci-Zahlen (bei der Implementierung hier gibt es natürlich einen Überlauf) - ist aber so schon hässlich genug. Wir können jetzt alles mögliche damit machen: Alle Elemente mit 42 multiplizieren, die durch 5 teilbaren herausfiltern, die 500 ersten Einträge wegschmeißen, oder die ersten 1000 Einträge in eine Liste packen. Wieviel davon **wirklich **im Speicher steht, hängt davon ab, wie weit du auf den Stream zugegriffen hast. Dabei findet jede Berechnung nur einmal statt (sonst könnten sich ja zwei Stream.head()-Aufrufe unterscheiden, etwa wenn der entsprechende Supplier System.currentTimeMillis zurückgibt).

Es wird so weit wie möglich nur das berechnet, was benötigt wird:

Stream<Integer> s = repeat(24);  // 24,24,24,24,24....
Stream<Integer> t = iterate(0, x -> x + 1);  //0,1,2,3,4,5....
Stream<Integer> u = Streams.zipWith(s,t, (a, b) -> a/b);  //24/0, 24/1, 24/2, 24/3, 24/4 ...
System.out.println(u.tail()); // Stream(24,12,8,6,4,4,3,3,2,2...)

Stream u enthält einen potentiellen „Division by 0“-Fehler, aber das ist kein Problem bei der Konstruktion. Bei der Ausgabe würde es dann natürlich knallen, aber wenn wir mit tail() den gefährlichen Bereich einfach „wegwerfen“, passiert ebenfalls nichts.

Ich habe übrigens repeat (und analog cycle) mit etwas (hässlicher) Trickserei so geschrieben, dass es der Defintion

//PSEUDOCODE
public static <A> Stream<A> repeat(A a) {
  Stream<A> s = Stream.<A>of(a, () -> s);
  return s;
}
``` entspräche, wenn das erlaubt wäre - tail zeigt einfach wieder auf den gesamten Stream. Auch das ist nur möglich, weil die ganze Struktur lazy ist.
4

D.h. wenn ich eine Datei als Stream von Zeilen auffasse und am Ende der Datei bin, habe ich die Unendlichkeit erreicht?

5

Ein (funktionaler, nicht I/O-) Stream wäre eine schlechte Abstraktion für eine Datei, weil man dann nur mit irgendwelchen Krücken arbeiten kann (wie etwa nur noch null-Zeilen nach dem Dateiende zu liefern). Ein Stream wäre z.B. geeignet, irgend einen Sensor abzufragen: Egal wann, es gibt immer einen neuen Wert. Das Beispiel mit Zahlenfolgen wie den Fibonacci-Zahlen hatten wir schon, auch ein Zufallszahlengenerator lässt sich gut in einen Stream verpacken. Kurz gesagt ist ein Stream eine spezielle “Liste für unendliche Sachen”, und nur dafür sollte er eingesetzt werden.

Die Datei würde besser in eine (bei großen Dateien idealerweise auch lazy arbeitende) Liste passen, da die eben ein “natürliches” Ende hat.

6

auch mal nachgestochert:

Streams oder auch Iteratoren sind doch ein sehr nützliches, von Listen sehr unterschiedliches Konzept,

  • benötigen quasi 0 Speicher statt grenzenlos viel, halleluja, was das allein bei Datei- oder DB-Datenmengen spart, auch intern in DB bei Join-Berechnungen usw.,
    die Welt könnte ohne gar nicht leben, müsste erfunden werden
  • ideale Verkapselung eben von IO oder DB oder Berechnung im Hintergrund, lange oder kurze Lade/ Berechnungszeiten, Pause bei Eingaben/ Reaktion anderer Quellen,
  • evtl. unbekannte Größe (bei Endlichkeit), kein immer bekannter Anfang, überhaupt keine Rückkehr zu vorherigen Elementen, kein Index-Konzept
  • evtl. komfortable Eingriffmöglichkeit, nach Berechnung beliebig Elemente zusätzlich enfügen/ filtern/ zusammenlegen (ZIP!)
  • dicker Wiki-Artikel Datenstrom – Wikipedia , prominente Verwendung für Medieninhalte, allgemein Übertragung, Shells, Netzwerk-, User-Eingabe, so viel überall, Arrays.stream(double) im neuen Java

und manches davon würdest du unter schrägen Konzept ‚lazy Liste‘ abbilden?
für den simplen Unterscheidungspunkt Ende ja oder nein?
was spielt denn das Ende für eine große Rolle? wie an genug offensichtlichen Beispielen zu sehen kann ein potentiell endloser Stream auch irgendwann einfach beendet werden und dann endlich Ruhe Verarbeitung dazu,

Ende oder nicht ist kein strukturell wesentlicher Unterschied, wie strukturbestimmend wichtig sind dagegen die anderen Punkte?

7

@Landei

Ich bin ein wenig ambivalent bzgl. des Beispiels das ein Stream eine gute Möglichkeit für einen Sensor wäre. Es klingt auf den ersten Blick gut, auf den zweiten stellt sich mir dann sofort die Frage was ist wenn der Verbraucher der Daten nicht hinterher kommt, der Sensor wird nicht einfach aufhören zu liefern. Wie möchtest du mit derartigen Situationen umgehen?

@SlaterB

Die Konzepte finde ich nicht so unähnlich. Mir fällt bisher nur ein wirklicher Unterschied ein und der ist das Listen bis zu einem gewissen Grad Speicher verbrauchen. Ich kann eine Liste aber auch funktional, lazy und potenziell unbeschränkt machen. Mies wird es dann wenn man ein foldRight auf einer unbeschränkten Liste versucht. :wink:

8

Gute Idee!

auch mal nachgestochert:

Streams oder auch Iteratoren sind doch ein sehr nützliches, von Listen sehr unterschiedliches Konzept,

  • benötigen quasi 0 Speicher statt grenzenlos viel, halleluja, was das allein bei Datei- oder DB-Datenmengen spart, auch intern in DB bei Join-Berechnungen usw.,
    die Welt könnte ohne gar nicht leben, müsste erfunden werden
  • ideale Verkapselung eben von IO oder DB oder Berechnung im Hintergrund, lange oder kurze Lade/ Berechnungszeiten, Pause bei Eingaben/ Reaktion anderer Quellen,
  • evtl. unbekannte Größe (bei Endlichkeit), kein immer bekannter Anfang, überhaupt keine Rückkehr zu vorherigen Elementen, kein Index-Konzept
  • evtl. komfortable Eingriffmöglichkeit, nach Berechnung beliebig Elemente zusätzlich enfügen/ filtern/ zusammenlegen (ZIP!)
  • dicker Wiki-Artikel Datenstrom – Wikipedia , prominente Verwendung für Medieninhalte, allgemein Übertragung, Shells, Netzwerk-, User-Eingabe, so viel überall, Arrays.stream(double) im neuen Java

Das beschreibt aber alles mehr oder weniger die Streams in Java. Der Unterschied zwischen einem funktionalen Stream und einem Iterator ist, dass der Stream eine echte Collection ist, und auch entsprechend Speicher belegen kann. Nur wenn der ursprüngliche Head „losgelassen“ wird, kann auch der GC ran. Iteriert man dagegen mit einem Muster stream = stream.tail();, wird in der Tat kaum Speicher gebraucht. Man hat also sozusagen die Wahl zwischen Iterator- und Collection-Verhalten.

und manches davon würdest du unter schrägen Konzept ‚lazy Liste‘ abbilden?
für den simplen Unterscheidungspunkt Ende ja oder nein?
was spielt denn das Ende für eine große Rolle? wie an genug offensichtlichen Beispielen zu sehen kann ein potentiell endloser Stream auch irgendwann einfach beendet werden und dann endlich Ruhe Verarbeitung dazu,

Ende oder nicht ist kein strukturell wesentlicher Unterschied, wie strukturbestimmend wichtig sind dagegen die anderen Punkte?

Es macht bei der Verarbeitung schon einen Unterschied, ob ich dauernd damit rechnen muss, auf ein Ende zu stoßen. Es ist ein wenig wie in der Mathematik mit endlichen und unendlichen Mengen. Letztere verhalten sich doch deutlich anders (und manchmal recht „unintuitiv“) als erstere. Manche Operationen ergeben bei einem Stream einfach keinen Sinn (etwa reverse), und die Datenstruktur bringt diesen Unterschied klar zum Ausdruck.

Ich verstehe auch nicht, was einer lazy-Liste so schräg sein soll: Ich habe tausend Zahlen, will alle mit 42 multiplizieren, und dann die ersten neunhundert droppen. Was spricht dagegen, die Multiplikation erst dann auszuführen, wenn das Ergebnis gebraucht wird (also in diesem Fall nur für die letzten hundert)?. Den Unterschied zu einer strikten Liste sieht man nur, wenn Seiteneffekte im Spiel sind (IO, Exceptions werden geworfen, mutable Listenelemente beziehen sich aufeinander), für alle „normalen“, seiteneffektfreien Operationen (und das sollten normalerweise in einem Programm die allermeisten Operationen sein) ist das Ergebnis exakt das gleiche.

Nebenbei bemerkt werden lazy Listen auch dafür benötigt, um von Streams ohne böse Überraschungen konvertieren zu können. Ein Beispiel:

Stream<Auto> s = ...

for(Auto a : s) {
   doSomethingWith(a); 
   if (test(a)) {
       break;
   }
}

Wie du schon bemerkt hast, verbraucht das so gut wie keinen Speicher, selbst nach Millionen von Durchläufen nicht (zumindest wenn s nicht noch irgendwo referenziert wird). Angenommen, wir wollen jetzt doch eine Begrenzung einführen:

for(Auto a : s.take(1000000)) {
   doSomethingWith(a); 
   if (test(a)) {
       break;
   }
}

Der Stream wird also in eine Liste umgewandelt. Ist die Liste strikt, stehen auf einmal 1000000 Elemente im Speicher (die eventuell nicht einmal benötigt werden). Wie willst du einem Nutzer begreiflich machen, dass hier ein Memory-Hit und ein Berechnungs-Spike auftritt, hier aber nicht:

int index = 0;
for(Auto a : s) {
   doSomethingWith(a); 
   if (index++ < 1000000 && test(a)) {
       break;
   }
}
9

@ThreadPool
so unklar alle Themen auch sind, zu deiner Anmerkung zu meinem ersten Posting fällt mir gar nicht mal was zu sagen ein :wink:

hierzu auch wieder 42 Cent:

[QUOTE=ThreadPool]was ist wenn der Verbraucher der Daten nicht hinterher kommt, der Sensor wird nicht einfach aufhören zu liefern. Wie möchtest du mit derartigen Situationen umgehen?
[/QUOTE]
was wäre denn die Alternative, Massenspeicherung in Datei?
ein Sensor könnte schon einfach aufhören Daten zu senden wenn nix abgeholt wird bzw. an irgendeiner Stelle intern wird nicht mehr weitergeleitet/ überschrieben,
Wiederaufnahme des Stream-Empfangs liefert übersprungen neue aktuelle Daten

10

[QUOTE=ThreadPool]@Landei

Ich bin ein wenig ambivalent bzgl. des Beispiels das ein Stream eine gute Möglichkeit für einen Sensor wäre. Es klingt auf den ersten Blick gut, auf den zweiten stellt sich mir dann sofort die Frage was ist wenn der Verbraucher der Daten nicht hinterher kommt, der Sensor wird nicht einfach aufhören zu liefern. Wie möchtest du mit derartigen Situationen umgehen? [/quote]

Ich dachte an Situationen, in denen der Nutzer “pollt”: Welche Temperatur misst du jetzt? Und jetzt? Und jetzt? Und jetzt? …

Andersherum - also wenn ein Strom von Ereignissen gepusht wird - wäre Stream wahrscheinlich nicht die beste Wahl. Sicher, er könnte blockieren, wenn er “leer” ist (und das kann eventuell vielleicht noch akzeptabel sein), aber wenn der Nutzer mit dem Lesen nicht hinterherkommt und auch keine Werte überspringen kann, wäre das natürlich das Rezept für ein Desaster.

11

@Landei
dass die Betrachtung mathematisch/ funktional ist, hast du ja fairerweise vorher schon eingebracht,
ich habe mich aber doch noch etwas auf den Umstand von Java und Programmierung bezogen,
wenn das alles keine Rolle spielt, dann braucht man auch darüber nicht zu diskutieren, also ich kann wenig folgen

[QUOTE=Landei]

for(Auto a : s.take(1000000)) {
   doSomethingWith(a); 
   if (test(a)) {
       break;
   }
}

Der Stream wird also in eine Liste umgewandelt. Ist die Liste strikt, stehen auf einmal 1000000 Elemente im Speicher (die eventuell nicht einmal benötigt werden).[/QUOTE]

zum Beispiel mit Stream auch nicht, kurz nachgeschlagen gibt es in der API keine take()-Methode, nicht dass ich überhaupt Java 8 (oder 7 …) ausführen könnte,
vielleicht hier im Projekt, wo ich allerdings auch nicht firm bin :wink:

strikte Liste sagt mir auch nicht recht was, 1 Mio. Autos in irgendeinen Speicher zu schreiben klingt aber unter allen Betrachtungen nicht intelligent
und die wenigen kaum unterscheidbaren Codes machen es anscheinend nicht erforderlich

falls s.take(1000000) Speicher vollschreibt, verstehe ich einen ernsten Vorwurf an diese Methode, deren Schreiber und der evtl. Philosophie dahinter (strikte Listen?)
mein Posting trägt dafür hoffentlich keine Verantwortung, falls doch dann gewiss nicht so geplant :wink:

edit: ich könnte da eher in meinem Sinne rauslesen:
„s.take(1000000) sollte genauso einen Stream herauslesen wie zuvor, ohne Speicherleck, ob unendlich oder begrenzt auf 1 Mio. macht eben keinen Unterschied,
denn Ende oder nicht ist eben kein wichtiges struktureller Baustein von Streams (zur gigantischen Unterscheidung von Listen)“ :wink:
ginge natürlich kaum ohne s selber kaputt zu machen usw., das ist in der Natur der (realen, nicht funktionalen) Sache

12

@SlaterB Wir reden aneinander vorbei, es geht die ganze Zeit um die Stream-Klasse für neco4j:

[spoiler]

public final class Stream<A> implements Iterable<A> {

    private Supplier<A> head;
    private Supplier<Stream<A>> tail;

    private Stream(Supplier<A> head, Supplier<Stream<A>> tail) {
        this.head = head;
        this.tail = tail;
    }

    public static <A> Stream<A> of(A head, Stream<A> tail) {
        return new Stream<A>(new Evaluated<A>(head), new Evaluated<Stream<A>>(tail));
    }

    public static <A> Stream<A> of(A head, Supplier<Stream<A>> tailSupplier) {
        return new Stream<A>(new Evaluated<A>(head), tailSupplier);
    }

    public static <A> Stream<A> of(Supplier<A> headSupplier, Stream<A> tail) {
        return new Stream<>(headSupplier, new Evaluated<>(tail));
    }

    public static <A> Stream<A> of(Supplier<A> headSupplier, Supplier<Stream<A>> tailSupplier) {
        return new Stream<>(headSupplier, tailSupplier);
    }

    public A head() {
        A result = head.get();
        if (! (head instanceof Evaluated)) {
            head = new Evaluated<>(result);
        }
        return result;
    }

    public Stream<A> tail() {
        Stream<A> result = tail.get();
        if (! (tail instanceof Evaluated)) {
            tail = new Evaluated<>(result);
        }
        return result;
    }

    //all prefixes of the current stream
    public Stream<NecoList<A>> inits() {
        return Stream.<NecoList<A>>of(NecoList.<A>empty(), () -> tail().inits().map(list -> NecoList.cons(head(), list)));
    }

    //all suffixes of the current stream
    public Stream<Stream<A>> tails() {
        return Stream.<Stream<A>>of(this, () -> tail().tails());
    }

    public <B> Stream<B> map(Function<? super A, ? extends B> fn) {
        return Stream.<B>of(() -> fn.apply(head()), () -> tail().map(fn));
    }

    //takes the "main diagonal" when the generated stream of streams is written as 2D table
    public <B> Stream<B> flatMap(Function<A, Stream<B>> fn) {
        return flatten(map(fn));
    }

    //takes the "main diagonal" when the stream of stream is written as 2D table
    public static <A> Stream<A> flatten(Stream<Stream<A>> nested) {
        return Stream.<A>of(() -> nested.head().head(), () -> flatten(nested.tail().map(a -> a.tail())));
    }

    public Stream<A> dropWhile(Predicate<? super A> predicate) {
        return dropUntil(predicate.negate());
    }

    public Stream<A> dropUntil(Predicate<? super A> predicate) {
        for (Stream<A> stream = this; ; stream = stream.tail()) {
            if (predicate.test(stream.head())) {
                return stream;
            }
        }
    }

    public NecoList<A> take(int n) {
        NecoList<A> result = NecoList.empty();
        for (A a : this) {
            if (n-- <= 0) {
                break;
            }
            result = NecoList.cons(a, result);
        }
        return result.reverse();
    }

    public Stream<A> drop(int n) {
        Stream<A> result = this;
        while (n-- > 0) {
            result = result.tail();
        }
        return result;
    }

    public Stream<A> filter(Predicate<? super A> predicate) {
        Stream<A> stream = this.dropUntil(predicate);
        return Stream.<A>of(stream.head(), () -> stream.tail().filter(predicate));
    }

    public <B> Stream<B> scan(B seed, BiFunction<? super B, ? super A, ? extends B> fn) {
         return Stream.<B>of(seed, () -> tail().scan(fn.apply(seed, head()), fn));
    }

    public Stream<A> scan1(BiFunction<? super A, ? super A, ? extends A> fn) {
        return tail().scan(head(), fn);
    }

    @Override
    public Iterator<A> iterator() {
        return new Iterator<A>() {

            private Stream<A> stream = Stream.this;

            @Override
            public boolean hasNext() {
                return true;
            }

            @Override
            public A next() {
                A result = stream.head();
                stream = stream.tail();
                return result;
            }
        };
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("Stream(");
        int i = 10;
        for (Stream<A> stream = this; i-- > 0; stream = stream.tail()) {
            sb.append(stream.head()).append(i > 0 ? "," : "...)");
        }
        return sb.toString();
    }

    private static class Evaluated<A> implements Supplier<A> {

        private final A a;

        private Evaluated(A a) {
            this.a = a;
        }

        @Override
        public A get() {
            return a;
        }
    }

}

… sowie zugehörige Streams-Klasse mit statischen Methoden:

public final class Streams {
    private Streams() {
    }

    public static <S, T> Stream<T> unfold(S seed, Function<? super S, Pair<S, T>> fn) {
        Pair<S, T> pair = fn.apply(seed);
        return Stream.<T>of(pair.get2(), () -> unfold(pair.get1(), fn));
    }

    public static <A> Stream<A> iterate(A a, Function<? super A, ? extends A> fn) {
        return Stream.<A>of(a, () -> Streams.<A>iterate(fn.apply(a), fn));
    }

    public static <A> Stream<A> repeat(A a) {
        Stream<?>[] ref = new Stream<?>[1];
        Stream<A> result = Stream.<A>of(a, () -> (Stream<A>) ref[0]);
        ref[0] = result;
        return result;
    }

    @SafeVarargs
    public static <A> Stream<A> cycle(A... as) {
        switch (as.length) {
            case 0:
                throw new IllegalArgumentException();
            case 1:
                return repeat(as[0]);
            default:
                Stream<?>[] ref = new Stream<?>[1];
                Stream<A> result = Stream.<A>of(as[as.length - 1], () -> (Stream<A>) ref[0]);
                for (int i = as.length - 2; i >= 0; i--) {
                    result = Stream.of(as**, result);
                }
                ref[0] = result;
                return result;
        }
    }

    public static <A> Stream<A> intersperse(Stream<A> stream, A a) {
        return Stream.<A>of(stream::head, () -> Stream.<A>of(a, intersperse(stream.tail(), a)));
    }

    public static <A> Stream<A> interleave(Stream<A> first, Stream<A> second) {
        return Stream.<A>of(first::head, () -> interleave(second, first.tail()));
    }

    public static <A, B, C> Stream<C> zipWith(Stream<A> streamA, Stream<B> streamB, BiFunction<? super A, ? super B, ? extends C> fn) {
        return Stream.<C>of(() -> fn.apply(streamA.head(), streamB.head()),
                () -> zipWith(streamA.tail(), streamB.tail(), fn));
    }

    public static <A, B> Stream<Pair<A, B>> zip(Stream<A> streamA, Stream<B> streamB) {
        return zipWith(streamA, streamB, Pair::of);
    }

}

[/spoiler]

Das ist eine “echte” Collection (im Gegensatz zu Java8-Streams), wirklich “unendlich” und unglaublich lazy.

Es wird wirklich Zeit, den Code auf GitHub zu stellen.

13

Mein OK hast du.

14

habe ich ja auch schon selber gemerkt, aber wenn wir gerade bei diesem konkreten Beispiel sind:
take von Stream nimmt die genannten 1 Mio. Autos raus, im Moment anscheinend eine normale Liste (geraten: strikt),
wenn ich richtig interpretiere evtl. geplant Wechsel auf eine andere Art Liste, lazy,

was wäre der Plan, es dürfte ja wohl unmöglich sein dass A) nicht sofort millionenfach aus Stream s gelesen wird
und gleichzeitig B) der nächste normale Aufruf auf s das 1 Mio.+1ste Folge-Element liefert,
was sollte passieren?

in meinen Augen wäre bei einem Stream eher sinnvoll, s selber auf noch folgende 1 Mio. + Selbstzerstörung zu begrenzen
-> Streams endlich machen ist ok, sonst sowieso keine Änderungen, keine Probleme,

oder noch halbwegs akzeptabel könnte die take()-Methode ein neues Stream-Objekt s2 liefern, welches auf 1 Mio. begrenzt ist
-> s2 ist endlich, immer noch ein endlicher Stream voll ok,
s selber bliebe offen, nach 1 Mio. weiter nutzbar, sollte aber besser nicht genutzt werden bis s2 fertig…, irgendein Lock + ConcurrentModificationException vielleicht…,
unschöne Sache, aber ist ja auch unschöne Ausgangssituation, falls take() nicht kopieren soll

15

[QUOTE=SlaterB]habe ich ja auch schon selber gemerkt, aber wenn wir gerade bei diesem konkreten Beispiel sind:
take von Stream nimmt die genannten 1 Mio. Autos raus, im Moment anscheinend eine normale Liste (geraten: strikt),
wenn ich richtig interpretiere evtl. geplant Wechsel auf eine andere Art Liste, lazy,[/quote]

Ja, wobei ich die lazy-Liste so implementieren würde, dass sie nach einmaliger Auswertung faktisch strikt ist (also memoisieren).

was wäre der Plan, es dürfte ja wohl unmöglich sein dass A) nicht sofort millionenfach aus Stream s gelesen wird
und gleichzeitig B) der nächste normale Aufruf auf s das 1 Mio.+1ste Folge-Element liefert,
was sollte passieren?

Keine Frage, wenn du an das millionste Element von s willst, musst du die davor wenigstens „überlesen“ (dazu musst du aber nicht die Werte berechnet, auch der „head“ in dieser Implementierung kann lazy sein).

in meinen Augen wäre bei einem Stream eher sinnvoll, s selber auf noch folgende 1 Mio. + Selbstzerstörung zu begrenzen
→ Streams endlich machen ist ok, sonst sowieso keine Änderungen, keine Probleme,
oder noch halbwegs akzeptabel könnte die take()-Methode ein neues Stream-Objekt s2 liefern, welches auf 1 Mio. begrenzt ist
→ s2 ist endlich, immer noch ein endlicher Stream voll ok,

„Endliche Streams“ sind lazy Listen.

s selber bliebe offen, nach 1 Mio. weiter nutzbar, sollte aber besser nicht genutzt werden bis s2 fertig…, irgendein Lock + ConcurrentModificationException vielleicht…,
unschöne Sache, aber ist ja auch unschöne Ausgangssituation, falls take() nicht kopieren soll

Nein, alles ist immutable, wir brauchen keine Form von Synchronisierung. take muss kopieren, kann das aber auch lazy tun. Wenn man es richtig macht, wird auch hier jeder Supplier nur (höchstens) einmal ausgelesen, egal ob der originale Stream oder die davon erstellte Liste das Element als erster liest.

Natürlich kann man auch mutable Objekte wie Date in immutable Collections stecken, modifizieren und dann überrascht gucken, aber dafür sind immutable Collections nicht gedacht. Wenn sich das in Java irgendwie kontrollieren ließe (und das geht nicht mal in Scala), würde ich es liebend gerne tun, aber so muss man halt „aufpassen“.

Nochmal ganz grob, um was es mir eigentlich geht:

Ich weiß nicht, warum ich mich gerade bei diesem Thema so schwer begreiflich machen kann, eigentlich ist das Grundkonzept recht einfach. Eine NecoList ist unveränderlich, durch nichts und niemanden kann ihr Inhalt verändert werden - egal ob strict oder lazy implementiert. Bei einer „Veränderung“ wird eine neue Kopie herausgegeben, die aber soviel wie möglich mit dem „Original“ teilt (was kein Problem ist, weil… unveränderlich). Nun ist im Kontext immutabler Datenstrukturen (besonders bei unendlich großen) die Unveränderlichkeit auch ein gewisses Problem, denn wenn etwas erst einmal da ist, ist es da, und kann nicht mehr verändert werden (D’oh!). Das führt natürlich dazu, dass Laziness hier größere Vorteile bringt als bei veränderlichen Datenstrukturen. Solange man Seiteneffekte und veränderliche Objekte (bzw. deren tatsächliche Veränderung) meidet, hat Laziness kaum Nachteile gegenüber Strictness (mir fällt nur etwas erhöhter Speicherbedarf ein), kann aber deutliche Vorteile haben, wie meine obigen Beispiel zeigen sollten.

Die Stream-Klasse sollte vor allem ein praktisches Beispiel sein, wie eine (notwendigerweise) lazy Datenstruktur aussieht, und als Diskussionsgrundlage dienen, was man in ein gemeinsames „listenartiges“ Interface packen sollte und was nicht. Eine vollständig strikte unveränderliche Liste ist - nicht nur im Zusammenhang mit Streams - nicht besonders flexibel. Eine lazy Liste mit Memoisierung (die also nach dem Durchgehen „strikt“ ist, und z.B. keine Werte doppelt berechnet), also das endliche Gegenstück zu Stream, halte ich für deutlich nützlicher. Daneben kann eine strikte Liste (mit entsprechend weniger Speicherverbrauch, oder auch mit besserer Zugriffszeit wie die von Okasaki) durchaus sinnvoll sein, sollte aber aus den genannten Gründen nicht der „Default“ sein.

16

in dem Fall ist es nicht möglich, Elemente neu zu generieren oder zu filtern, die Anzahl der Elemente zu variieren, oder?
na, ist wohl im Modell nicht vorgesehen, ist ja auch kein Java-Stream

du vergisst sicherlich, obwohl schon offensichtlich geworden, auch von dir genannt, dass ich gar nichts von dem Projekt kenne,
dass ich z.B. das immutable nun wiederum gar nicht auf dem Plan hatte,

ich sehe nun etwas mehr durch, etwa dass durch s.take(1 mio) s nicht verändert wird,
genauso noch vom ersten weiteren Element an weiter durchlaufen werden könnte, interessant

aber bei der gewissen Hauptfrage Streams mit Ende könnte ich noch beim Ball bleiben (wenn es dir leid ist, auch ok, oder kurze Antworten :wink: ) :
warum nicht Stream endlich machen können? mit neuen Objekt = der vorherige Stream + Info dass (mitzählend) bald Ende, wäre Immutable eingehalten

die Code-Variante in Posting #8 Auto-Schleife mit Index der nebenher bis 1 Mio. zählt ist allgemein sicher untauglich,
wenn man den Stream in wer weiß wie komplizierte andere Methoden steckt, Schleife erst 3 Ebenen woanders von der Entscheidung auf Begrenzung,
zudem sieht der mitzählende index nicht besonders funktionial aus :wink:

die take-Variante mit Liste, mit 1 Mio.-Speicheranforderung ist extrem unschön,
ein für die Verwendung unsichtbarer und unnötiger dramatischer Wechsel von eleganten Stream auf dicke Liste, warum?
Lazy Listen habe ich wahrscheinlich immer noch nicht ganz begriffen, aber sieht so aus als würde nur je Objekt auf Rechnen verzichtet werden, 1 Mio. Platzhalter/ Rohdaten müssten immer noch abgelegt werden?

warum nicht einfach s = s.limit(1000000);, den Stream zu einem Stream machen der irgendwann aufhört, und restliche Verarbeitung gleich weiter,
stehen Prinzipien über der Programmierhandlichkeit, ein speicherloses Objekt mit Ende zu haben?

17

[QUOTE=SlaterB]in dem Fall ist es nicht möglich, Elemente neu zu generieren oder zu filtern, die Anzahl der Elemente zu variieren, oder?
na, ist wohl im Modell nicht vorgesehen, ist ja auch kein Java-Stream[/quote]

filter ist schon implementiert, ein Element zu „ändern“ (also eine Methode zu schreiben, die einen Stream zurückzuliefert, der an der genannten Stelle ein anderes Element enthält) ist auch nicht schwer. Ist halt immer ein neuer Stream (auch wenn möglichst viel vom alten recycelt wird).

du vergisst sicherlich, obwohl schon offensichtlich geworden, auch von dir genannt, dass ich gar nichts von dem Projekt kenne,
dass ich z.B. das immutable nun wiederum gar nicht auf dem Plan hatte,

ich sehe nun etwas mehr durch, etwa dass durch s.take(1 mio) s nicht verändert wird,
genauso noch vom ersten weiteren Element an weiter durchlaufen werden könnte, interessant

Gut, der Stream muss bis dahin durchlaufen werden, was genaugenommen seinen Status **intern **verändert, was man aber von außen nicht beobachten kann, also ein Implementationsdetail bleibt.

aber bei der gewissen Hauptfrage Streams mit Ende könnte ich noch beim Ball bleiben (wenn es dir leid ist, auch ok, oder kurze Antworten :wink: ) :
warum nicht Stream endlich machen können? mit neuen Objekt = der vorherige Stream + Info dass (mitzählend) bald Ende, wäre Immutable eingehalten

Kann man doch auch, nur ist das dann eben eine lazy Liste. Ich glaube fast, dass das wirklich nur ein Terminologieproblem ist. Wäre es besser gewesen, das Ding einfach „InfiniteList“ zu nennen? Aber ich orientiere mich gern an funktionalen Vorbildern (hier z.B. Data.Stream)

die Code-Variante in Posting #8 Auto-Schleife mit Index der nebenher bis 1 Mio. zählt ist allgemein sicher untauglich,
wenn man den Stream in wer weiß wie komplizierte andere Methoden steckt, Schleife erst 3 Ebenen woanders von der Entscheidung auf Begrenzung,
zudem sieht der mitzählende index nicht besonders funktionial aus :wink:

So soll man es ja auch nicht schreiben, das war nur zu Demonstrationszwecken gedacht. Liste und Stream haben z.B. ein takeWhile(condition), die solange Elemente liefern, bis die Bedingung nicht erfüllt ist.

die take-Variante mit Liste, mit 1 Mio.-Speicheranforderung ist extrem unschön,
ein für die Verwendung unsichtbarer und unnötiger dramatischer Wechsel von eleganten Stream auf dicke Liste, warum?
Lazy Listen habe ich wahrscheinlich immer noch nicht ganz begriffen, aber sieht so aus als würde nur je Objekt auf Rechnen verzichtet werden, 1 Mio. Platzhalter/ Rohdaten müssten immer noch abgelegt werden?

warum nicht einfach s = s.limit(1000000);, den Stream zu einem Stream machen der irgendwann aufhört, und restliche Verarbeitung gleich weiter,
stehen Prinzipien über der Programmierhandlichkeit, ein speicherloses Objekt mit Ende zu haben?

Zur Zeit ist das noch strict implementiert, aber mit einer lazy Liste würde es genau so funktionieren, wie du dir das wünschst: Wenn man keine Referenz auf den Original-Listenkopf hat, holt sich der GC alle fertigen Elemente der Liste, und Laziness sorgt dafür, dass nur bis zur aktellen Stelle gelesen wird. Das neue Stream.take könnte so aussehen:

class Stream<A> ...

   public NecoList<A> take(int n) {
        return (n <= 0) 
           ? NecoList.empty();
           : NecoList.cons(head(), () -> this.tail().take(n-1);
    }
}

Wenn du jetzt for(Auto a : stream.take(1000000)) schreibst, verbraucht die erzeugte Liste so gut wie keinen zusätzlichen Speicher. Wenn auch die Stream-Variable nirgendwo sonst referenziert wird, ist idealerweise immer nur ein Auto im Speicher.

Man kann natürlich auch den Listenkopf „festhalten“, dann hat man die ganze Liste mit entsprechendem Speicherbedarf:

NecoList<Auto> list = stream.take(1000000);
for(Auto a : list) { 
   System.out.println(a);
}
Auto first = list.get(0); //alles noch da, Speicher voll...
18

klingt funktionierend

19

Ich habe mal angefangen, die hier öfters erwähnte LazyList zu implementieren, wobei der Funktionsumfang noch bescheiden ist, und sicher nicht alles funktioniert. Sie ist im Prinzip ein Stream mit “Ende”, und unterschiedet sich damit etwas von den Lazy-Versuchen mit NecoList (u.a. weil dort LazyConst im Head strict ist).