seminar10.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Seminar Problemorientierte Programmierung\n",
    "\n",
    "## Exkurs: Was mir an Python gefällt\n",
    "\n",
    "In dieser Rubrik, die immer am Anfang eines Kapitels steht, möchte ich Ihnen zeigen, wofür ich Python nutze und warum ich es mag. Sie werden vielleicht noch nicht verstehen, was ich genau mache, aber Sie sehen damit schon einmal die Möglichkeiten von Python und können später darauf zurückgreifen. Da dies auch ein Exkurs ist, können Sie diese Rubrik gerne auch erst einmal überspringen.\n",
    "\n",
    "Mit Hilfe von pydotplus ist es möglich, Graphen zu visualisieren, die auch direkt im Jupyter Notebook angezeigt werden können. Als Beispiel wird hier ein [Trie](https://de.wikipedia.org/wiki/Trie) erzeugt, der schnellen Zugriff auf die Präfixe einer Liste von Wörtern bildet (so etwas ermöglicht z.B. eine schnelle Wortvervollständigung bei der Eingabe von Wörtern auf der Handy-Tastatur ([siehe](https://towardsdatascience.com/implementing-a-trie-data-structure-in-python-in-less-than-100-lines-of-code-a877ea23c1a1))."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.display import Image  \n",
    "import pydotplus\n",
    "\n",
    "# Der Quellcode für die Klasse TrieNode und die Funktion add stammt von der Webseite\n",
    "# from https://towardsdatascience.com/implementing-a-trie-data-structure-in-python-in-less-than-100-lines-of-code-a877ea23c1a1\n",
    "class TrieNode(object):\n",
    "    def __init__(self, char: str):\n",
    "        self.char = char\n",
    "        self.children = []\n",
    "        self.word = None\n",
    "        self.counter = 1\n",
    "\n",
    "def add(root, word):\n",
    "    node = root\n",
    "    for char in word:\n",
    "        found_in_child = False\n",
    "        # Search for the character in the children of the present `node`\n",
    "        for child in node.children:\n",
    "            if child.char == char:\n",
    "                # We found it, increase the counter by 1 to keep track that another\n",
    "                # word has it as well\n",
    "                child.counter += 1\n",
    "                # And point the node to the child that contains this char\n",
    "                node = child\n",
    "                found_in_child = True\n",
    "                break\n",
    "        # We did not find it so add a new chlid\n",
    "        if not found_in_child:\n",
    "            new_node = TrieNode(char)\n",
    "            node.children.append(new_node)\n",
    "            # And then point node to the new child\n",
    "            node = new_node\n",
    "    # Everything finished. Mark it as the end of a word.\n",
    "    node.word = word\n",
    "\n",
    "# fügt eine Liste von Wörtern hinzu\n",
    "def add_words(root, words):\n",
    "    for word in words:\n",
    "        add(root, word)\n",
    "\n",
    "# wandelt den Baum in einen Graphen, also eine Menge von Knoten (vertices) und Kanten (edges) um\n",
    "# Eingaben:\n",
    "# - root: Wurzelknoten des Baums\n",
    "# - vertices: (leere) Liste mit Knoten (jeder Knoten ist vom Typ TrieNode)\n",
    "# - edges: (leere) Liste mit Kanten (jede Kante ist ein Tupel von ganzen Zahlen, die die Knoten-IDs repräsentieren)\n",
    "def tree_to_graph(root, vertices, edges):\n",
    "    # Hinzufügen des Wurzelknotens\n",
    "    if len(vertices) == 0:\n",
    "        vertices.append(root)\n",
    "    # wir nummerieren die Knoten durch:\n",
    "    # jeder Knoten erhält als ID seine Position in der Liste (ab 1 zählend)\n",
    "    rootid = len(vertices)\n",
    "    # Hinzufügen der Kindknoten\n",
    "    for child in root.children:\n",
    "        vertices.append(child)\n",
    "        childid = len(vertices)\n",
    "        \n",
    "        # Kante zum Kindknoten hinzufügen\n",
    "        edges.append((rootid, childid))\n",
    "\n",
    "        # Rekursion, falls Kindknoten vorhanden\n",
    "        if child.children:\n",
    "            tree_to_graph(child, vertices, edges)\n",
    "\n",
    "# erzeugt eine Zeichenkette in der Syntax for GraphViz (http://graphviz.org/)\n",
    "def build_graph_string(vertices, edges):\n",
    "    # Konfiguration für Graph, Knoten und Kanten \n",
    "    s = \"\"\"\n",
    "digraph G {\n",
    "  graph [rankdir=\"LR\"];\n",
    "  node [sep=\"+0.01,+0.01\", height=\"0\", width=\"0\", shape=\"box\", margin=\"0.05, 0.05\"];\n",
    "  edge [];\n",
    "    \"\"\"\n",
    "    # Hinzufügen der Knoten\n",
    "    for i, vertice in enumerate(vertices):\n",
    "        label = vertice.char\n",
    "        # Knoten, die ein Wort repräsentieren, sollen dieses zusätzlich enthalten\n",
    "        if vertice.word:\n",
    "            label += \" (\" + vertice.word + \")\"\n",
    "        s += '  ' + str(i + 1) + ' [label=\"' + label + '\"];\\n'\n",
    "    # Hinzufügen der Kanten\n",
    "    for v1, v2 in edges:\n",
    "        s += '  ' + str(v1) + ' -> ' + str(v2) + ';\\n'\n",
    "    s += \"}\"\n",
    "    return s\n",
    "        \n",
    "\n",
    "# Beispielwörter zum Visualisieren - ergänzen Sie die Liste oder probieren Sie andere Wörter\n",
    "words = [\"Braten\", \"Brauerei\", \"Brause\", \"Brot\", \"Brett\", \n",
    "         \"Brei\", \"Brief\", \"Breite\", \"Brille\", \"Brand\", \"Bruder\", \n",
    "         \"Bruch\", \"Brust\", \"Bronze\", \"Brache\", \"Branche\", \n",
    "         \"Brandung\", \"Braten\", \"Bratsche\", \"Bremse\", \"Brenner\", \n",
    "         \"Brezel\", \"Brikett\", \"Brise\", \"Brocken\", \"Bronze\", \n",
    "         \"Brosche\", \"Brunnen\", \"Brut\"]\n",
    "# Alternative: aus einer Datei einlesen\n",
    "# words = []\n",
    "# fin = open('top10000de.txt', encoding=\"latin1\")\n",
    "# for line in fin:\n",
    "#     if line.startswith(\"Bra\"):\n",
    "#         words.append(line.strip())\n",
    "\n",
    "# Wörter zum Trie hinzufügen (in sortierter Reihenfolge, das liest sich leichter)\n",
    "root = TrieNode('*')\n",
    "add_words(root, sorted(words))\n",
    "\n",
    "# aus dem Trie einen Graph erzeugen\n",
    "vertices = []\n",
    "edges = []\n",
    "tree_to_graph(root, vertices, edges)\n",
    "\n",
    "# die Zeichenkette für GraphViz erzeugen\n",
    "graphdata = build_graph_string(vertices, edges)\n",
    "\n",
    "# den Graph zeichnen und anzeigen\n",
    "graph = pydotplus.graph_from_dot_data(graphdata)  \n",
    "Image(graph.create_png())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10 Listen\n",
    "\n",
    "In diesem Kapitel lernen wir einen der nützlichsten eingebauten Datentypen von Python kennen: Listen. Wir lernen auch mehr über Objekte und was passieren kann, wenn es mehr als einen Namen für das gleiche Objekt gibt.\n",
    "\n",
    "### 10.1 Eine Liste ist eine Folge\n",
    "\n",
    "Wie eine Zeichenkette, ist eine **Liste** eine Folge (*sequence*) von Werten. In einer Zeichenkette sind die Werte Zeichen; in einer Listen können sie von jedem Typ sein. Die Werte in einer Liste heißen **Elemente**, im Englischen manchmal auch *items*.\n",
    "\n",
    "Es gibt mehrere Möglichkeiten, eine neue Liste zu erzeugen. Die einfachste ist es, Elemente in eckigen Klammern einzuschließen (`[` und `]`):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[10, 20, 30, 40]\n",
    "l = ['crunchy frog', 'ram bladder', 'lark vomit']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das erste Beispiel ist eine Liste mit vier ganzen Zahlen. Das zweite Beispiel ist eine Liste mit drei Zeichenketten. Die Elemente einer Liste müssen nicht vom gleichen typ sein. Die folgende Liste enthält eine Zeichenkette, eine Gleitkommazhal, eine ganze Zahl und (ja!) eine andere Liste:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "['spam', 2.0, 5, [10, 20]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eine Liste innerhalb einer anderen Liste ist **verschachtelt** (*nested*).\n",
    "\n",
    "Eine Liste, die keine Elemente enthält wird **leere Liste** genannt. Wir können Sie mit Hilfe von leeren Klammern erzeugen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir Sie vielleicht schon vermutet haben, können wir Listen Variablen zuweisen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cheeses = ['Cheddar', 'Edam', 'Gouda']\n",
    "numbers = [42, 123]\n",
    "empty = []\n",
    "print(cheeses, numbers, empty)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.2 Listen sind veränderbar\n",
    "\n",
    "Die Syntax, um auf Elemente einer Liste zuzugreifen, ist die gleiche wie die zum Zugriff auf die Zeichen einer Zeichenkette: der Klammer-Operator. Der Ausdruck innerhalb der Klammern gibt den Index an. Denken Sie daran, dass die Zählung der Indizes mit 0 beginnt:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cheeses[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Anders als Zeichenketten sind Listen veränderbar. Wenn der Klammer-Operator auf der linken Seite einer Zuweisung auftaucht, identifiziert er das Element der Liste, dessen Wert geändert wird."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers = [42, 123]\n",
    "numbers[1] = 5\n",
    "numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das zweite Element von `numbers`, welches 123 war, ist jetzt 5.\n",
    "\n",
    "Die folgende Abbildung zeigt das Zustandsdiagramm für `cheeses`, `numbers` and `empty`:\n",
    "\n",
    "![Zustandsdiagramm für drei Listen](zustandsdiagramm_listen.svg)\n",
    "\n",
    "In diesen Diagrammen sind Listen als Boxen mit dem Wort \"Liste\" oberhalb und den Elementen der Liste innerhalb repräsentiert. Dabei zeigt `cheeses` auf eine Liste mit drei Elementen, die mit 0, 1 und 2 indiziert sind. `numbers` enthält zwei Elemente; das Diagramm zeigt, dass der Wert des zweiten Elements von 123 zu 5 geändert wurde. `empty` verweist auf eine Liste ohne Elemente.\n",
    "\n",
    "Listenindizes funktionieren genauso wie Indizes bei Zeichenketten:\n",
    "- Jeder Ausdruck, der eine ganze Zahl ergibt, kann als Index verwendet werden.\n",
    "- Wenn wir versuchen, ein Element zu lesen oder zu schreiben, welches nicht existiert, erhalten wir einen `IndexError`.\n",
    "- Wenn ein Index einen negativen Wert hat, zählt er rückwärts vom Ende der Liste.\n",
    "\n",
    "Der `in`-Operator funktioniert auch für Listen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cheeses = ['Cheddar', 'Edam', 'Gouda']\n",
    "'Edam' in cheeses"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'Brie' in cheeses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.3 eine Liste durchlaufen\n",
    "\n",
    "Üblicherweise durchläuft man die Elemente einer Liste mit einer `for`-Schleife. Die Syntax ist die gleiche wie für Zeichenketten:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for cheese in cheeses:\n",
    "    print(cheese)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das funktioniert gut wenn wir die Elemente einer Liste lediglich *lesen* wollen. Wenn wir die Elemente aber schreiben oder verändern wollen, benötigen wir die Indizes. Eine übliche Variante das zu tun ist, die eingebauten Funktionen `range` und `len` zu kombinieren: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(len(numbers)):\n",
    "    numbers[i] = numbers[i] * 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Diese Schleife durchläuft die Liste und aktualisiert jedes Element. Dabei gibt `len` die Anzahl der Elemente in der Liste zurück und `range` gibt eine Liste von Indizes zurück, die mit 0 bis $n-1$ numeriert sind - wobei $n$ die Länge der Liste ist. Bei jedem Schleifendurchlauf erhält `i` den Index des nächsten Elements. Die Zuweisung im Rumpf verwendet `i`, um den alten Wert des Elementes zu lesen den neuen Wert zuzuweisen. \n",
    "\n",
    "Eine `for`-Schleife über eine leere Liste durchläuft niemals den Schleifenrumpf:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for x in []:\n",
    "    print(\"This never happens.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Obwohl eine Liste eine andere Liste enthalten kann, zählt die verschachtelte Liste als ein einzelnes Element. Die Länge der folgenden Liste ist vier: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "allerhand = ['spam', 1, ['Brie', 'Roquefort', 'Pol le Veq'], [1, 2, 3]]\n",
    "len(allerhand)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.4 Listenoperatoren\n",
    "\n",
    "Der `+`-Operator verknüpft Listen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [1,2,3]\n",
    "b = [4,5,6]\n",
    "c = a + b\n",
    "c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der `*`-Operator wiederholt eine Liste so oft wie angegeben:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[0] * 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[1,2,3] * 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das erste Beispiel wiederholt `[0]` viermal. Das zweite Beispiel wiederholt die Liste `[1,2,3]` dreimal.\n",
    "\n",
    "### 10.5 Listensegmente\n",
    "\n",
    "Der Segmentoperator (*slice operator*) funktioniert auch auf Listen: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = ['a', 'b', 'c', 'd', 'e', 'f']\n",
    "t[1:3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t[:4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t[3:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wenn wir den ersten Index weglassen, dann beginnt das Segment mit dem Anfang. Wenn wir den zweiten Index weglassen, dann geht das Segment bis zum Ende. Wenn wir also beide weglassen, dann ist das Segment eine Kopie der gesamten Liste. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t[:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Da Listen veränderbar sind, ist es oft nützlich, eine Kopie der Liste zu erstellen, bevor man Operationen anwendet, die die Liste verändern.\n",
    "\n",
    "Wenn wir den Segmentoperator auf der linken Seite einer Zuweisung verwenden, können wir mehrere Listenelemente verändern: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = ['a', 'b', 'c', 'd', 'e', 'f']\n",
    "t[1:3] = ['x', 'y']\n",
    "t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.6 Listenmethoden\n",
    "\n",
    "Python stellt Methoden bereit, die auf Listen operieren. Zum Beispiel fügt `append` neue Elemente am Ende einer Liste hinzu:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = ['a', 'b', 'c']\n",
    "t.append('d')\n",
    "t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`extend` erwartet eine Liste als Argument und fügt alle Elemente der Liste am Ende hinzu:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t1 = ['a', 'b', 'c']\n",
    "t2 = ['d', 'e']\n",
    "t1.extend(t2)\n",
    "t1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In diesem Beispiel wird `t2` nicht verändert.\n",
    "\n",
    "Mit `sort` können wir die Elemente einer Liste sortieren - vom kleinsten zum größten:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = ['d', 'c', 'e', 'b', 'a']\n",
    "t.sort()\n",
    "t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die meisten Listenmethoden sind leer - sie verändern die Liste und geben `None` zurück. Wenn wir fälschlicherweise `t = t.sort()` schreiben, werden wir vom Ergebnis enttäuscht sein.\n",
    "\n",
    "### 10.7 Map, filter und reduce\n",
    "\n",
    "Um die Elemente einer Liste aufzuaddieren, können wir eine Schleife wie die folgende nutzen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def add_all(t):\n",
    "    total = 0\n",
    "    for x in t:\n",
    "        total += x\n",
    "    return total"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`total` wird mit 0 initialisiert. Bei jedem Durchlauf der Schleife enthält `x` ein Element der Liste. Der `+=`-Operator ist eine Kurzschreibweise zum Verändern einer Variable. Diese **erweiterte Zuweisung** (*augmented assignment statement*),\n",
    "\n",
    "```python\n",
    "total += x\n",
    "```\n",
    "\n",
    "ist äquivalent zu \n",
    "\n",
    "```python\n",
    "total = total + x\n",
    "```\n",
    "\n",
    "Während die Schleife läuft, akkumuliert `total` die Summe der Elemente. Eine Variable die so verwendet wird, wird manchmal **Akkumulator** genannt.\n",
    "\n",
    "Die Elemente einer Liste aufzuaddieren ist eine so übliche Operation, dass Python dafür die eingebaute Funktion `sum` bereitstellt:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = [1, 2, 3]\n",
    "sum(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eine Operation wie diese, die eine Folge von Elementen in einen einzelnen Wert kombinbiert, wird manchmal **Reducer** genannt. \n",
    "\n",
    "Manchmal wollen wir eine Liste durchlaufen während wir eine andere aufbauen. Beispielsweise erwartet die folgende Funktion eine Liste von Zeichenketten und gibt eine neue Liste zurück, die großgeschriebene Zeichenketten enthält:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def capitalize_all(t):\n",
    "    res = []\n",
    "    for s in t:\n",
    "        res.append(s.capitalize())\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`res` wird mit der leeren Liste initialisiert. Bei jedem Schleifendurchlauf fügen wir das nächste Element hinzu. Also ist `res` eine andere Art von Akkumulator.\n",
    "\n",
    "Eine Operation wie `capitalize_all` wird manchmal **Mapper** genannt, da sie eine Funktion auf alle Elemente einer Folge anwendet (*maps*). \n",
    "\n",
    "Eine andere übliche Operation ist es, einige Elemente einer Liste auszuwählen und dann eine Teilliste zurückzugeben. Beispielsweise erwartet die folgende Funktion eine Liste von Zeichenketten und gibt eine Liste zurück, die nur die Zeichenketten enthält, die nur aus Großbuchstaben bestehen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def only_upper(t):\n",
    "    res = []\n",
    "    for s in t:\n",
    "        if s.isupper():\n",
    "            res.append(s)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`isupper` ist eine Zeichenketten-Methode, die `True` zurückgibt, wenn die Zeichenkette nur aus Großbuchstaben besteht.\n",
    "\n",
    "Eine operation wie `only_upper` wird **Filter** genannt, denn sie wählt einige der Elemente aus und filtert andere heraus.\n",
    "\n",
    "Die meisten üblichen Listenoperatoren können als eine Kombination aus Mapper, Filter und Reducer ausgedrückt werden."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.8 Elemente löschen\n",
    "\n",
    "Es gibt mehrere Möglichkeiten, um Elemente aus einer Liste zu entfernen. Wenn wir den Index des Elementes kennen, dann können wir es mittels `pop` entfernen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = ['a', 'b', 'c']\n",
    "x = t.pop(1)\n",
    "t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`pop` verändert die Liste und gibt das Element zurück, welches entfernt wurde. Wenn wir keinen Index angeben, dann wird das letzte Element entfernt und zurückgegeben.\n",
    "\n",
    "Wenn wir den gelöschten Wert nicht benötigen, können wir den `del`-Operator verwenden:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = ['a', 'b', 'c']\n",
    "del t[1]\n",
    "t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wenn wir das Element kennen, welches wir entfernen wollen (aber nicht seinen Index), können wir `remove` verwenden:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = ['a', 'b', 'c']\n",
    "t.remove('b')\n",
    "t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Rückgabewert von `remove` ist `None`.\n",
    "\n",
    "Um mehr als ein Element zu löschen, können wir `del` mit einem einem Segment-Index nutzen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = ['a', 'b', 'c', 'd', 'e', 'f']\n",
    "del t[1:5]\n",
    "t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wie sonst auch, beinhalted das Segment alle Elemente bis zum zweiten Index."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.9 Listen und Zeichenketten\n",
    "\n",
    "Eine Zeichenkette ist eine Folge von Zeichen und eine Liste ist eine Folge von Werten, aber eine Liste von Zeichen ist nicht das gleiche wie eine Zeichenkette. Um eine Zeichenkette in eine Liste von Zeichen zu konvertieren, können wir die Funktion `list` verwenden:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = 'spam'\n",
    "t = list(s)\n",
    "t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Da `list` der Name einer eingebauten Funktion ist, sollten wir diesen nicht als Variablennamen verwenden. Da `l` der `1` sehr ähnlich sieht, sollten wir `l` als Name für Listen vielleicht auch verwenden. Daher verwenden wir hier `t`.\n",
    "\n",
    "Die `list`-Funktion teilt eine Zeichenkette in die individuellen Zeichen auf. Wenn wir eine Zeichenkette in die enthaltenen Wörter aufteilen wollen, können wir die `split`-Methode verwenden:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = 'pining for the fjords'\n",
    "t = s.split()\n",
    "t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ein optionales Argument, genannt **Trennzeichen** (*delimiter*) gibt an, welche Zeichen als Wortgrenzen verwendet werden sollen. Im folgenden Beispiel wird ein Bindestrich als Trennzeichen verwenden:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = 'spam-spam-spam'\n",
    "delimiter = '-'\n",
    "t = s.split(delimiter)\n",
    "t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das Gegenstück zu `split` ist `join`. Die Methode erwartet eine Liste von Zeichenketten und verkettet die einzelnen Elemente. `join` ist eine Zeichenketten-Methode, daher müssen wir sie auf ein Trennzeichen anwenden und die Liste als Parameter übergeben:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = ['pining', 'for', 'the', 'fjords']\n",
    "delimiter = ' '\n",
    "s = delimiter.join(t)\n",
    "s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In diesem Fall ist das Trennzeichen das Leerzeichen, so dass `join` ein Leerzeichen zwischen die Wörter setzt. Um die Zeichenketten ohne Trennzeichen miteinander zu verketten, können wir die leere Zeichenkette  `''` als Trennzeichen verwenden."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.10. Objekte und Werte\n",
    "\n",
    "Wenn wir diese beiden Zuweisungen ausführen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = 'banana'\n",
    "b = 'banana'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "wissen wir, dass sowohl `a` als auch `b` auf eine Zeichenkette verweisen, aber wir wissen nicht, ob sie auf *die selbe* Zeichenkette verweisen. Es gibt zwei mögliche Zustände:\n",
    "\n",
    "![Zustandsdiagramm für zwei Zeichenketten](https://amor.cms.hu-berlin.de/~jaeschkr/teaching/spp/zustandsdiagramm_zeichenketten.svg)\n",
    "\n",
    "Im ersten Fall verweisen `a` und `b` auf zwei unterschiedliche Objekte, die den gleichen Wert haben. Im zweiten Fall verweisen sie auf das selbe Objekt.\n",
    "\n",
    "Um zu prüfen, ob zwei Variablen auf das selbe Objekt verweisen, können wir den `is`-Operator verwenden:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = 'banana'\n",
    "b = 'banana'\n",
    "a is b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In diesem Beispiel erzeugt Python nur ein Zeichenketten-Objekt und sowohl `a` als auch `b` verwiesen darauf. Wenn wir jedoch zwei Listen erzeugen, erhalten wir zwei Objekte:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [1, 2, 3]\n",
    "b = [1, 2, 3]\n",
    "a is b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das Zustandsdiagramm sieht in diesem Fall so aus:\n",
    "\n",
    "![Zustandsdiagramm für zwei Listen](https://amor.cms.hu-berlin.de/~jaeschkr/teaching/spp/zustandsdiagramm_listen_ab.svg)\n",
    "\n",
    "In diesem Fall würden wir sagen, dass die beiden Listen **äquivalent** sind, denn sie enthalten die gleichen Elemente, aber sie sind nicht **identisch**, denn sie sind nicht das selbe Objekt. Wenn zwei Objekte identisch sind, sind sie auch äquivalent; aber wenn sie äquivalent sind, sind sie nicht notwendig auch identisch.\n",
    "\n",
    "Bis jetzt haben wir die Begriffe \"Objekt\" und \"Wert\" synonym verwendet, aber es ist eigentlich präziser, zu sagen, dass ein Objekt einen Wert hat. Wenn wir `[1,2,3]` evaluieren, dann erhalten wir ein Listenobjekt, dessen Werte eine Folge von ganzen Zahlen darstellen. Wenn ein anderes Listenobjekt die gleichen Elemente enthält sagen wir, dass es den gleichen Wert hat, aber es ist nicht das selbe Objekt."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.11 Aliasing\n",
    "\n",
    "Wenn `a` auf ein Objekt verweist und wir die Zuweisung `b = a` ausführen, dann verweisen beide Variablen auf das selbe Objekt:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [1, 2, 3]\n",
    "b = a\n",
    "b is a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das Zustandsdiagramm schaut dann folgendermaßen aus:\n",
    "\n",
    "![Zustandsdiagramm für zwei Listen](https://amor.cms.hu-berlin.de/~jaeschkr/teaching/spp/zustandsdiagramm_listen_ab2.svg)\n",
    "\n",
    "Die Verbindung (*association*) einer Variable mit einem Objekt wird **Referenz** (*reference*) genannt. In diesem Beispiel gibt es zwei Referenzen auf das selbe Objekt.\n",
    "\n",
    "Ein Objekt mit mehr als einer Referenz hat mehr als einen Namen, daher sagen wir, dass dieses Objekt einen **Alias** besitzt. \n",
    "\n",
    "Falls das Objekt mit Alias veränderbar ist, dann betreffen Veränderungen, die an einem Alias vorgenommen werden auch den anderen:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "b[0] = 42\n",
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Obwohl dieses Verhalten nützlich sein kann, ist es auch fehleranfällig. Im allgemeinen ist es sicherer, Aliasing zu vermeiden wenn wir mit veränderbaren Objekten arbeiten.\n",
    "\n",
    "Bei unveränderbaren Objekte wie z.B. Zeichenketten ist Aliasing kein großes Problem. Im Beispiel\n",
    "```python\n",
    "a = 'banana'\n",
    "b = 'banana'\n",
    "```\n",
    "macht es so gut wie nie einen Unterschied, ob `a` und `b` auf die gleiche Zeichenkette verweisen oder nicht."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.12 Listen als Argumente\n",
    "\n",
    "Wenn wir eine Liste an eine Funktion als Argument übergeben, erhält die Funktion eine Referenz auf die Liste. Wenn die Funktion die Liste verändert, verändert sich auch die Liste an der aufrufenden Stelle (denn es ist die selbe Liste). Beispielsweise entfernt die Funktion `delete_head` das erste Element einer Liste:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def delete_head(t):\n",
    "    del t[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hier sehen wir, wie die Funktion verwendet werden kann und wie sie wirkt:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],