13_theorie.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "ea2b397e",
   "metadata": {},
   "source": [
    "# Funktionsobjekte und Lambda-Ausdrücke\n",
    "\n",
    "#### Patrick Schnider, Marcel Lüthi</br>Departement Mathematik und Informatik, Universität Basel"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45cb39b4",
   "metadata": {},
   "source": [
    "In diesem Notebook werden wir das Konzept der funktionalen Programmierung streifen. Dabei werden wir zwei neue, nützliche Methoden für unsere Listenklasse einführen.\n",
    "\n",
    "Die erste ist die Methode `map`.\n",
    "Diese wendet auf jedem Element der Liste eine Operation an.\n",
    "Zurückgegeben wird eine neue Liste, gefüllt mit den jeweiligen Resultaten.\n",
    "\n",
    "Die zweite Methode heisst `filter`.\n",
    "Filter wird genutzt um Elemente aus einer Liste auszusortieren.\n",
    "Dabei wird eine neue, kleinere Liste erzeugt.\n",
    "Diese enthält nur Elemente welche ein bestimmtes Prädikat erfüllen.\n",
    "Anders gesagt, die verbleibenden Elemente erfüllen alle eine bestimmte Bedingung.\n",
    "\n",
    "Welche Operation `map` auf jedem Element ausführt und welche Bedingung bei `filter` geprüft wird ist nicht in deren Implementation vorgegeben.\n",
    "Dies kann durch den Benutzer der Methoden bestimmt werden.\n",
    "Wir müssen also die Bedingung, respektive die Operation an die Methoden übergeben können."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9485c18",
   "metadata": {},
   "source": [
    "#### Übung: \n",
    "\n",
    "* Diskutieren Sie, welches Sprachkonstrukt Sie dafür einsetzen könnten."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7af3c65f",
   "metadata": {},
   "source": [
    "### Funktionen "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e4906d0",
   "metadata": {},
   "source": [
    "Um allgemeine Funktionen der Form\n",
    "$$f: T \\rightarrow R$$\n",
    "zu implementieren können wir ein Interface `Function` schreiben.\n",
    "Eine Funktion hat nur eine Methode, nämlich die Anwendung der Funktion auf einen Wert.\n",
    "Wir nennen diese `apply`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6796fc42",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "interface Function<T, R> {\n",
    "    R apply(T t);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "33781f33",
   "metadata": {},
   "source": [
    "#### Übung: \n",
    "\n",
    "* Schreiben Sie eine Funktion `Square` als Implementation des Interfaces `Function`, welche die Funktion $f(x)=x^2$ implementiert. Nehmen Sie für beide Typparameter `Integer`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b38db81b",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "// Implementation missing"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e571ede6",
   "metadata": {},
   "source": [
    "Wir können unsere Funktion nun verwenden."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e05e9a47",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "class SquareTest {\n",
    "    public static void main(String[] args) {\n",
    "        Square fun = new Square();\n",
    "        int value = 2;\n",
    "        System.out.println(\n",
    "                value + \" squared is \" +\n",
    "                fun.apply(value)\n",
    "        );\n",
    "    }\n",
    "}\n",
    "\n",
    "SquareTest.main(new String[0]);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ad546c3",
   "metadata": {},
   "source": [
    "### Implementation der `map` und `filter` Operation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac638008",
   "metadata": {},
   "source": [
    "Mit Hilfe dieser Abstraktion für Funktionen können wir nun die Methoden `map` und `filter` für unsere LinkedList-Implementation schreiben. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8de0c88",
   "metadata": {},
   "source": [
    "#### Übung\n",
    "\n",
    "* Ergänzen Sie das Interface um die Methoden `map` und `filter`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2b217821",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "interface List<E> {\n",
    "    void add(E element);\n",
    "    \n",
    "    int size();\n",
    "    \n",
    "    E get(int index);\n",
    "    \n",
    "    // Hier folgen weitere Methoden\n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88e3bf66",
   "metadata": {},
   "source": [
    "Nachfolgend implementieren wir die beiden Methoden."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "73f6fd47",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "class Node<E> {\n",
    "    E value;\n",
    "    Node<E> next;\n",
    "    \n",
    "    Node(E value) {\n",
    "        this.value = value;\n",
    "        this.next = null;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "66cddaf7",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "class LinkedList<E> implements List<E> {\n",
    "    \n",
    "    Node<E> first;\n",
    "    Node<E> last;\n",
    "    \n",
    "    int size;\n",
    "    \n",
    "    public LinkedList() {\n",
    "        this.first = null;\n",
    "        this.last = null;\n",
    "        this.size = 0;\n",
    "    }\n",
    "    \n",
    "    \n",
    "    public void add(E element) {\n",
    "        Node<E> newNode = new Node<E>(element);\n",
    "        if (first == null) {\n",
    "            first = newNode;\n",
    "            last = newNode;\n",
    "        } else {\n",
    "            last.next = newNode;\n",
    "            last = newNode;\n",
    "        }        \n",
    "        size = size + 1;\n",
    "    }\n",
    "    \n",
    "    public int size() { \n",
    "        return size;\n",
    "    }\n",
    "    \n",
    "    public E get(int index) {\n",
    "        Node<E> curr = first;\n",
    "        for (int i = 0; i < index; i = i + 1) {\n",
    "            curr = curr.next;\n",
    "        }\n",
    "        return curr.value;\n",
    "        \n",
    "    }\n",
    "    \n",
    "    //Implementation missing\n",
    "    \n",
    "    \n",
    "   \n",
    "     // Gibt die Liste aus\n",
    "    @Override\n",
    "    public String toString() { \n",
    "        if (first == null) {\n",
    "            return \"[]\";\n",
    "        } else {\n",
    "            StringBuffer sb = new StringBuffer();\n",
    "            sb.append(\"[\");\n",
    "            for (Node current = first; current != last; current = current.next) {\n",
    "                sb.append(current.value);\n",
    "                sb.append(\",\");\n",
    "            }\n",
    "            sb.append(last.value);\n",
    "            sb.append(\"]\");\n",
    "            return sb.toString();\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76e3310a",
   "metadata": {},
   "source": [
    "### Anwendung"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f731e051",
   "metadata": {},
   "source": [
    "Nun werden wir die beiden Methoden `map` und `filter` anwenden.\n",
    "Dafür benötigen wir aber noch eine Funktion, welche wir als Prädikat für Filter verwenden können."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e79d576",
   "metadata": {},
   "source": [
    "Wir verwenden die Funktion `EvenNumberPred`, welche ein Zahl `n` als Eingabe nimmt und `True` zurückgibt falls `n` gerade ist und sonst `False`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0395b84a",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "class EvenNumberPred implements Function<Integer, Boolean> {\n",
    "    public Boolean apply(Integer e) {\n",
    "        return e % 2 == 0;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "450a0a33",
   "metadata": {},
   "source": [
    "#### Übung\n",
    "- Wenden Sie beide Methoden ```Square``` und ```EvenNumberPred``` einmal auf die Liste an."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "623b37db",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "class MapFilterTest {\n",
    "    public static void main(String[] args) {\n",
    "        LinkedList<Integer> l = new LinkedList<Integer>();\n",
    "        for (int i = 0; i < 10; i = i + 1) {\n",
    "            l.add(i);\n",
    "        }\n",
    "        \n",
    "        // Implementation missing\n",
    "    }\n",
    "}\n",
    "\n",
    "MapFilterTest.main(new String[0]);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02e5b365",
   "metadata": {},
   "source": [
    "### Kurzschreibweise mit Lambdas \n",
    "Die Methoden `map` und `filter` sind sehr elegant.\n",
    "Das Schreiben der Funktionen selbst, jeweils als Klasse, ist aber mühsam.\n",
    "Java stellt mit Lambda-Funktionen hier eine kurze Schreibweise zur Verfügung. Für unsere Funktionen können wir eine sehr kompakte Schreibweise nutzen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "63477cbc",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "import java.util.function.BiFunction;\n",
    "class LambdaTest {\n",
    "    public static void main(String[] args) {\n",
    "    \n",
    "        Function<Integer, Integer> fun = x -> x + 1;\n",
    "        System.out.println(fun.apply(0));\n",
    "    \n",
    "        BiFunction<Integer, Integer, Integer> fun2 = (x, y) -> x + y;\n",
    "        System.out.println(fun2.apply(3, 4));\n",
    "    }\n",
    "}\n",
    "\n",
    "LambdaTest.main(new String[0]);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "505e58c1",
   "metadata": {},
   "source": [
    "### Aufgaben"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea613ed5",
   "metadata": {},
   "source": [
    "- Schauen Sie sich das Paket [`java.util.function`](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/function/package-summary.html) und die darin enthaltenen Interfaces an.\n",
    "Finden Sie passende Interfaces zu unseren beiden Funktionen? Wie heissen diese?\n",
    "- Übergeben Sie den Methoden `map` und `filter`, statt der erstellten Objekte, jeweils equivalente Lambda-Ausdrücke."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1c445767",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "class MapFilterTest {\n",
    "    public static void main(String[] args) {\n",
    "        LinkedList<Integer> l = new LinkedList<Integer>();\n",
    "        for (int i = 0; i < 10; i = i + 1) {\n",
    "            l.add(i);\n",
    "        }\n",
    "        \n",
    "        // Implementation missing\n",
    "\n",
    "    }\n",
    "}\n",
    "\n",
    "MapFilterTest.main(new String[0]);"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java [conda env:ijava]",
   "language": "java",
   "name": "conda-env-ijava-java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".jshell",
   "mimetype": "text/x-java-source",
   "name": "Java",
   "pygments_lexer": "java",
   "version": "17.0.3-internal+0-adhoc..src"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}