streams-complete.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "024ec1d5",
   "metadata": {},
   "source": [
    "# Streams \n",
    "\n",
    "\n",
    "#### Andreas Morel-Forster, Marcel Lüthi</br>Departement Mathematik und Informatik, Universität Basel"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "18a77fe7",
   "metadata": {},
   "source": [
    "Zu Beginn der Vorlesung haben wir gelernt, Werte in Variablen zu speichern. Für mehrere Werte konnten wir folgendes verwenden:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f8ee542b",
   "metadata": {},
   "outputs": [],
   "source": [
    "int i1 = 0;\n",
    "int i2 = 2;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "322b98ad",
   "metadata": {},
   "source": [
    "So konnten wir die Werte nur einzeln bearbeiten. Danach haben wir Arrays kennengelernt um eine Reihe von Elementen vom selben Typ zu speichern. Mit Schleifen war es möglich die Elemente effizient zu bearbeiten:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eacb4d34",
   "metadata": {},
   "outputs": [],
   "source": [
    "int[] arr = new int[4];\n",
    "for(int i = 0; i < 4; i = i + 1) {\n",
    "    arr[i] = i;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "767aa55a",
   "metadata": {},
   "source": [
    "Wir haben jedoch auch die Limitierungen kennegelernt und gesehen, dass Arrays nicht sehr komfortabel zu benutzen sind. Deshalb haben wir dann unsere eigene `LinkedList` Klasse entwickelt. So haben wir eine erste Abstraktion kennengelernt, das Interface `List`, was das Arbeiten mit einer Reihe von Elementen noch einfacher macht. Java bietet aber noch weitere Abstraktionen. `Collection` ist ein Interface, welches alle möglichen Arten von *Sammlungen* von Elementen repräsentiert (siehe [API-Doc](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Collection.html)). Dazu gehört nicht nur `List` sondern auch Datenstrukturen wie `Set`, `Queue` oder `Map` (siehe [Übersicht der Collection Klassen](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/doc-files/coll-overview.html)). \n",
    "\n",
    "Ein weitere Abstraktion ist `Iterable`. `Iterable` ist ein Interface, welches von einer Klasse implementiert werden muss, damit wir über die Elemente mit der erweiterten `for`-Schleife iterieren können. Das bearbeiten von einer Serie von Elementen wurde so noch komfortabler:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6e68aec9",
   "metadata": {},
   "outputs": [],
   "source": [
    "int[] arr = new int[4];\n",
    "for(int e : arr) {\n",
    "    e = 1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2533d2af",
   "metadata": {},
   "source": [
    "Auf einer noch höheren Abstraktionsebene befindet sich die Klasse `Stream` ([API-Doc](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/stream/Stream.html)).\n",
    "Streams repräsentiert Folgen von Elementen.\n",
    "Im Prinzip können diese Folgen sogar unendlich lange sein.\n",
    "Die Folgen werden nur als ganzes bearbeitet.\n",
    "Die jeweiligen Operationen werden jedoch elementweise auf der ganzen Folge angewendet.\n",
    "Wir haben bereits `map` und `filter` kennen gelernt.\n",
    "Streams erlauben keinen Zugriff auf die einzelnen Elemente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "df97ca3b",
   "metadata": {},
   "outputs": [],
   "source": [
    "// ... (Zelle kann nicht ausgeführt werden, und ist nur zur Demonstration)\n",
    "list.map(x -> x + 2);\n",
    "list.filter(x -> x % 2 == 0);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f720f20e",
   "metadata": {},
   "source": [
    "> Hinweis: In diesem Notebook beschränken wir uns auf den wesentlichen Java-Code und lassen umgebende Klassen oder Methoden meist weg. Dies ist so nur in Jupyter-Notebooks (und JShell) und nicht in regulärem Java-Code möglich."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9390e3d",
   "metadata": {},
   "source": [
    "### Streams erzeugen\n",
    "\n",
    "Es gibt unterschiedliche Wege einen Stream zu erzeugen.\n",
    "Naheliegend zum Thema LinkedList, schauen wir uns zuerst an, wie man einen Stream ausgehend von einer vorhanden Collection erzeugen kann.\n",
    "Wir verwenden die `LinkedList` von Java und füllen diese mit den Zahlen 0 bis und mit 9.\n",
    "Dafür verwenden wir einen uns schon lange bekannten `for`-Loop.\n",
    "Davon erzeugen wir unseren ersten Stream."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "acd32bd6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "java.util.stream.ReferencePipeline$Head@7288a5c1\n"
     ]
    }
   ],
   "source": [
    "import java.util.List;\n",
    "import java.util.LinkedList;\n",
    "import java.util.stream.Stream;\n",
    "\n",
    "LinkedList<Integer> l = new LinkedList<Integer>();\n",
    "for (int i = 0; i < 10; i = i + 1) {\n",
    "    l.add(i);\n",
    "}\n",
    "\n",
    "Stream<Integer> intStream =  l.stream();\n",
    "\n",
    "System.out.println(intStream);\n",
    "// Die Ausgabe gibt den Typ und eine Speicheradresse aus, nicht die Elemente.\n",
    "// Die Methode toString ist nicht überladen und es wird sehr wahrscheinlich diejenige von Object benutzt."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b998a0bb",
   "metadata": {},
   "source": [
    "#### Miniübung\n",
    "\n",
    "* Geben Sie die Variable `intStream` mit `System.out.println` aus. Was beoabachten Sie? Warum ist das so?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1bc0004a",
   "metadata": {},
   "source": [
    "Es gibt auch Streams welche für konkrete, primitive Datentypen ausgelegt sind. Der wichtigste ist vielleicht `IntStream`. Auf diesem ist auch eine Methode definiert, die uns erlaubt Zahlen in einem gewissen Bereich einfach zu generieren.\n",
    "\n",
    "Wir erzeugen erneut einen Stream mit den Zahlen von 0 bis und mit 9."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "e4266be5",
   "metadata": {},
   "outputs": [],
   "source": [
    "import java.util.stream.IntStream;\n",
    "\n",
    "IntStream intStream = IntStream.range(0, 10);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8da3c78f",
   "metadata": {},
   "source": [
    "Wir können einen `IntStream` in den entsprechenden Stream des zugehörigen nicht-primitiven Datentyps konvertieren.\n",
    "Dazu steht die Methode `boxed` zur Verfügung.\n",
    "\n",
    "#### Miniübung\n",
    "\n",
    "* Was passiert, wenn Sie die folgende Zelle 2 mal ausführen? Verstehen Sie die Fehlermeldung?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "1139664b",
   "metadata": {},
   "outputs": [],
   "source": [
    "Stream<Integer> integerStream = intStream.boxed();\n",
    "// Diese Zelle ergibt beim zweiten Mal ausführen einen Fehler.\n",
    "// Ein Stream kann nur einmal verwendet werden. Danach ist er verbraucht oder gar geschlossen."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "044f2859",
   "metadata": {},
   "source": [
    "### Zurück zur Collection"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b92675e8",
   "metadata": {},
   "source": [
    "Die Elemente von einem Stream können wir mit Hilfe eines `Collectors` in eine Collection einfügen. Wir wandeln also den `Stream` um in eine `Collection`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "5545ee4b",
   "metadata": {},
   "outputs": [],
   "source": [
    "import java.util.stream.Collectors;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ece5ff50",
   "metadata": {},
   "source": [
    "Für die Umwandlung können wir die Methode wählen, hier `toList`. Die Wahl bestimmt was für eine Collection zurück gegeben wird. Nachfolgend sehen wir einen weiteren Weg wie wir eine Liste mit den Zahlen von 0 bis und mit 9 füllen können. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "872a91a3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "import java.util.List;\n",
    "\n",
    "Stream<Integer> stream = IntStream.range(0, 10).boxed(); \n",
    "\n",
    "List<Integer> ll = stream.collect(Collectors.toList());\n",
    "\n",
    "System.out.println(ll);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "89093fba",
   "metadata": {},
   "source": [
    "### Arbeiten mit Streams"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd0f326d",
   "metadata": {},
   "source": [
    "Wir verändern die Elemente in eine Stream, indem wir Funktionen jeweils auf dem ganzen Stream ausführen.\n",
    "Die wichtigsten Methoden in diesem Zusammenhang sind `map` und `filter`, welche wir ja schon kennen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "74a53834",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]\n"
     ]
    }
   ],
   "source": [
    "Stream<Integer> stream = IntStream.range(0, 10).boxed();\n",
    "\n",
    "List<Integer> list = stream\n",
    "    .map(x -> x * x)\n",
    "    .collect(Collectors.toList());\n",
    "\n",
    "System.out.println(list);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "e2ca40e6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 2, 4, 6, 8]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Stream<Integer> stream = IntStream.range(0, 10).boxed();\n",
    "\n",
    "List<Integer> list = stream\n",
    "    .filter(x -> x % 2 == 0)\n",
    "    .collect(Collectors.toList());\n",
    "\n",
    "list"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c90a1746",
   "metadata": {},
   "source": [
    "Es gibt aber eine vielzahl weiterer Methoden die auf Streams definiert sind und deren Verhalten durch einen, der Methode übergebenen, Lambda-Ausdruck bestimmt werden kann. Hier ein paar Beispiele:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "2c56f06b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Stream<Integer> stream = IntStream.range(0, 10).boxed();\n",
    "\n",
    "// nimm solange eine Bedingung erfüllt ist\n",
    "stream\n",
    "    .takeWhile(i -> Math.sqrt(i) < 2)\n",
    "    .collect(Collectors.toList())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "4e097174",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Stream<Integer> stream = IntStream.range(0, 10).boxed(); \n",
    "\n",
    "// teste ob für alle Elemente ein Prädikat true ergibt\n",
    "stream\n",
    "    .allMatch(i -> i * i > 50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "411348a6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Stream<Integer> stream = IntStream.range(0, 10).boxed(); \n",
    "\n",
    "// teste ob mindestens für ein Element ein Prädikat zutrifft\n",
    "stream\n",
    "    .anyMatch(i -> i * i > 50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "d6fc5264",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "Stream<Integer> stream = IntStream.range(0, 10).boxed(); // boxed um in in Integer umzuwandeln\n",
    "\n",
    "// wendet eine Funktion auf jedes Element an\n",
    "stream\n",
    "    .forEach(s -> System.out.println(s));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "912910c3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "Stream<Integer> stream = IntStream.range(0, 10).boxed(); // boxed um in in Integer umzuwandeln\n",
    "\n",
    "// verwenden einer Methoden-Referenz\n",
    "stream\n",
    "    .forEach(System.out::println)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "399be051",
   "metadata": {},
   "source": [
    "### Miniübung\n",
    "\n",
    "* Was macht `anyMatch`? Was macht `allMatch`? Experimentieren Sie. \n",
    "* können Sie statt dem Lambda-Ausdruck in der Methode `forEach` eine Methodenreferenz nutzen um die Elemente auszugeben?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3fba638",
   "metadata": {},
   "source": [
    "### Streams unendlicher Länge"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f2c6d51c",
   "metadata": {},
   "source": [
    "*Hinweis:*  Die Nachfolgend eingeführten Beispiele sind sehr fortgeschritten und als Ausblick zu verstehen. Sie müssen diese nicht im Detail verstehen oder selbst umsetzen können. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf87cffe",
   "metadata": {},
   "source": [
    "Wir können auch unendliche lange Sequenzen erzeugen.\n",
    "Dazu verwenden wir die Klassen-Methode `iterate` von `Stream`.\n",
    "Dieser Methode übergeben wir den Wert des ersten Elements sowie eine Funktion, welche basierend auf einem Element, das nächste berechnet.\n",
    "Als Beispiel wird hier ein Stream aus fortlaufenden Zahlen erzeugt, beginnend mit der 1. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "ebf493c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "Stream<Integer> infinitelyLongStream = Stream.iterate(1, (Integer i) -> i + 1);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "74384e9f",
   "metadata": {},
   "source": [
    "Wir können wie bei endlichen Streams die Methoden `map`, oder `filter` verwenden um die Elemente zu transformieren. \n",
    "Das folgende Beispiel füllt eine Liste mit alle Quadratzahlen bis 1000, die durch 8 Teilbar sind.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "212f7a19",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[16, 64, 144, 256, 400, 576, 784]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Stream<Integer> infinitelyLongStream = Stream.iterate(1, (Integer i) -> i + 1);\n",
    "\n",
    "infinitelyLongStream\n",
    "    .map(i -> (i * i))\n",
    "    .filter(i -> i % 8 == 0)\n",
    "    .takeWhile(i -> i < 1000)\n",
    "    .collect(Collectors.toList())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92bd502d",
   "metadata": {},
   "source": [
    "Wir können auch einen unendlich lange Folge von Zufallszahlen erzeugen. Im Unterschied zur Methode `iterate` nimmt die Methode `generate` eine Methode ohne Parameter entgegen. Im Folgenden erzeugen wir mit Hilfe der Methodenreferenz `rng::nextInt` so lange Zufallszahlen, bis eine der Zahlen im Interval $[-10000, 10000]$ liegt. Dann zählen wir, wieviele Zahlen wir erzeugt haben, bis dies der Fall war. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "9c85c563",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "452290"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import java.util.Random;\n",
    "\n",
    "Random rng = new Random();\n",
    "\n",
    "Stream<Integer> randomStream = Stream.generate(rng::nextInt);\n",
    "\n",
    "randomStream\n",
    "    .takeWhile(i -> (i < -10000) || (i > 10000))\n",
    "    .count()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "583e7c2e",
   "metadata": {},
   "source": [
    "### Streams debuggen\n",
    "\n",
    "Ein Problem bei Streams ist, dass diese nur jeweils einmal verwendet werden können. So können wir nach einem Aufruf der Methode `foreach` den Stream nicht noch für eine andere Operation wie zum Beispiel ein `map` verwenden.\n",
    "\n",
    "Gerade beim Debuggen ist dies nicht sehr handlich.\n",
    "Doch Java Streams bieten dafür die Methode `Stream<E> peek(Consumer c)` an.\n",
    "Als Argument können wir einen *Consumer* angeben (siehe Übersicht [Functional Interfaces](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/function/package-summary.html)).\n",
    "Beim Debuggen können wir so zum Beispiel die Methodenreferenz `System.out::println` übergeben."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "8fb10e1e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "16\n",
      "64\n",
      "144\n",
      "256\n",
      "400\n",
      "576\n",
      "784\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[16, 64, 144, 256, 400, 576, 784]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Stream<Integer> infinitelyLongStream = Stream.iterate(1, (Integer i) -> i + 1);\n",
    "\n",
    "infinitelyLongStream\n",
    "    .map(i -> (i * i))\n",
    "    .filter(i -> i % 8 == 0)\n",
    "    .takeWhile(i -> i < 1000)\n",
    "    .peek(System.out::println)\n",
    "    .collect(Collectors.toList())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c3131f4",
   "metadata": {},
   "source": [
    "#### Miniübung\n",
    "\n",
    "* Verschieben Sie den Aufruf der Methode `peek` jeweils um eine Zeile *nach oben* und führen Sie den Code aus. Was beobachten Sie?\n",
    "* Überlegen Sie sich folgendes: Wie ist es möglich, dass wir mit einer unendlich langen Sequenz arbeiten können? Sollte das nicht unendlich lange dauern und unendlich viel Speicher benötigen?\n",
    "* Können Sie die nachfolgende `for`-Schleife umschreiben in funktionales Java?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "fed8957e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5494\n",
      "2747\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "long cnt = 0;\n",
    "for(int i = 7000; i > 1234; i = i - 1) {\n",
    "    if (i % 41 == 0 && i % 67 == 0) {\n",
    "        System.out.println(i); // debug output\n",
    "        cnt = cnt + 1;\n",
    "    }\n",
    "}\n",
    "System.out.println(cnt);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "6f599927",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5494\n",
      "2747\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "long cnt = Stream.iterate(7000, i -> i - 1)\n",
    "    .takeWhile(i -> i > 1234)\n",
    "    .filter(i -> i % 41 == 0 && i % 67 == 0)\n",
    "    .peek(System.out::println)\n",
    "    .count();\n",
    "    \n",
    "System.out.println(cnt);"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
    "name": "conda-env-ijava-java",
    "display_name": "Java [conda env:ijava]",
    "language": "java"
  },
  "language_info": {
    "name": "Java",
    "version": "17.0.3-internal+0-adhoc..src",
    "mimetype": "text/x-java-source",
    "file_extension": ".jshell",
    "pygments_lexer": "java",
    "codemirror_mode": "java"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}