Einführung in die funktionale Programmierung

Inhalt

Überblick

Schwerpunkte in diesem Kurs

• Grundlagen funktionaler Programmiersprachen

• Konzepte funktionaler Programmiersprachen

• Praktische Relevanz und Anwendung der funktionalen Programmierung

• Funktionale Programmiersprache Haskell

Begleitet von Übungen um obige Techniken konkret anzuwenden

Vorlesung

2 SWS mit Grundlagen und Live Programming mit einfachen Programmierübungen zum mitmachen (Notebook zur Vorlesung mitbringen!)

Übung

2 SWS mit Programmierung und angewandter Vertiefung

Voraussetzungen

Grundlegende Kenntnisse der Mathematik, Grundlegende Programmierfähigkeiten (in einer beliebigen Sprache)

Literatur

Vorlesungsskript

Die Inhalte der Vorlesung werden als navigierbarer Foliensatz und kompiliertes Skript bereitgestellt

Literatur

Software

Verwendete Software (Vorlesung):

Haskell WEB Laboratory

• Einfacher WEB basierter Haskell Compiler und Interpreter (REPL)

  • Ursprung: JSHC entstanden in einer Bachelor Arbeit von Stefan Björnesjö und Peter Holm (2011, Universität Göteburg)

• Benötigt wird nur ein WEB Browser und eine einzige Datei (hslab.html) → Kann auch offline mit lokaler Kopie ausgeführt werden!

• Enthält Editor, Interpreter Shell, und Online Hilfe

• Compiler übersetzt (Untermenge) von Haskell in JavaScript → Übersetztes Programm kann auch außerhalb des Labs ausgeführt werden!

• Integriertes WEB basiertes Clipboard zum Austausch von Code in der Vorlesung (Lehrer-Student-Student)!

Software

Software

Haskell to go

• Eine weitere Version (hseddy.html) basierend auf einem Emacs Editor ist auch für Smartphones und Tabletrechner geeignet → Begleitender Einsatz in der Vorlesung!

Software

Verwendete Software (Vorlesung und Übung):

$ ghci
GHCi, version 6.10.4: 
http://www.haskell.org/ghc/ :? for help 
Loading package ghc-prim ... linking ... done. 
Loading package integer ... linking ... done. 
Loading package base ... linking ... done. 
Prelude> let sq x = x*x
Prelude> sq 3
9

Ziele

1. Die Studierenden verstehen das Paradigma der funktionalen Programmierung und beherrschen eine entsprechende Programmiersprache wie etwa

   • Haskell
   • OCAML
   • (JavaScript, Lua)

2. Die Studierenden können einfache algorithmische Probleme und Datenstrukturen funktional modellieren und können dabei Funktionen höherer Ordnung und Typkonstruktoren wie etwa

   • Funktoren, Monaden und Monoiden einsetzen

3. Die Studierenden kennen typische Szenarien der funktionalen Programmierung etwa im

   • Bereich der Numerik oder im
   • Kontext der Daten-/Web- oder parallelen Programmierung.

Inhalte

1. Funktionen mit der Mathematik als Ausgangspunkt → Mathematische Funktionen als “Programmiersprache”

2. Einführung in die Programmierung mit Haskell

3. Mehr über Funktionen: Funktionen als Werte, Funktionen höherer Ordnung, Anonyme Funktionen, usw.

4. Typisierung

   • Wie kann man Daten strukturieren und strukturiert verwenden

   • Wie kann man Typen benutzen um Randbedingungen zu beschreiben, z.B., welche Art von Daten können mit einer Funktion verarbeitet werden

   • Wie kann man Daten unterscheidbar machen (Im Programm für den Übersetzer und zur Laufzeit)

   • Wie kann man Typen konstruieren - alles nur eine Funktion?

5. Anwendung der funktionalen Programmierung

Übung

Mo. 16:00 s.t. in M 201
Umfang: 2SWS
Marcel Heinz

Ablauf der Übung:

• Besprechung der Lösungen zu den letzten Assignments

• Vorbereitung auf die neuen Assignments mit Live-Programmierung

Formalitäten:

• Es gibt 9-12 Assignments-

• Abgaben werden in SVN hochgeladen.

• Vorschlag bzgl. der Zulassung: siehe “Exam admission rules” hier: http://www.softlang.org/course:fp17

  • 3/4 der Abgaben müssen mindestens eine Bewertung von 1 Punkt bekommen.
  • 1/2 der Abgaben müssen eine Bewertung von 2 Punkten bekommen.

• Alles, was in der Übung programmiert wird, wird hoch geladen.

Geschichte

Übersicht der Programmiersprachen

Funktionale Programmierung - Warum?

• Funktionale Programmierung kann schwieriger zu Erlernen sein als prozedurale und objektorientierte Programmierung

• Aber: Mit funktionaler Programmierung lassen sich Programmierfehler reduzieren

Funktionale Programmierung - Warum?

• Probleme in der prozeduralen/imperativen Programmierung:
  • Nicht beobachtbare Seiteneffekte durch globale/geteilte Variablen
  • Prozeduren statt reine Funktionen

Kenntnis verschiedener Sprachen

Eigene Ideen bei der Software-Entwicklung können besser und effizienter ausgedrückt werden

Nötig, um in konkreten Projekten geeignete Sprache auszuwählen

Erleichtert das Erlernen weiterer Programmiersprachen

Grundlage für den Entwurf neuer Programmiersprachen

Funktionale Programmiersprachen

• Haskell: Reine funktionale Programmiersprache

• OCaML: Funktionale Programmiersprache kombiniert mit prozeduraler und objektorientierter Programmierung

• JavaScript: Prozedurale Programmiersprache kombiniert mit objektorientierter und funktionaler Programmierung

• Lua: Prozedurale Programmiersprache kombiniert mit objektorientierter und funktionaler Programmierung

Primär wird in diesem Kurs Haskell gelehrt und in den Übungen eingesetzt. Es werden aber immer wieder Analogien zu den drei weiter aufgelisteten Sprachen gezeigt.

Funktionale Programmierung - Geschichte

1930

Alonzo Church entwickelte den Lambda Calculus, eine einfache und ausdrucksstarke Theory und Notation von Funktionen

Funktionale Programmierung - Geschichte

1950

John McCarthy entwickelte Lisp, die erste Funktionale Sprache, mit etwas Einfluß vom Lambda Calclus, aber noch mit Speichervariablen und Zuweisungen

Funktionale Programmierung - Geschichte

1970

Robin Milner und andere entwicklten ML, die erste moderne Funktionale Sprache mit Typinferenz und polymorphen Typen

Funktionale Programmierung - Geschichte

1987

Ein internationales Kommitee von Forschern starteten die Entwicklung von Haskell, eine standardisierte Funktionale Sprache mit Bedarfsauswertung (lazy evaluation)

Funktionale Programmierung - Haskell

• Haskell-Interpreter ghci
  • Eingabe: Auszuwertender Ausdruck
  • Ausgabe: Ergebnis des ausgewerteten Ausdrucks
• Bsp:
  • Eingabe: sum [15, 36, 70]
  • Ausgabe: 121

Interpreter

• Führen jede Zeile des Programms nacheinander aus.
• Vorteil: Keine vorherige Übersetzung nötig, gut zur Programmentwicklung geeignet.
• Schnelles Testen und steile Lernkurve
• Nachteil: Ineffizienter als Compiler
• Ausnahme: Interpreter mit Just-in-Time Übersetzern (z.B. JavaScript und V8 Maschine)

Interpreter

Just-in-Time Compiler

• Interpreter können im wesentlichen auf drei Arten (Architekturklassen) implementiert werden:

1. Direkte Ausführung des Quelltextes (die Nutzereingabe und bereits geschriebene Skripte) (Parse → Execute)
2. Virtuelle Maschine und Übersetzung des Quelltextes in eine Zwischenrepräsentation die von einer virtuellen Maschine ausgeführt werden kann → Bytecode
3. Virtuelle Maschine mit Bytecode Übersetzung, Ausführung des Bytecodes, und ausgewählter Übersetzung des Bytecodes in nativen Maschinencode → JIT Compiler!

Beispiele

• Python: Klasse 2 (Bytecode)
• JavaScript: Klasse 2 (Spidermonkey, WEB Browser) und Klasse 3 (Google Chrome/V8, nodejs)
• OCaML: Klasse 2 (und native Codeerzeugung mit Compiler)
• Lua: Klasse 2 (Lua) und Klasse 3 (LuaJit)

Haskell WEB Labor

• Die Datei hslab.html enthält das Haskell Labor bestehend aus den folgenden Komponenten:

  • Haskell Editor mit Syntaxkontrolle
  • Interpreter Shell
  • JSHC Haskell → JavaScript Compiler
  • Ein WEB Clipboard zum Austausch von Programmkode zwischen Leher und Studenten (und untereinander)

• JSHC unterstützt nur eine Untermenge von Haskell und ersetzt daher GHC nicht!

• Es gibt leichte syntaktische Abweichungen zu Glasgow Haskell (wird darauf hingewiesen)

• Die Typsignaturen von JSHC haben etwas andere Notation als bei Glasgow Haskell

• Das Haskell WEB Labor ist experimentell! Daher unterliegt es fortlaufender Aktualisierung

Haskell WEB Labor

Einführung in die Funktionale Programmierung

Mathematik

• Mathematik ist Funktionale Programmierung ;-)

• Mathematische “Methoden”: Funktionen, Ausdrücke (Terme), symbolische Variable, Werte!

• Mathematische Funktionen bestehen aus Termen und berechnen ein Ergebnis

• Mathematische Funktionen sind zeit- und zustandslos

  Die Ergebnisse einer Berechnung hängen nur von den aktuellen Werten und nicht von Berechnungen aus der Vergangenheit ab → Kein Speicher!

• Eine symbolische Variable ist daher nur eine Ausdruckssubstituierung

• Mathematische Funktionen beschreiben Zusammenhänge und nicht im Detail die Berechnung:

Terme

• Terme sind Ausdrücke und bestehen aus:
  • Werten (Konstanten) 1 1.0 3.14 (-1,1) ..
  • Symbolischen Variablen (Literale) a b c ..
  • Operationen + - * / mod ..
  • Konditonalen Ausdrücken

Zusammengesetzte Werte

Vektoren

• Bindung von Werten des gleichen Typs (z.B. aus ℕ)

• Einzelne Elemente können durch einen ganzzahligen Index ausgewählt werden

Tupel

• Ein Tupel ist eine Bindung von verschiedenen Werten u.U. unterschiedlichen Typs

• Notation eines n-stelligen Tupels: <v₁,v₂,v₃,..,v_n>

• Beispiel komplexe Zahlen: <real,complex> : <1,-1> <2,2> ..

• Beispiel mehrsortiges Tupel: <True,1> ∈ 𝔹 × ℕ

• Anders als bei einem Vektor kann man einzelne Werte nicht direkt indizieren

• Man benötigt Musteranpassung um einzelne Elemente eines Tupels lesen zu können (wird später eingeführt, oder vordefinierte Funktionen aus der Prelude Bibliothek)

Zusammengesetzte Werte

Beispiele Tupel

Typen

• Werte, Variablen, und Funktionen können ganz verschiedene Werttypen (Datentypen) besitzen und verarbeiten

𝕀

Die Menge aller ganzen Zahlen - unendlich groß aber abzählbar! {..,-2,-1,0,1,2,..}

ℕ

Die Menge aller natürlichen Zahlen - unendlich groß aber abzählbar!

ℝ

Die Menge aller reeller Zahlen - unendlich groß und nicht abzählbar! {..,3.14,..}

𝔹

Boolesche Werte {0,1} oder {False, True}

ℂ

Die Menge aller Textzeichen (alphanumerisch) {‘a’,‘b’,‘c’,‘d’,..}

• In Programmiersprachen ist häufig die Zuordnung eines Wertes zu einem Typ nicht unmittelbar eindeutig, z.B. 0 ∈ ℝ,ℕ,𝕀

Funktionen

• Eine Funktion bildet Werte (Argumente) von Eingabevariablen a,b,c,.. (Parametern) auf Werte durch Ausgabevariablen x,y,z,.. (Ergebnisse) ab, d.h. sie führt eine Berechnung durch:

• Man unterscheidet:
  • Funktionsdefinition (Algorithmus)
  • Funktionsdeklaration (Typisierung)
  • Funktionsappliaktion (Anwendung und Evaluierung einer Funktion)

Funktionen

Formal

Def. Funktion: Eine Funktion f ist ein Tripel <𝔻_f,𝕎_f,ℝ_f> aus drei Mengen: Definitionsmenge 𝔻_f, Wertemenge 𝕎_f, und einer Relation ℝ_f

Definitionsmenge 𝔻_f

Die Menge aller Eingabewerte. Z.B. die Additionsfunktion (+) kann die Definitionsmenge 𝔻_f = ℕ × ℕ = {<0,0>, <0,1>, ..} besitzen.

Wertemenge 𝕎_f

Die Menge aller Ausgabewerte (alle möglichen Berechnungsergebnisse). Z.B. die Additionsfunktion (+) könnte die Wertemenge 𝕎_f = ℕ = { 0, 1, 2, .. } besitzen.

Relation ℝ_f

Die Relation verknüpft Eingabewerte mit Ausgabewerten. Im Beispiel der Addition wäre dies ℝ_f = { <<0,0>,0>, .. , <<2,3>,5> .. }

Funktionen

Diagramme

• Funktionen kann man als Blöcke in Diagrammnotation darstellen
• Jeder Funktionsblock hat Eingangsports (die Funktionsparameter) und ein oder mehrere Ausgangsports (Ergebnisvariablen)

Beispiel: Wurfweite

• Mathematisch:

• Block:

Links: Funktionsdefinition, Rechts: Funktionsanwendung mit konkreten Werten

Funktionen

Beispiele Funktionen

Funktionen

Aufgabe

1. Momentan gibt es nur Ganzzahlarithmetik (Int32). Im vorherigen Beispiel war die Sinusfunktion nicht implementiert. Verändere die Funktion sin und w so dass eine Näherung eines Sinus im Wertebereich Grad einen Wert von ausgibt. Eine Skalierung in w ist dann erforderlich.
   • Beachte Rundungsfehler der Ganzzahlarithmetik
   • benutze das Haskell WEB Labor

Funktionen und Datenfluss

• Das Blockdiagramm ist hierarchisch. Die Implementierung einer Funktion wird durch Unterdiagramme spezifiziert (Funktionale Komposition).

• Die Auswertung von Ausdrücken kann man sich leicht als Datenfluss durch ein Netz von Funktionskästen (Blöcken) vorstellen.

• Zum Beispiel kann die obige Formel zur Berechnung der Wurfweite folgendermaßen visualisiert werden (wobei hier der Fluss nicht von oben nach unten, sondern von links nach rechts läuft)

Funktionsrekursion

• Rekursion ist der Selbstaufruf einer Funktion

• Beispiele: Fakultät und Fibonacci

• Was ist zu beachten?

Funktionsrekursion

Terminierung

• Eine Rekursion benötigt ein Terminierungskriterium!

• Gefahr: Endlosrekursion

• Zwei ähnliche Beispiele:

Aufgabe

• Wo ist das Terminierungskriterium definiert?
• Terminieren beiden Funktionen garantiert???
• Was passiert technisch bei Endlosrekursion?

Funktionsrekursion

• Man unterscheidet zwei Arten der Rekursion, die erhebliche Auswirkungen zur Laufzeit und auf die Programmausführung haben können:

  • In vielen Programmiersprachen werden Funktionsaufrufe mittels eines Stackspeichers realisiert.
  • Bei jedem Funktionsaufruf wird ein Satz “neuer” Funktionsparameter auf dem Stack erzeugt → Gefahr: Stack Überlauf!!!

End (Tail) Rekursion

• Rekursionsaufruf einer Funktion am Ende der Funktion bzw. des Ausdrucks ohne weitere Berechnung
• Vorteil dieser Funktionsdefinition ist, dass kein zusätzlicher Speicherplatz zur Verwaltung der Rekursion benötigt wird

Kopf (Head) Rekursion

• Rekursionsaufruf einer Funktion am Anfang oder in der Mitte der Funktion bzw. des Ausdrucks mit nachfolgender Berechnung.
• Jede Kopfrekursion kann durch eine funktionale Transformation in eine Endrekursion überführt werden

Funktionsrekursion

• Folgendes Beispiel zeigt den Unterschied zwischen Kopf- und Endrekursion und den Einfluss von Akkumulatoren für Zwischenergebnisse

Kopfrekursion (!)

• Die letzte Berechnung die durchgeführt wird ist die Addition (+)!
• Solange wird der Funktionsparameter n noch benötigt!

Endrekursion

Funktionsrekursion

• Das Laufzeitverhalten unterscheidet sich grundsätzlich (Stack):

Kopfrekursion

sum(3) = 3 + sum(2)        Stack [n1=3]
 sum(2) = 2 + sum(1)       Stack [n1=3,n2=2]
  sum(1) = 1 + sum(0)      Stack [n1=3,n2=2,n3=1]
   sum(0) = 0              Stack [n1=3,n2=2,n3=1,n4=0]
  sum(1) = 1 + 0 = 1
 sum(2) = 2 + 1 = 3
sum(3) = 3 + 3 = 6

Endrekursion

sum(3) = add_sum(0, 3)     Stack [m=0,n=3]
       = add_sum(3, 2)     Stack [m=3,n=2]
       = add_sum(5, 1)     Stack [m=5,n=1]
       = add_sum(6, 0)     Stack [m=6,n=0]
       = 6

Funktionsrekursion

• Kopfrekursion hat progressiven Speicherbedarf

• Endrekursion hat konstanten Speicherbedarf

Jede (End)rekursion kann in eine bedingte Schleife (while do) mit konstanten Speicherbedarf transformiert werden

sum=0;
while (n>0) do
  sum := sum + n;
  n := n -1;
done

Funktionsrekursion

Die Praxis und Realität :-(

Haskell

JavaScript

Funktionsrekursion

Die Praxis und Realität :-)

OCAML

Funktionale Komposition

Funktionsdefinition

Die Zuordnung eines Funktionsnamens und benannten Funktionsparametern zu einer Berechnung mit einem Ausdruck: f(p₁,p₂,..) = ε(p₁,p₂,..). Die Funktionsparameter sind nur im Funktionskörper nutzbar und sichtbar.

Funktionsapplikation

Die Anwendung einer Funktion i.A. in Ausdrücken, d.h. die Berechnung mit konkreten Werten: f(ε₁,ε₂,..), wobei ε ein beliebiger Wert oder Ausdruck sein kann.

Funktionskomposition

Die Zusammensetzung neuer Funktionen aus bereits definierten Funktionen:

Funktionale Komposition

Definition, Applikation, Komposition, und Rekursion sind elementare Eigenschaften der Programmierung und von Programmiermodellen!

• Die Funktionsdefinition und Applikation erlaubt die Zerlegung von Programmen in kleine wiederverwendbare Einheiten!

• Die (Funktionale) Komposition ist hierarchisch und kann durch Blockdiagramme graphisch dargestellt werden:

Funktionale Programmierung

Die funktionale Programmierung ist ein Programmierparadigma welches die Berechnung als Evaluierung von mathematischen Funktionen behandelt und Zustand mit veränderlichen Speicher vermeidet!

• Funktionale Programmierung hat seinen Ursprung im Lambda Calculus (1930), einer formalen Methode
• Es gibt eine Vielzahl von funktionalen Programmiersprachen:

ML

Meta Language (Standard)

Haskell

Rein funktionale Programmiersprache

OCAML

Basierend auf ML, aber mit zusätzlichen prozeduralen/imperativen und objektorientierten Programmierparadigmen

LISP

Eine der ersten funktionalen Sprachen?

Funktionale Programmierung

Programmierparadigma funktionaler und deklarativer Sprachen

Spezifiziere was berechnet werden soll, nicht wie es berechnet werden soll.

• Imperative Sprachen (C, JAVA, ..) starten mit low-level Code (z.B. Assembler) und führen Abstraktionen ein um die Programmierung zu vereinfachen:
  • Schleifen
  • Funktionen (!)
• Imperative Sprachen geben die Reihenfolge von Anweisungen vor!
• Deklarative Sprachen sind durch die Sprache der Mathematik motiviert und beschreiben Funktionen oder Beziehungen

• Die charakteristische Eigenschaft deklarativer Sprachen ist die Church-Rosser Eigenschaft:

  Intuitiv besagt sie, dass die Reihenfolge der Auswertung unerheblich für das Resultat ist.

Funktionale Programmierung

Vorteile deklarativer und funktionaler Sprachen

• Korrektheitsbeweise von Programmen sind relativ einfach → Terminierung!
• Programme sind meist sehr viel kürzer als z.B. in imperativen Sprachen.
• Erste Prototypen des Codes können schnell erstellt werden (“rapid prototyping”).
• Es gibt keine inhärent sequentielle Auswertung → Parallelisierung !

Funktionale Programmierung

Nachteile deklarativer und funktionaler Sprachen

• Es gibt keine Möglichkeit den Ressourcenverbrauch zu steuern und zur Programmierzeit abzuschätzen

• Es gibt weniger Werkzeuge für den Programmentwurf

• Ein- und Ausgabe (auch Netzwerkkommunikation) ist (evtl. strikt) sequenziell!

  • IO erfordert Erweiterung des funktionalen Programmiermodells (z.B. mit Monaden) um Sequenz und Speicher zu implementieren!

Einführung in Haskell

Haskell

• Haskell ist eine rein-funktionale, nicht-strikte Programmiersprache.

• Die wichtigsten Konzepte in Haskell sind:

  • Rein funktionale Semantik (d.h. keine Seiteneffekte)
  • Algebraische Datenstrukturen mit mächtigen Operationen wie “pattern matching”, “list comprehensions”
  • Funktionen höherer Ordnung (“higher-order functions”)
  • Statisches Typensystem
  • Bedarfsauswertung (“lazy evaluation”)

• Neben Haskell sollen in diesem Kurs aber auch einige andere funktionale Sprachen beleuchtet werden: ML, JavaScript, Lua (teils,!)

• Da es auch in Haskell nicht alle Konzepte der funktionalen Programmierung gibt wird eine allgemein verständliche Pseudonotation verwendet (siehe [A])

Haskell - Basistypen

• Werte (Konstanten und symbolische Variablen) haben einen bestimmten Datentyp.

Basistypen in Haskell

Bool

Boolesche (logische) Werte: True und False

Char

Zeichenkette String ⇔ Zeichenfolgen sind Listen von Zeichen, d.h [Char]

Int

Ganze Zahlen (“fixed precision integers”)

Integer

Ganze Zahlen beliebiger Länge (“arbitrary precision integers”)

Float

Fließkommazahlen (“single-precision floating point numbers”)

Haskell - Terme

• Ausdrücke werden in Pseudonotation allgemein mit ε bezeichnet

• Ausdrücke bestehen aus (symbolischen) Variablen, Werten, Funktionsapplikationen, und Operatoren

Haskell - Symbolische Variablen

• Werte und Terme können symbolischen (unveränderlichen) Variablen zugewiesen und in folgenden Ausdrücken wieder verwendet werden (Substitution):

x = ε
let x = ε1 in ε2 

• let in wird innerhalb von Ausdrücken verwendet und ist nur innerhalb des Ausdrucks und nach der Definition sichtbar

Haskell - Bedingte Ausdrücke

Bedingte Ausdrücke

f x = if cond-ε1x then ε1 else
      if cond-ε2x then ε2 else
      ...
      else ε0

Bewachte Ausdrücke

f x | cond-ε1x = ε1
    | cond-ε2x = ε2
    ...
    | otherwise = ε0

Haskell - Bedingte Ausdrücke

Beispiel: Entscheidungsbäume

• Entscheidungsbäume werden im Maschinellen Lernen (ML) eingesetzt. Zweck des ML ist u.A. das Lernen von Zusammenhängen (Modellfunktionen) mit Trainingsdaten.

• Das Ergebnis vom überwachten Lernen ist eine Funktion die einen Satz von Eingabevariablen x₁,x₂,.., x_n auf Ausgabevariablen y₁,y₂,..,y_m abbildet:

Beispiel: Überlebenswahrscheinlichkeit Titanik Unfall

• Eingabevariablen: x₁:Geschlecht, x₂:Alter, x₃:Anzahl Verwandte

• Ausgabevariable: y:Überleben?

Haskell - Bedingte Ausdrücke

Entscheidungsbaum

• Ein mögliches ML Modell der die Funktion f() approximiert ist der Entscheidungsbaum:

  • Abgeleitet aus Protokollen des Unglücks und Statistiken

Haskell - Bedingte Ausdrücke

Mathematisches Modell

Haskell

Haskell - Listen und Tupel

Listen: Definition

• Listen werden in Haskell statisch durch eine Aufzählung von Werten (oder Ausdrücken) mit Kommatrennung in eckigen Klammerpaaren erzeugt:

[ v1, v2, ε3 , .. ] 

• Die Listenelemente sind eindeutig wie bei einem Array durch einen Index {0,1,2,..,n-1} referenzierbar.

Tupel: Definition

• Tupel werden in Haskell statisch durch eine Aufzählung von Werten (oder Ausdrücken) mit Kommatrennung in runden Klammerpaaren erzeugt:

( v1, v2, ε3 , .. )

Haskell - Listen und Tupel

Listen: Zugriff

• Auf einzelne Listenelemente oder Bereiche kann mit verschiedenen eingebauten Funktionen zugegriffen werden:

FUN head: [α] →  α
FUN last: [α] →  α
FUN tail: [α] →  [α]
FUN drop: Int → [α] →  [α]
FUN take: Int → [α] →  [α]
FUN (!!): [α] → Int →  α

Haskell - Listen und Tupel

Listen: Komposition

• Listen können zur Laufzeit neu zusammengesetzt werden:

FUN (++): [α] → [α] → [α]
FUN reverse: [α] → [α]

Haskell - Listen und Tupel

Listen: Mathematische Mengen

[x^2 | x <- [1..5]]

Haskell - Listen und Tupel

Tupel: Elementzugriff und Zerlegung

• Auf einzelne Tupelelemente oder Bereiche kann nicht direkt zugegriffen werden.

• Stattdessen muss Musteranpassung oder Zerlegung verwendet werden, d.h., im einfachsten Fall wird eine Ausdruckszuweisung verwendet mit einem Variablentupel auf der linken Seite und dem zu zerlegenden Tupel:

tuple = ( v1, v2, .. , vn) 
( x1, x2, .. , xn ) = tuple
let ( x1, x2, .. , xn ) = tuple
f  ( x1, x2, .. , xn ) = ..
fst (x,_) = x
snd (_,y) = y

Haskell - Listen und Tupel

• Wenn ein Element eines Tupels nicht verwendet wird, kann ein Platzhalter _ eingefügt werden (wildcard)

• Tupelzerlegung kann auch bei der Definition von Funktionsparametern angewendet werden

Haskell - Mehrfachauswahl und Musteranpassung

• Wie in allen gängigen Programmiersprachen gibt es auch in Haskell eine Mehrfachauswahl.

• Die Mehrfachauswahl ist aber deutlich ausdrucksstärker als z.B. switch-case in C

• Die Mehfrachauswahl ist ein Ausdruck der einen Wert berechnet!

case ε of {
  v1 -> ε1 ;
  v2 -> ε2 ;
  ..
  vn -> εn ;
  OTHERWISE
  x ->  ε0 ;  ODER 
  _ ->  ε0
}

Haskell - Mehrfachauswahl und Musteranpassung

Ein Case-Ausdruck muss mindestens eine Alternative haben und jede Alternative muss mindestens einen Körper haben. Jeder Körper muss denselben Typ haben, und der Typ des gesamten Ausdrucks ist dieser Typ.

• Werte v_i der Mehrfachauswahl können skalare Werte, Tupel, und Listenmuster (z.B. x : xs) enthalten!

Haskell - Mehrfachauswahl und Musteranpassung

Beispiel

farbe = "rot"
ist_rot col =  case col of {
                 "rot" -> True ; 
                 _ -> False
               }
ist_mischung col =  case col of {
                      "rot" -> False ; "blau" -> False; "gruen" -> False;
                      _ -> True
                    }

Haskell - Mehrfachauswahl und Musteranpassung

Tupelzerlegung

• Mit der Mehrfachauswahl können auch zusammengesetzte Werte (Tupel) zerlegt werden → Musteranpassung

case tuple-ε of {
  (v1,v2,..) -> ε1 ;
  (v1,x2,..) -> ε1 ;
  (x1,x2,..) -> ε1 ;
}

Haskell - Mehrfachauswahl und Musteranpassung

Aufgabe

1. Es soll eine Funktion disto in Haskell und dem Haskell Laboratory implementiert werden, die die Distanz zwischen zwei Punkten p₁ und p₂ im kartesischen Koordinatensystem berechnet.
   • Punkte werden durch ein Tupel (x,y) repräsentiert.

2. Implementiere eine iterative Näherung der Wurzelfunktion sqrt für ganze Zahlen

Haskell - Funktionen

Definition

DEF f (x,y,z,..) = ε(x,y,z) ⇔ DEF f x y z = ε(x,y,z)
In vielen Programmiersprachen werden die Funktionsparameter x,y,z,.. in Klammern und durch Komma getrennt definiert. Aber in ML/Haskell ist (x,y,z,..) ein Parameter (ein Tupel)! Geht auch!

f x y z .. = εx,y,z,..
f (x,y,z,..) = εx,y,z,.. 

Applikation

Definierte (oder eingebaute) Funktionen können durch Angabe des Namens und folgende Argumente für die Parameter evaluiert werden.

Haskell - Funktionen

Typsignatur

FUN f : typ1 → typ2 .. → typr ⇔ FUN f : typ1 × typ2 × .. → typr
Die Typsignatur einer Funktion (oder einer Variable) gibt die Datentypen der Funktionsparameter und des Rückgabewertes an. Kann mittels der :type Funktion angezeigt werden.

Überladung und Polymorphie

Wenn eine Funktion, z.B. Addition, für Werte von verschiedenen Typen anwendbar ist, wird eine Typklasse angegeben. Beispiel: :type (+) → (+) :: Num a => a -> a -> a mit Num als Typklasse aller numerischen Typen (ℕ ℝ ..)

Haskell - Funktionen

Beispiel: Berechnung der Wurfweite

Haskell - Funktionen

Eingebaute Funktionen (Prelude)

Arithmetische, Boolesche, Logische Operation, Mathemtische

Gehören zu den eingebauten Funktionen, häufig überladen/polymorph definiert.

Listen

Viele Funktionen wie die Summationsfunktion sum des Basismoduls Prelude arbeiten mit Listen, d.h., einsortige Listen von Elementen:
[v1,v2,v3,..]

Haskell - Funktionen

Funktionskomposition

FUN f1, FUN f2, .., DEF fN x y z .. = f1 ∘ f2 ∘ ..
Verwendung von Funktionen in Funktionen oder Definition von Funktionen und Verwendung in Funktionen!

Haskell - Funktionen

Muster mit Funktionen

• Klassisch ist eine Funktionsdefinition monolitisch, d.h. es existiert eine Definition mit:

  • Namen, Parametersatz, Körper (Ausdruck)
  • Typsignatur

• In der funktionalen Programmierung können Funktionen aber durch mehrere partielle Funktionsdefinitonen bestehen (nicht zu verwechseln mit Funktionen höherer Ordnung), die durch verschiedene Muster unterscheidbar sind.

f pat1 = ε1
f pat2 = ε2
..
f patn = εn

Haskell - Funktionen

Beispiel

count [] = 0
count (x:xs) = 1+(count xs)

Haskell - Funktionen

Aufgabe

1. Implementiere im HSLAB eine Zählfunktion, die alle Nullwerte einer Liste zählt, mit funktionaler Musterzerlegung:

   • In Mustern können auch konkrete Werte (anstelle von symbolsichen Variablen), wie z.B. der Wert 0, eingesetzt werden, z.B. div (x,0) = None
   • Starte mit count [] = 0

2. Spielt die Reihenfolge der musterbasierten Definitionen von Funktionen eine Rolle?

   • Warum?

Haskell - Sequenzielle Ausführung

Problem

• In einer rein funktionalen Sprache wie Haskell haben Funktionen keine Seiteneffekte. Deshalb spielt auch die Reihenfolge des Aufrufs eine weniger wichtige Rolle.

• Ein- und Ausgabe erzeugen einen Seiteneffekt auf die Programmumgebung. Sie müssen in der richtigen Reihenfolge ausgeführt werden.

do

Für die sequentielle Ausführung von IO-Aktionen stellt Haskell die do-Notation zur Verfügung:

do {
  Anweisung 1;
  Anweisung 2;
  ..
  Anweisung n  
}

Haskell - Sequenzielle Ausführung

JSHC Implementierung

• In JSHC gibt es keine do Anweisung.
• Daher wird die Anweisungssequenz einer do Anweisung durch einen Präprozessor in eine Liste transformiert:

do {
  I1;
  I2;   ⇒
  ..
  In  
}

reduce (+) [
  I1,
  I2,
  ..
  In  
] 

• Eine Anweisung wird als Berechnung verwendet die einen Zahlenwert als Ergebnis liefert (i.A. 0)
• Die gesamte Sequenz liefert ebenfalls einen Wert, der durch die Listenreduktion (Summation) berechnet wird
  • Annahme: Die Listenausdrücke werden der Reihe nach durch JSHC evaluiert!

Haskell - Sequenzielle Ausführung

Haskell - Eingabe und Ausgabe

putStr

Ausgabe einer Zeichenkette auf der Konsole

putStrLn

Ausgabe einer Zeichenkette mit nachfolgenden Zeilenumbruch auf der Konsole

getLine

Einlesen einer Zeichenkette von der Konsole (Tastatur

FUN putStr: String -> IO ()
FUN putStrLn: String -> IO ()
FUN getLine: IO String

Haskell - Eingabe und Ausgabe

Speichervariablen und Seiteneffekte

• Neben den IO Anweisungen gibt es Anweisungen um Daten zwischenzuspeichern → Speichervariablen!

x <- getLine;

Beispiel

main = do {
  hSetBuffering stdout NoBuffering ; -- import System.IO
  putStr "Gib eine Zeichenreihe ein: ";
  s <- getLine ;
  putStr " Revertierte Zeichenreihe : ";
  putStrLn ( reverse s)
}

Haskell - Bedingte Ausführung

if-then-else

Bedingte Ausführung von Anweisungen nur in einer do-Umgeung. Achtung: Ausführung und nicht Berechnung! Es wird ein boolescher Ausdruck cond evaluiert. Ist dieser wahr dann wird die erste then Anweisung ausgeführt, sonst die zweite else Anweisung.

do {
  if cond then
    Anweisung 1
    else
      Anweisung 2
  ..
  Anweisung n  
}

Funktionen und Lambda Calculus

Definition, Deklaration, Applikation, Komposition

Zusammenfassung der Methoden

DEF f par1 par2 .. = 
    ε(par1,par2,..)
DEF f = λ p1,p2,.. . 
    ε(p1,p2,..)
DEF f (par1,par2,..) = 
    ε(par1,par2,..)

FUN f : partyp1 → partyp2 → .. 
        → restyp
 
 
FUN f : (partyp1 × partyp2 × ..) 
        → restyp

(f arg1 arg2 ..) → Wert 
(λ x,y,.. . ε(x,y,..))

(f ∘ g ∘ h ∘ .. ) arg1 arg2 .. 

Lambda Calculus

Konzept: Jeder Ausdruck und jeder Wert wird als auswertbare Funktion betrachtet, so dass die ganze Programmierung auf der Übergabe von Funktionen als Parameter an Funktionen beruht.

Lambda Notation

• In der Lambda Notation werden Variablen an Ausdrücke gebunden

Definition 13.

Beispiel

v/g sin(2*phi) ⇔
λ v,g,phi → (v2/g sin(2*phi))
λ v,g,phi . (v2/g sin(2*phi))

Lambda Notation

Lambda Ausdrücke

• Ein Lambda Ausdruck ist eine anonyme Funktion, d.h. er definiert wie das Resultat in Abhängigkeit von der Eingabe berechnet wird ohne der Funktion einen Namen zu geben!

Freie und gebundene Variablen

• Die Bindungsregeln in einer Abstraktion λ x → ε sind so geregelt:

  • Alle Vorkommen der Variablen x im Ausdruck ε gehören zu diesem Ausdruck (sind an dieses x und die Abstraktion gebunden).

  • Die gebundenen Variablen sind nur in dem Ausdruck sichtbar und verwendbar!

  • Zum Beispiel ist im Ausdruck (λ x → (y x)) die Variable x eine gebundene Variable (durch λ gebunden), und y eine freie Variable

• Variablen (bzw. Vorkommen von Variablen), die in keinem Gültigkeitsbereich einer Bindung stehen, sind frei.

Lambda Notation

• Da es auch Konflikte geben kann durch Verwendung des gleichen Variablennamens, gilt dann die Regel: die innerste Bindung ist sichtbar/anwendbar.

• Ein Ausdruck ohne freie Variablen heißt geschlossener Ausdruck, anderenfalls offener Ausdruck.

Bindungsregeln und Klammerung

• Notation: (s t) sind Anwendungen, d.h. t wird auf s angewendet, z.B. ( sq 4 ) = 16

• Warum gilt: ( ( x y ) z ) = ( x y z )
  Aber nicht: ( x ( y z )) ≠ ( x y z ) ?
  Auflösung folgt gleich …

Lambda Notation

Beispiele

• Wo sind freie und wo gebundene Variablen?

g = 9.81
sq1 x = x*x 
sq2 = λ x -> x*x 
wurfweite1 v0 phi = 
  let sq x = x*x in 
  (sq v0)/g*(sin phi) ⇔
wurfweite2 = λ v0 phi -> ((λ x -> x*x) v0)/g*(sin phi) 
wurfweite3 = λ v0 phi -> (sq2 v0)/g*(sin phi)

Funktionen als Werte

• Funktionen sind Werte erster Ordnung, d.h. f = λp . ε ⇔ f p = ε

• Eine Funktion kann symbolischen Variablen und Funktionsparametern zugeordnet werden

  • D.h. Funktionen können Funktionen als Argumente übergeben werden

• Ein Lambda Ausdruck ist eine Funktion als Wert und kann von einer Funktion als Ergebnis geliefert werden!

Beispiele

f comb x y  = (comb x y)/2
p = f
m = p (+) 1 2
incr = (+) 1

function f (comb,x,y) { return comb(x,y)/2 }
function add (x,y) { return x+y }
var p = f;
var m = p (add,1,2)
incr = function (x) { return x+1 }

Anonyme Funktionen

• Eine anonyme Funktion beschreibt die Abbildung von Variablen auf Werte ohne der Funktion einen konkreten Namen zu geben!

• Da Funktionen auch Werte sind und Funktionsparametern übergeben werden können gibt es zwei Anwendungsfälle:

  • Eine anonyme Funktion wird “identifizierbar”, d.h. anwendbar, durch Zuweisung (Bindung) an eine gebundene oder freie Variable

  • Eine anonyme Funktion wird “identifizierbar” durch Bindung an einen Funktionsparameter (eigentlich das gleiche)

• Ein Lambda Ausdruck ist eine anonyme Form (wie gehabt)!

\ x y z -> ε(x,y,z,..) ⇔
\ x y z . ε(x,y,z,..) ⇔
λ x y z → ε  

Anonyme Funktionen

• Sehr nützlich bei wiederholter Anwendung einer Funktion auf Listenelemente

• Wichtige Methode der Datenverarbeitung: Map & Reduce

Beispiele

l = [1,2,3]
sq x = x*x
squares = map sq l

var l = [1,2,3]
function sq (x) { return x*x }
var squares = l.map(sq)

Data Mining - Datenverarbeitung

Ein kleiner Ausflug in Big Data ..

Motivation

• Großskalige Datenverarbeitung

  • Viele Daten verarbeiten (> 1 TB)
  • Parallelisierung auf Hunderttausende von CPUs
  • Einfache Handhabung und Umsetzung

• Map-Reduce bietet:

  • Automatische Parallelisierung und Verteilung
  • Fehlertoleranz
  • Stellt Status- und Überwachungstools bereit.
  • Abstraktion für Programmierer

Data Mining - Datenverarbeitung

Funktionale Programmierung

• Map-Reduce Algorithmen, wie sie z.B. im Hadoop System verwendet werden, haben Ähnlichkeit mit funktionalen Programmiersprachen (wenn auch Map&Reduce kein spezifisches funktionales Problem ist):
  • Funktionale Operationen verändern keine Datenstrukturen: Sie erstellen immer neue;
  • Originaldaten sind unverändert vorhanden;
  • Datenfluss ist im Programmdesign implizit;
  • Reihenfolge der Operationen spielt keine Rolle.
  • Funktionale Programmierung wendet Operationen auf Listen an

Data Mining - Datenverarbeitung

Map0

function (f: ’a->’b, ’a list) -> ’b list

Ursprüngliche funktionale map Funktion. Erzeugt eine neue Liste durch Anwendung einer Funktion f auf jedes Element der Eingangsliste (oder Arrays) → Abbildung

[a]

Data Mining - Datenverarbeitung

Map

function (in_key,in_value) -> (out_key,intermediate_value) list

Adaption der ursrptünglichen map Funktion. Datensätze von einer Datenquelle (Zeilen aus Dateien, Zeilen einer Datenbank usw.) werden als Schlüssel / Wert-Paare in die Abbildungsfunktion eingegeben: z. B. (Dateiname, Zeile). map erzeugt aus der Eingabe einen oder mehrere Zwischenwerte zusammen mit einem Ausgabeschlüssel.

[a]

Data Mining - Datenverarbeitung

Fold

function (f:'a*'b->'b, x0:'b, lst;'a list) ->'b

Ursprüngliche funktionale fold Funktion. Iteriert über eine Liste und wendet f auf jedes Element plus einen Akkumulator an (Anfangswert x₀). f gibt den nächsten Akkumulatorwert zurück, der mit dem nächsten Element der Liste kombiniert wird → Reduktion.

[a]

Data Mining - Datenverarbeitung

Reduce

function (out_key, intermediate_value list) -> out_value list

Adaption der ursprünglichen fold Funktion. Nach der Beendigung der Abbildungsphase werden alle Zwischenwerte für einen bestimmten Ausgabeschlüssel zu einer Liste zusammengefasst. reduce kombiniert diese Zwischenwerte zu einem oder mehreren Endwerten für denselben Ausgabeschlüssel (in der Praxis normalerweise nur ein Endwert pro Schlüssel)

[a]

Data Mining - Datenverarbeitung

Map-Reduce Methode in Hadoop

• Daten werden verteilt im HDFS (Hadoop Distributed File System) abgelegt

• Datenblöcke werden mehreren Mappern zugewiesen, die Schlüssel-Wert-Paare ausgeben, die parallel gemischt und sortiert werden.

• Der Reduzierungsschritt gibt ein oder mehrere Paare (mit Daten die den gleichen Schlüssel haben) aus, wobei die Ergebnisse im HDFS gespeichert werden

Data Mining - Datenverarbeitung

Curry Form

Bei der Curryfizierung findet eine Umwandlung einer einzelnen Funktion mit n Argumenten in n Funktionen mit je einem einzelnen Argument statt.

• Traditionell kennen wir nur Funktionen die eine Menge von Argumenten als “ganzes” evaluieren, d.h., Eingabewerte führen immer zu Ausgabewerten (Zahlen usw.)

• Da Funktionen aber auch Funktionen zurück geben können kann man (wie bisher schon geschehen) die Funktion zerlegen und die Funktionsargumente einzeln evaluieren → Curry Schreibweise (vom Mathematiker Haskell Curry)

FUN f x y z : typx → typy → typz → typr ⇔  
FUN f x y :  typx → typy → ( typz → typr ) ⇔
FUN f x :  typx → ( typy → typz → typr )

Curry Form

• Die Curry Form ist häufig flexibler (nützlicher) als die Tupelform durch partielle Applikation

• Beispiel: Die Definition einer neuen Inkrementalfunktion und Abbildungsfunktion für Listen

incr = (+) 1
mapsq = map \x -> x*x

Curry Form

Beispiel

f (x,y,z) = x+y+z ⇔
f x y z = x+y+z   ⇔
f x = \ y -> \ z -> x+y+z
f = \ x -> \ y -> \ z -> x+y+z

function f(x,y,z) = { return x+y+z } ⇔
function f(x) = { 
  return function (y) {
    return function (z) {
      return x+y+z
    }
  }
}  

Curry Form

• Man kann die Curry Form immer in eine nicht-Curry Form transformieren:

uncurry f (x,y) = f x y
curry f x y = f(x,y)

• Die folgenden Funktionen unterscheiden sich daher mathematisch nur minimal (bezüglich des Funktionsraumes)

f1 (x,y) = x*2+y*3
f2 (y,x) = x*2+y*3
f3 x y = x*2+y*3
f3 y x = x*2+3*y

Curry Form

Funktionen höherer Ordnung

• Konzepte:
  • Funktionen sind Werte
  • Funktionen als Parameter
  • Funktionen als Rückgabewerte von Funktion

Funktionen höherer Ordnung (“higher-order functions”) nehmen Funktionen als Argumente oder liefern Funktionen als Resultate.

• Bei der funktionalen Komposition werden Funktionen statisch (also zur Programmierzeit) zu neuen Funktionen zusammengesetzt

• Mit Funktionen höherer Ordnung kann man dynamisch zur Laufzeit neue Funktionen erzeugen!

• Funktionen höherer Ordnung stellen eine Abstraktion und Generalisierung dar.

Funktionen höherer Ordnung

Beispiel: Listen

• Listen (oder Vektoren) werden häufig mit der gleichen Funktion transformiert, d.h. sum sq [1,2,3]

Beispiel: Integral

• Das Integral einer Funktion f im Interval [a,b] (Bestimmtes Integral):

int f delta = \ a b -> 
  (sum (map f [ x*delta | x <- [a/delta..b/delta] ]))*delta

Funktionen höherer Ordnung

• Die Anwendung der int f delta Funktion ist eine partielle Applikation von f und liefert eine neue Funktion als Wert zurück!

Totalisierung

Partielle Funktionen

• Es gibt Funktionen bei denen der Definitionsbereich nicht vollständig auf den Wertebereich abgebildet werden kann.

• Die bekannteste partielle Funktion ist die Ganzzahldivision :

𝔻=< ..,<0,0>, <0,1>, <1,0>, <1,1>, <4,2>, ..>

Teilmenge des Definitionsbereiches von

𝕎= <0,1,2,3,4..>

Wertebereich der Divisionsfunktion

ℝ=< .., <<0,0>,⊥>, <<0,0>,0>, <<1,0>,⊥>, <<1,1>,1>, <<4,2>,2>,..>

Die Relationsmenge enthält ‘Löcher’ wo der Nenner 0 ist

Totalisierung

• Unvollständige Funktionen stellen mathematisch wie numerisch/informatorisch ein Problem dar

Totalisierung

• Die Totalisierung fügt ein symbolisches “Not a Number” für ein undefiniertes Ergebnis einer Funktion ein um die Relationsmenge vollständig zu machen

• Dazu wird das Symbol “NaN” oder mathematisch ⊥ dem Wertebereich hinzugefügt:

  • 𝕎^* := 𝕎 ∪ {⊥}

Beispiel

• Totalisierung der Divisionfunktion durch Einführung eines Summentyps:

data Num x = NaN | Value x
div a b = if b == 0 then NaN else Value (a/b)
add (Value a) (Value b) = Value (a+b) 

Totalisierung

Aufgabe

1. Erweitere die Totalisierung der arithmetische Funktionen damit diese mit den “Werten” NaN umgehen können

Polymorphie

• Polymorphie bedeutet die Möglichkeit dass Variablen und Funktionsparameter Werte mit verschiedenen Datentypen annehmen können.

• Dabei gibt es zwei (+1) Arten von Polymorphie:

  • Statisch: Bei der Definition und Applikation im Programm: Der konkrete Datentyp wird zur Kompilierungszeit durch die Applikation festgelegt → Typinferenz (Haskell)

  • Dynamisch: Zur Laufzeit können Variablen und Funktionsparameter noch Werte mit unterschiedlichen Datentypen aufnehmen und verarbeiten (JavaScript)

  • Überladung: Es wird nicht eine polymorphe Funktion definiert und mit unterschiedlichen Typsignaturen verwendet, sondern eine Menge gleichnamiger Funktionen mit unterschiedlichen Typsignaturen die dann bei der Applikation zur Kompilierungszeit zugeordnet werden.

• Polymorphe Funktionen können polymorphe Funktionen verwenden/aufrufen. Aber:

Polymorphie

• Das Problem: Irgendwann zur Kompilierungs- oder Laufzeit müssen Werte mit konkreten Funktionen/Operatoren verarbeitet werden.

Beispiel: Arithmetik

Eine polymorphe Funktion zur Addition von: Ganzen Zahlen (Int), reellen Zahlen (Real), und Zeichenketten ([char]):

FUN add: α → α → α 
FUN addInt: Int → Int → Int 
FUN addReal: Real → Real → Real 
FUN addString: [char] → [char] → [char] 

Beispiel: Tupel und Listen

fst :: (a,b) → a     snd: (a,b) → b 
fst(x,_) = x          snd(_,y) = y 

Polymorphie

Beispiel: Listen

map :: (t → u) → [t] → [u] 
map f [] = [] 
map f (a : tail) = f a :  map f tail

Anwendungsbeispiel: Quicksort

• Sortierung ist ein gutes Beispiel für ein Divide&Conquer Problem, welches man auf einen map-reduce Algorithmus zurückführen kann.

qsort :: [Int] → [Int]
qsort [] = [] 
qsort (x:xs) = 
  qsort smaller ++ [x] ++ qsort larger 
  where
    smaller = [a | a <- xs, a <= x] 
    larger  = [b | b <- xs, b > x ]

• Bei der Sortierung können die Werte einer Liste aufsteigend [1,2,3,..] oder absteigend [10,9,8,..] sortiert werden.

• Frage: Werden im obigen Algorithmus die Werte einer Liste aufsteigend oder absteigend sortiert?

Anwendungsbeispiel: Quicksort

Beispiel

Anwendungsbeispiel: Quicksort 2.0

• Im vorherigen Beispiel wurden die Elemente mittels der eingebauten relationen Funktionen <= und < sortiert, anwendbar nur auf numerische Werte.

• Erweiterung der Sortierung auf beliebige Werttypen mittels nutzerdefinierten Vergleichsfunktionen cmp(a,b) die 0 liefert wenn a==b, -1 wenn a<b, sonst 1:

qsort :: (Int → Int → Bool) → [Int] →  [Int] 
qsort cmp [] = [] 
qsort cmp (x:xs) = 
  qsort cmp smaller ++ [x] ++ qsort cmp larger 
  where
    smaller = [a | a <- xs, (cmp a x) != 1 ] 
    larger  = [b | b <- xs, (cmp b x) == 1 ]

Anwendungsbeispiel: Quicksort 2.0

Funktoren

• Funktoren sind Parametrisierte Strukturen

• Strukturen werden im nächsten Kapitel eingeführt und dienen der namentlichen Bindung von Werten.

• Neben der klassischen Polymorphie mit ihrer Einschränkung auf Typvariablen stellt eine Parametrisierung von Strukturen eine Möglichkeit bereit, in der neben Typvariablen auch Funktionsvariablen vorkommen können.

• Dieses Programmierkonstrukt basiert auf Modularisierungstechniken.

Später mehr …

Datentypen

Typisierung

• Bisher wurden z.B. Funktionen oder auch Ausdrücke ohne explizite Typdeklaration definiert oder berechnet. Untypisch in traditionellen Programmiersprachen wie C, C++, JAVA, usw.

• Die Datentypen werden dabei in der funktionalen Programmierung durch Ableitung (Typinferenz) ermittelt. Wenn nicht möglich gibt wird der Typ eines Wertes bzw. Funktionsparameters durch einen Platzhalter vorläufig bestimmt → α, β, ..

• Man kann aber auch explizit Typen und Typsignaturen angeben, in folgender Form:

Beispiele

sum a b = a+b
sumInt a b = (a::Int)+(b::Int)
mapInt f l = map f (l::Int)

Typisierung

• Typen sind auch nur Terme!

• Daher kann man neue Typen mit Typausdrücken konstruieren

• Einfachster Typausdruck: Synonym

Beispiele

type Euro = Double
type Dollar = Double
type Exchange = (Euro , Dollar)
type ExchangeBack = (Dollar , Euro)
let exchange euro = ((euro::Euro)*1.2)::Dollar
::t exchange
>> exchange :: Euro -> Dollar

Typprüfung

Dynamische Prüfung (run-time check)

Bei der Ausführung des Programms wird bei jedem Aufruf f(e) einer Funktion f: A → B überprüft, ob der Argumentwert e dem geforderten Typ A genügt und ob das Resultat dem Typ B genügt.

• Vorteil: Ausdrucksstarkes Typsystem; Nachteil: Performanz zur Laufzeit (Typprüfung)

Statische Prüfung (compile-time check)

Der Compiler analysiert das Programm (mit Tpydeklarationen und Typinferenz) um sicherzustellen, dass jeder Funktionsaufruf die Typisierung erfüllt. Man kann das als den einfachsten Grenzfall einer Programmverifikation auffassen.

• Vorteil: Prüfung findet nur einmal statt; Nachteil: Typkonzepte müssen einfach sein um automatisch bewiesen zu werden (durch den Compiler)

Typinferenz

• Die Typeinferenz ist die Fähigkeit eines Übersetzers oder einer Laufzeitumgebung den Datentype von Variablen, d.h. Ausdrücken, Funktionsparametern und Rückgabewerten aus eine Kette (Baumstruktur) von Applikationen und Ausdrücken abzuleiten

• Bei der Typinferenz wird nach konkreten Datentypen gesucht und diese entlang des Evaluierungsbaums von Ausdrücken propagiert und aufgelöste Typen substituiert.

• Beispiel:
  ⇒
  ⇒ ⇒
  da ⇒ da und ⇒
  ⇔
  

Typinferenz

Beispiel: Listen

id x = x
incr x = x+1
incr2 x = x+1.0
map :: (t → u) → [t] → [u] 
map f [] = [] 
map f (a : tail) = f a :  map f tail
mapDecr = map (\ x -> x-1)

Algebraische Datentypen

• Algebraische Datentypen werden benutzt um Werte (Daten) namentlich zu binden und identifizierbar zu machen.

Eine der häufigsten Gründe für die Einführung neuer Datenstrukturen ist die Beobachtung, dass eine Gruppe von Daten logisch zusammengehört und gemeinsam etwas Neues, Eigenständiges darstellt.

• Interessanterweise zeigt sich bei Datenstrukturen das gleiche Phänomen wie bei Funktionen: Die reiche Fülle von Möglichkeiten erwächst aus einer kleinen Zahl von elementaren Konstruktionsprinzipien. Dies sind bei Funktionen:

  • Funktionsdefintion, Funktionsapplikation, Funktionskomposition, Tupelbildung, Fallunterscheidung und Rekursion;

• Bei Datenstrukturen:

  • Definition, Komposition, Produktbildung, Summenbildung und Rekursion!

Algebraische Datentypen

• Unser Ziel ist also: Wir wollen aus vorhandenen Datenstrukturen neue Datenstrukturen aufbauen.

• Dafür gibt es im Wesentlichen drei Konstrukte:

  • Tupelbildung, Arrays (Produkt);
  • Variantenbildung (Summe oder Gruppe);
  • Aufzählung.

• Dass diese Konstrukte die elementaren Bausteine eines ganzen Universums von Datenstrukturen sind , ist keine Entdeckung der Informatik , sondern - wieder einmal - der Mathematik, genauer: der elementaren Mengenlehre.

• Auch eine zweite Beobachtung verdanken wir der Mathematik, und zwar diesmal der Algebra: Die Konstruktion von Datenstrukturen liefert nicht nur Mengen neuer Werte, sondern gleichzeitig auch kanonische Operationen fur diese Werte: Datenstrukturen und ihre kanonischen Operationen bilden eine logisch zusammenqehöriqe Einheit - das Eine macht ohne das Andere keinen Sinn.

Algebraische Datentypen :: Produkttypen

• Produkttypen sind Aggregationen und Gruppentypen

Einsortige Produkttypen

• Listen und Arrays sind Produkttypen, d.h. die Elemente eines Produkttyps werden prinzipiell alle zusammen in Berechnungen verwendet (e₁ und e₂ und ..)

• I.A. ist der Datentyp der Elemente gleich, d.h. es handelt sich um einen einsortige Komposition

• Die Elemente von Produkttypen sind i.A. durch einen Index (ganze Zahl) identifizierbar und referenzierbar.

Mehrsortige Produkttypen: Tupel

• Tupel sind mehrsortig, d.h., die Werte der einzelnen Tupelelemente können zu verschiedenen Datentypen gehören.

• Aber die Elemente sind anonym (wie anonyme Funktionen) und nicht selektierbar

Algebraische Datentypen :: Produkttypen

• Tupel werden i.A. ohne vorherige Typdefinition erzeugt (anonym und dynamisch zur Laufzeit)

• Es können aber auch namentliche Tupeltypen definiert werden:

Mehrsortige Produkttyen: Datenstrukturen/Records

• Hier sind die Elemente des Produkttyps über einen eindeutigen Namen (i.A. auf den speziellen Produkttyp begrenzt) identifizierbar und referenzierbar (selektierbar).

• Die gesamte Typsignatur eines mehrsortigen Produkttyps ist genau wie beim Tupel ein Produkt der Typen der Einzelelemente:

Algebraische Datentypen :: Produkttypen

• Die Definition eines Strukturtyps (Gruppenbildung) erfordert die Aufzählung der Typelemente in Form von Tupeln <Name_i,Typ_i>,

• Die Definition eines Strukturtyps kann wieder rein funktional durch eine Typkonstruktionsfunktion erfolgen, die i.A. gleichnamig wie der Produkttyp ist:

Beispiele

DATA point  == point(x : real, y : real)
DATA line   == line(p1: point, p2: point)
DATA circle == circle(center:point, radius: real)

Algebraische Datentypen :: Produkttypen

Erzeugung von Datenstrukturen

• Die reine Typdefinition ist hier nicht ausreichend. Sinn macht sie nur bei der Instanzierung (Erzeugung) von Daten (zusammengesetzten Werten) mittels der Konstruktionsfunktion

Zugriff auf Strukturelemente

• Der Sinn und Zweck der namentlichen Kennzeichnung von Elementen ist der einfache Zugriff auf die Elemente über deren Namen. Auch dieser Zugriff kann funktional über eine gleichnamige Selektorfunktion erfolgen:

Algebraische Datentypen :: Produkttypen

• D.h. um auf ein Element einer Datenstruktur des Typs (lesend) zugreifen zu können wird die Funktion verwendet → Die Selektorfunktion liefert den Wert des Elements.

• Häufige wird eine Kurzschreibweise in der Form verwendet, wobei eine vom Typ abgeleitete Datenstruktur ist.

• In vielen Programmiersprachen sind die Strukturelemente (Variablen) ebenso (über die Selektorfunktion) veränderlich. Nicht so in der (strikten) funktionalen Programmierung!

Definition eines Strukturtyps in Haskell

• Im Grunde sind Datenstrukturen (Records) in Haskell typisierte Tupel!
• Zunächst definiert man einen Summentyp (kommt später) T mit nur einem Untertyp (kann gleichnamig sein) T über das Schlüsselwort data und den Strukturelementen als Parameter des Summentypelements T:

Algebraische Datentypen :: Produkttypen

Beispiel

data Eintrag = E
String -- Vorname
String -- Nachname
String -- Straße
String -- Stadt
String -- Land
getVorname :: Eintrag -> String
getVorname (E n _ _ _ _) = n
setVorname :: String -> Eintrag -> Eintrag
setVorname n (E _ a b c d) = E n a b c d
createVorname :: String -> Eintrag
createVorname n = E n undefined undefined undefined undefined
-- analog für die weiteren Felder
-- ...

Algebraische Datentypen :: Produkttypen

Handhabung von Datenstrukturen in Haskell

• Da es in Haskell nicht direkt die Möglichkeit gibt einen Strukturtyp (Record mit namentlicher Identifizierung der Elemente) zu definieren geht man wie folgt vor:

1. Definition eines einelementigen Summentyps:
   data T = T typ1 typ2 ..
2. Definition der einzelnen Selektionsfunktionen über eine Musterzerlegung:
   ei (T _ .. xi _ ..) = xi
3. Instanzierung von Werten vom Strukturtyp T:
   s = T ε1 ε2 ..

Algebraische Datentypen :: Produkttypen

Recordsyntax in Haskell

• Da bei der Tupeltypisierung keine Elementnamen enthalten sind wird die Strukturtypdefinition und Verwendung schnell unhandlich und verwirrend.

• Erweiterte Tupeltypdefinition und Elementselektion mit Feldnamen:

Beispiel

data Eintrag = E {
  vorname :: String,
  nachname :: String,
  strasse :: String,
  stadt :: String,
  land :: String }

Algebraische Datentypen :: Produkttypen

Beispiele in Haskell

Beispiele in JavaScript

Algebraische Datentypen :: Summentypen

• Sehr häufig hat man das Problem, dass ein Typ Elemente zusammenfassen soll, die inhaltlich etwas Gemeinsames darstellen, aber strukturell unterschiedlich aufgebaut sind.

• In diesen Situationen lassen sich die Elemente des Typs in verschiedene Varianten klassifizieren. Im Sinne der Mengenlehre haben wir es dann mit einer so genannten direkten Summe zu tun, d.h. im Wesentlichen mit einer disjunkten Vereinigung.

Beispiele

DATA figure == line(pl : point , p2 : point)
               triangle (pl : point, p2 : point, p3 : po int)
               circle( center: point, radius : real)
DATA address == st (plz : nat , ort: denotation, str : denotation)
                pf (plz : nat , ort : denotation, postfach : nat )
DATA result == ok(value : real)
               error(message : denotation)
DATA infNat == normal(value : nat)
               infinity

Algebraische Datentypen :: Summentypen

• Konstruktor-Varianten. Diese Beispiele illustrieren, dass ein Summentyp aus mehreren Varianten besteht, die ihrerseits Produkte sind.

• Als Grenzfall sind auch Konstanten als Varianten möglich → Aufzählungstyp. Da die einzelnen Varianten Produkte sind, können wir ihre Konstruktorfunktionen wie üblich benutzen, um die Elemente des Summentyps zu erhalten.

Summentypen in Haskell

Algebraische Datentypen :: Summentypen

Summentypen in JavaScript

• JavaScript kennt keine Summentypen
• Implementierung mit mehrsortigen Strukturen die ein gemeinsames Tag Element besitzen.

var line = { 
  tag:'line', 
  p1:{tag:'point',x:0,y:20} , .. };
var circle = {
  tag:'circle', 
  center:{tag:'point',x:0,y:20} , .. };
function Line (p1,p2) {
  return {tag:'line',p1:p1,p2:p2}
}
function Circle (center,radius) {
  return {tag:'circle',center:center,radius:radius}
}
function height (o) {
  switch (o.tag) {
   case 'line': return Math.abs(o.p1.y-o.p2.y);
   case 'circle': return o.radius*2;
  } }

Datentyp Some-or-None

• In vielen Funktionen können Fehler auftreten, die den Benutzer nicht weiter interessieren. Er möchte lediglich wissen, ob die Berechnung erfolgreich war.

• Z.B. die Suche in einem Telefonbuch ergibt als Ergebnis keinen Eintrag. Häufig wird dann ein “leeres” Ergebnis (0, [], ..) zurückgegeben.

• Besser ist ein Summentyp für das Ergebnis der entweder einen konkreten gebundenen Wert Some ϕ zurück gibt oder ein Symbol None:

data Maybe v = Some v | None 

Beispiele

teilen :: Int -> Int -> Maybe Int
teilen n 0 = Nothing -- man kann nicht durch 0 teilen
teilen n m = Some (div n m)
teilenMoeglich :: Int -> Int -> String
teilenMoeglich a b = case (teilen a b) of
  Some _ -> " Der Divisor war nicht 0"
  Nothing -> " Die Division ist nicht möglich"

Algebraische Datentypen :: Summentypen

• Algebraische Datentypen können wie im Fall Maybe polymorph definiert werden!

• An die Daten von Summentypen und deren Elementen kann man wieder nur über eine Musterzerlegung gelangen, d.h., ein Ausdruck mit der Subtypkonstruktion (der Variante) auf der linken Seite mit Parametern und dem zu zerlegenden Wert:

Algebraische Datentypen :: Summentypen

Aufzählungstypen

• Der Aufzählungstyp ist ein Spezialfall des Summentyps mit rein symbolischen Elementen (d.h. Produkttypen nullter Ordnung):

• Die folgenden Typen illustrieren Situationen, in denen eine kleine Gruppe von Werten einen neuen Typ darstellt.

• Achtung: In Haskell fangen Typnamen immer mit einem Großbuchstaben an, daher auch die Summentypelemente!

data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday
data Color = Blue | Green | Red | Yellow
data Switch = On | Off
data TrafficLight = Green | Amber | Red
today = Tuesday

Aufzählungstypen

Rekursive Algebraische Typen

• Typkonstruktoren können wie bereits eingeführt wurde auf gewisse Weise als Funktionen über Typen interpretiert werden.

• Rekursion lässt sich nicht nur als Entwurfstechnik für Funktionen verwenden, sondern auch für die Definition von Datentypen.

• Oft enthält eine Datenstruktur als Bestandteile wieder Elemente derselben Sorte.

• Ausdrücken lassen sich solche Typen mit Hilfe von Produkten und Summen, wobei - analog zur Funktionsdefinition - jetzt der deklarierte Typ selbst auf der rechten Seite vorkommt.

• Die Liste haben wir bereits als rekursiven Datentypen kennen gelernt. Eine Liste ist entweder leer oder sie besteht aus einem Kopfelement und einer Restliste. Als algebraischen Datentypen können wir das beispielsweise wie folgt definieren:

data List a = Nil | Cons a (List a)

Module

• Aus Gründen der Wiederverwendbarkeit, Wartung und Fehlerlokalisierung ist es ratsam, Programme in Teile zu zerlegen und durch diese Modularisierung das Abstraktionsniveau zu erhöhen:

  • Funktionen
  • Typen
  • Module
  • Bibliotheken

• Gerade bei Projekten mit mehreren Programmierern ist es ratsam, Aufgaben in mehrere Bereiche aufzuteilen, die dann parallel bewältigt werden.

• Ein wichtiges Konzept für große Softwareprojekte stellt die Definition von Schnittstellen (Interfaces) dar → Typsignaturen

• Ein Modul besteht aus Deklarationen (Schnittstelle) und Definitionen (Implementierung)

• Haskell bietet in diesem Zusammenhang die Definition von Modulen an.

Module

• Ein Modul wird in Haskell mit dem Schlüsselwort module definiert.

• Höchstens ein Modul pro Datei ist dabei erlaubt.

• Als Konvention gilt, dass der Name eines Moduls identisch mit dem Dateinamen ist.

module M (
    e1,
    e2,
    e3,
    ..
    ei
  ) where 
ei :: typi
ei = εi 
..

Module

• Die in einem Modul definierten Elemente (Funktionen, Typen, Terme) sind nur innerhalb des Moduls nach where sichtbar. Daher:

• Module bzw. Ausschnitte (einzelne Funktionen usw.) können in andere Module über das Schlüsselwort import importiert werden (Ein Skript ist ebenso ein Modul):

import M (e1, e2, .. )

• Einzelne Elemente lassen über den Punktoperator M.ei selektieren.

Typklassen

• Typklassen bieten die Typisierung von Typen!

• Man erhält ein abgestuftes System der Typisierung (horizontal), verbunden mit einem abgestuften System der Modularisierung (vertikal).

• Der innerste Bereich betrifft die Werte. Dies sind atomare Werte wie Zahlen, Buchstaben etc., zusammengesetzte Werte wie Tupel, Listen, Arrays etc. und auch Funktionen.

Typklassen

• Die Werte werden durch Typen klassifiziert. Es gibt atomare Typen, Tupeltypen, Funktionstypen etc.

• Die Typen wiederum werden durch Typklassen klassifiziert. Dazu gehören Konzepte wie Eq, Ord, Numeric usw.

• Auf der ersten Modularisierungsstufe erlauben Strukturen die Zusammenfassung von Werten und Typen zu neuen Einheiten.

• Diese Strukturen werden durch Spezifikationen typisiert.

Typklassen

• Zu Typklassen gehören Operatoren wie z.B. die Gleichheitstest und Relationen (Klasse Eq) oder ein Formatted Printer (Klasse Show)

Eq

Alle Typen in Eq unterstützen die Funktionen (==) und (/=).

Ord

Alle Typen in Ord haben eine (<=) Relation auf ihren Typen und unterstützen alle weiteren Vergleichsoperatoren

Show

Alle Typen in Show verfügen über eine textuelle Formatierungsfunktion für die Ausgabe von Werten auf dem Bildschirm.

Typklassen

Typklassen

Instantiierung

Um beispielsweise einen neuen Datentypen zu einer Instanz der Klasse Show zu machen, müssen wir eine Funktion schreiben, die die Werte dieses Typen in Strings umwandelt.

• Ein Beispiel einer Instantiierung einer nutzerdefinierten Enumeration mittels des Schlüsselwortes deriving:

data Saison = Fruehling | Sommer | Herbst | Winter 
     deriving(Eq, Ord, Enum, Show, Read, Bounded)

• Der neue Datentyp wird den Typklassen Eq, Ord, Enum, Show, Read, und Bounded hinzugefügt (eine Instanz von den Typklassen).

Typklassen

Manuelles Instantiieren

Alternativ zur automatischen Instantiierung von Typen zu Klassen lassen sich diese auch manuell vornehmen.

• Das ist in den Fällen erforderlich, wenn entweder eine automatische Instanz für den Typen nicht erzeugt werden kann oder die erzeugte Instanz nicht das Gewünschte leistet.

instance Klasse Datentyp 
  where ...

Typklassen

Beispiele

data Boolean = T | F
  
instance Show Boolean 
  where 
  show T = "Wahr" 
  show F = "Falsch"
  
instance Eq Boolean     instance Ord Boolean 
  where                   where 
  T == T = True             F <= T = True 
  F == F = True             x <= y = x == y            
  _ == _ = False
  

Abstrakte Datentypen

Abstrakte Datentypen

• Abstrakte Datentypen (ADT) werden in Programmen verwendet um neue
  • Datenstrukturen (Realisierung der Objektmengen eines ADT’s mit Mitteln der Programmiersprache) und
  • Operationen (Algorithmen)

einzuführen (Vergleiche Haskell Intensivkurs [C]) .

• Dabei dienen die Operationen dem Zugriff und der Manipulationen der durch den ADT strukturierten Daten
• Ein ADT ist ein nutzerdefinierter Typ der Operationalität einführt die die Programmiersprache selber nicht bereit stellt.
• Beispiele
  • Listen (einfach und doppelt verkettet)
  • Warteschlangen
  • Wörterbücher und Hashtabellen
  • Stapelspeicher
  • Datenbanken
  • Bäume und Graphen
  • …

Wörterbuch

• Der abstrakte Datentyp Wörterbuch findet in vielen Anwendungen seinen Einsatz und trägt den Namen aufgrund der Ähnlichkeit zum physikalischen Wörterbuch.

• Elemente können mit einem Schlüssel darin abgelegt und anschließend effizient wieder gefunden werden.

• Ein Wörterbuch ist eine Liste von (Schlüssel,Wert)-Tupeln.

• Die Frage ist wie können Einträge Schnell anhand des Schlüssels gefunden werden?

Randbedingungen

• Ist der Schlüssel eine ganze Zahl oder eine Zeichenkette? Au falle Fälle sollte er abzählbar sein (Typ Ordinal).

• Der Schlüssel kann eindeutig oder mehrdeutig sein (relevant und kritisch)

• Ein Wert (der Datensatz) kann einzigartig sein oder nicht (Mehrdeutigkeit nicht relevant und unkritisch)

Wörterbuch

• Implementierung mit einem Modul

module Woerterbuch ( 
  WBuch, 
  leeresWBuch , 
  einfuegen , finde, loesche) 
where
  newtype WBuch k v = D [(k,v)] deriving Show 
  leeresWBuch :: Eq k => WBuch k v
  leeresWBuch = D []
  einfuegen :: (k, v) -> WBuch k v -> WBuch k v 
  einfuegen x (D l) = D (x:l)
  finde :: Ord k => k -> WBuch k v -> Maybe v 
  finde k (D l) = lookup k l  -- lookup aus Prelude
  loesche :: Eq k => k -> WBuch k v -> WBuch k v 
  loesche key (D l) = D [(k,v) | (k,v) <- l, k/=key]

Wörterbuch

• In der Exportliste des Moduls wird nur der Typ des Wörterbuchs WBuch angeben, nicht aber den Typkonstruktor D.
  • So ist es den Anwendern nicht möglich eigene Wörterbücher zu erstellen.

Effiziente Implementierung

Eine einfache Möglichkeit, den ADT Wörterbuch zu implementieren, besteht darin, nur eine Liste mit dem Tupel (Schlüssel k, Wert v) anzulegen.

• Das Einfügen ist trivial (O_einfuegen(N) = 1), aber das Finden und das Löschen der Elemente lässt sich nur in linearer Zeit realisieren. → O_lookup(N) = N.

• Das Suchen kann erfolgreich sein (Typ Maybe: Just v) oder ergebnislos (Nothing) und wird durch Iteration über die Wörterbuchliste durchgeführt:

lookup k ((x,v):tail) = if (x==k) Just v else lookup k tail
lookup k [] = Nothing

Wörterbuch

Hashtabellen

Ansatz

• Die Liste wird in einem linearen Array (Tabelle) gespeichert und der Schlüssel ist die Indexposition in der Tabelle.

Vorüberlegungen

• Listen erlauben eine Menge von Datensätzen so zu speichern, dass die Operationen Suchen, Einfügen und Entfernen unterstützt werden.

• Jeder Datensatz ist gekennzeichnet durch einen eindeutigen Schlüssel, z.B. eine Integer-Zahl oder eine Zeichenkette.

• Zu jedem Zeitpunkt ist lediglich eine (kleine) Teilmenge σ aller möglichen Schlüssel Σ gespeichert.

• Das bedeutet bei einer linearen Speicherung der Datensätze mit einer Tabelle, wo der Index der Tabelle/des Arrays gleich (bzw. die Speicheradresse proportional) dem Schlüssel ist, eine große Tabelle mit geringer Zeilenausnutzung.

Hashtabellen

• Vergleich linearer und verteilter Speicherung von Datensätzen in Arrays:
  • Linear: Der Schlüssel des Datensatzes ist der Index
  • Verteilt (Scattered): Der Index in der Tabelle muss durch eine Abbildungsfunktion (Hashfunktion) vom Schlüssel abgeleitet werden.

Hashtabellen

• Vorteil einer direkten Zuordnungsfunktion

liegt in der Suchzeit O(1)!

• Wünschenswert wäre eine indirekte Zuordnungsfunktion, die eine bessere Ausnutzung der Datentabelle ermöglicht:

• Die Funktion H nennt man Hash-Funktion. Die Datensätze werden in einer linearen Tabelle (Array) abgelegt, die man Hash-Tabelle nennt.

Hashtabellen

• Die Größe der Hash-Tabelle ist zweckmäßigerweise m < n=n_kmax

• Die Hash-Funktion ordnet jedem Schlüssel k einen Index der Tabelle (oder eine Speicheradresse) h(k) mit 1 ≤ h(k) ≤ m im Falle eines Indexes zu.

• I.A. ist σ eine sehr kleine Teilmenge von Σ. Z.B. gibt es 26*36⁷⁹ mögliche Schlüssel für eine Zeichenkette mit 80 Zeichen, die mit einem Buchstaben beginnt, und mit Buchstaben oder Ziffern fortgesetzt wird.

  • Beispiel: Symboltabelle eines Compilers.

• Die Hash-Funktion besitzt die Eigenschaft, dass zwei verschiedene Schlüssel k₁ und k₂ die gleiche Hash-Adresse besitzen können:

k₁ und k₂ heissen dann Synonyme. Ergibt sich direkt aus der Tatsache m < n und wird als Mehrdeutigkeit bzw. Adresskollision der Hash-Funktion bezeichnet.

• Die Adresskollision muss als Sonderfall getrennt behandelt werden!

Hashtabellen

• Eine gute Hash-Funktion sollte möglichst schnell berechenbar sein, und die zu speichernden Datensätze möglichst gleichmäßig, aber ohne erkennbare Struktur oder Ordnung auf den Speicherbereich verteilen, um Kollisionen zu minimieren.

• Problem: Die Schlüsselmenge σ={k_i} ist meistens nicht gleichmäßig verteilt.

• Z.B. bestehen Variablenamen in Programmen häufig aus 1-2 Zeichen mit den Buchstaben {x,y,z} und den Zahlen {1,2,..}.

• Ein Maß für Wahrscheinlichkeit der Kollision in einer Tabelle mit m Zellen und nach k Einfügungen ist:

• Annahme: Gleichverteilung der Schlüssel!

Hashtabellen

Hashfunktion

• Die einfachste Hashfunktion für numerische ganzzahlige Schlüssel ist die Division-mit-Rest Funktion (mod):

JavaScript

In JavaScript sind Arrays immer Hash-Tabellen → Und Objekte (Strukturen) sind ebenfalls Hash-Tabellen → Der Schlüssel ist immer eine Zeichenkette (auch bei numerischen Index)!

Hashtabellen

Beispiele

var a = [1,2,3,4]
var e1 = a[2];   -- == 3
var e2 = a["2"]; -- == 3!
a.counter = 4;
a["counter"]= 4;
var o = {x:1,y:2};
print(o.y-o.x)         -- 1
print(o["y"]-o["x"])   -- 1

Hashtabellen

Wörterbuch in JavaScript

function WBuch() {
  this.data={};
  this.n=0;
}
WBuch.prototype.finde = function (k) {
  return this.data[k];
}
WBuch.prototype.einfuegen = function (k,v) {
  this.data[k]=v; this.n++;
}
WBuch.prototype.loesche = function (k) {
  this.data[k]=undefined; this.n--;
}
function leeresWBUch() {
  return new WBuch();
}

Hashtabellen

Umgang mit Überläufern

1. Ein Eintrag in einer Hashtabelle ist eine lineare Liste. Die Überläufer werden in dieser Liste angeordnet.

   • Vorteil: Einfach zu implementieren
   • Nachteile: Suche in der Liste hat Laufzeitklasse O(n)! Listen sind dynamisch (Speichermanagement)

2. Die Überläufer werden in freien Zellen der Hashtabelle untergebracht:

   • Vorteil: Statische Tabelle
   • Nachteil: Sondierung erforderlich! Überläufer erhöhen wiederum Kollisionswahrscheinlichkeit!
   • Verfahren: Lineares und quadratisches Sondieren

Arrays

• Anders als Listen sind Arrays feste Blöcke im Speicher eines Computers.

• Analog zu den Listen lassen sich viele Elemente desselben Datentyps in einem Array speichern.

• Arrays lassen sich nicht vergrößern oder verkleinern, ohne sie neu anzulegen.

  • Daher muss zu Beginn bekannt sein, wie viele Elemente maximal gespeichert wer- den sollen.

• Dieser Nachteil führt dazu, dass Arrays in Haskell seltener zum Einsatz kommen als Listen.

• Vorteil gegenüber Listen: Die Zugriffszeit auf ein Array-Element ist immer konstant. Um auf das k-te Element zuzugreifen, müssen nicht die ersten k−1 Elemente entlanggelaufen werden, wie es bei einer verketteten Liste der Fall ist!

Arrays

Dynamische Arrays

• Für Hashtabellen werden veränderliche Arrays benötigt.

• Traditionell sind Arrays vor allem ein Zugeständnis an die Architektur der von Neumann-Rechner: Sie repräsentieren einen konsekutiven Speicherbereich, dessen Elemente sehr effizient und kompakt über Adressrechnung verarbeitbar sind.

• Ein Array ist ein i.A. monosortiger Produkttyp und besteht aus einer Anzahl N von Elementen die über einen abzählbaren Index selektiert werden können.

• Es gibt Schreib- und Leseoperationen auf Arrays bzw. deren selektierte Elemente:

  a = ARRAY (ia .. ib) typelem ([v0,..])
  write a index value
  x = read a index

Arrays

• Hat man ein Block- und Speichermodell, können Arrayoperationen und Elementzugriffe auf Blockoperationen abgebildet werden:

• Der Typ Array (a..b) α wird in einen Block der Länge b−a+1 konvertiert.

Arrays

• Die Array-Selektion v(i) wird auf die Blockselektion abgebildet, wobei ein Indexshift in das Intervall 0..n −1 vorgenommen wird.

  • Die Einhaltung der Indexgrenzen a ≤ i ≤ b ist Teil der Typprüfung, die vom Compiler generell eingebaut wird und deshalb hier nicht noch einmal angegeben werden muss.

• Der Array-Update wird entsprechend auf set abgebildet.

• Die Operation step kodiert die Richtung und Schrittweite, in der das Array verarbeitet werden soll

• Die Erzeugung eines Arrays über einen Ausdruck, also v = λ i • f (v, i), wird sequenziell über einen Iterator gelöst, der mit Hilfe der Operation step die Arrayelemente nacheinander mit den entsprechendenWerten von f (v, i) besetzt.

• Was wäre bei einem ‘rohen’ Speichermodell noch zu beachten?

• Funktional gibt es keine veränderlichen Daten!

Arrays

• Daher würde strikt funktional die Änderung eines Arrayelements die (virtuelle) Erzeugung eines neuen Arrays bedeuten:

FUN read: α Array → β → α
FUN write: α Array → β → α → α Array

• Auf semantischer und methodischer Ebene sind Arrays nichts anderes als spezielle Funktionen:

  • Arrays sind spezielle Funktionen. Sie haben die beiden folgenden Besonderheiten, von denen die erste semantisch ist, die zweite pragmatisch.
  • Der Definitionsbereich eines Arrays ist aus Intervallen der ganzen Zahlen gebildet. (Der Wertebereich ist beliebig.)
  • Arrays sind ‘eingefrorene’ Funktionen; d.h., sie liegen jeweils in einer tabellarischen Auflistung ihrer Werte vor. (Man kann das als eine Art genereller Memoization auffassen.)

Arrays

• Aber: Es gibt in Haskell auch ein Modul für veränderliche Arrays:

import Data.Array.IO
.. do ..
  a <- newArray (ia,ib) v0 
       :: IO (IOArray typindex typelem )
  writeArray a index value
  readArray a index

• Die Grenzen eines Arrays sind nicht wie in vielen anderen Sprachen auf den Datentyp Int beschränkt.

• Alle Typen aus der Typklasse Ix, insbesondere auch Tupel, können als Arraygrenzen verwendet werden.

• So können problemlos mehrdimensionale Arrays verwaltet werden, beispielsweise um Digitale Verarbeitung von Bildern zu ermöglichen.

Arrays

Statische Arrays

• Bei statischen Arrays können die Elemente nicht verändert werden.

• Arrays müssen in funktionalen Sprachen wie andere (symbolische) Variablen mit einem Wert initialisiert werden.

• Durch den Liste-Array Dualismus können statische Arrays auch aus Listen erzeugt werden:

import Data.Array.IArray
.. do ..
 a = (listArray (ia,ib) [..]) :: Array typindex typelem 
 a!index

• In Haskell kann auf ein Arrayelemente vereinfacht mittels des a!index Operators zugegriffen werden (nur lesend!)

Arrays

Beispiele in Haskell

Listen

• Eine Liste ist eine lineare Verkettung von Listenelementen (Daten).

• Ein Listenelement besteht dabei aus einem Verkettungs-, Schlüssel und Datenteil:

TYPE (α,β) LISTENELEMENT = { 
  connect:[(α,β) LISTENELEMENT], 
  key:β, 
  data:α 
} 

• Der Schlüssel ist optional assoziiert einen Datensatz (eindeutige oder mehrdeutige Assoziation)

• Listen unterstützen folgende wesentliche Operationen:

  • Einfügen eines Elements an einer bestimmten Position in der Liste
  • Löschen eines Elements an einer bestimmten Position in der Liste
  • Suchen eines Elements entweder anhand Position oder Schlüssel
  • Spezielle Operation: Einfügen/Löschen eines Elements am Kopf/Ende

Listen

• Listen können statisch mit Arrays und dynamisch durch Verkettung von Elementen implementiert werden.

• Es gibt dabei zwei Arten von Listen die sich durch die Art der Verkettung unterscheiden:

Einfach Verkettete Liste

Jedes Element besitzt eine Referenz (Link) zu dem nächsten rechten (oder linken) Nachbarn

Doppelt Verkettete Liste

Jedes Element besitzt zwei Referenzen zum jeweiligen linken und rechten Nachbarn

• Einfach verkettete Listen sind ein Kerndatentyp von Haskell und werden praktisch von allen funktionalen Programmiersprachen unterstützt.

Listen

Listen

Doppelt verkettete Listen in Haskell

• Annahme: Jeder Datensatz besitzt einen assoziierten Schlüssel

data DList a b = 
  Leaf | 
  Node { prev::(DList a b), key:: a, elt::b, next::(DList a b) } 
 
create = go Leaf
  where go _    []     = Leaf
    go prev ((key,val):xs) = current
      where current = Node prev key val next
        next    = go current xs
 
findRight _ Leaf = Nothing
findRight key (Node l k v r) = 
 if k == key then Just v 
 else findRight key r
 
findLeft _ Leaf = Nothing
findLeft key (Node l k v r) = 
 if k == key then Just v 
 else findLeft key l

Listen

Listen

• Bei einer einfach verketteten Liste muss immer das Kopfelement gespeichert werden, bei einer doppelt verketteten Listen können sowohl Kopf- als auch Endelement gespeichert werden

• Kopf- und Endelemente (Wurzelknoten) sind der Zugang zur Liste, z.B. beim Suchen

Laufzeiteigenschaften

• Laufzeit als Laufzeitklasse → Θ(x) → Größenordnung der groben Berechnungsschritte in Abhängigkeit von der Größe x der Datenstruktur

• Das Einfügen oder Löschen eines Elements am Kopf der Liste (und am Ende bei dopp. verk.) benötigt nur einen Schritt → Θ(1) → konstante Laufzeit unabhängig von n (Anzahl der Knoten)

• Das Suchen eines Elements benötigt bei beiden Listen maximal n Schritte → Θ(n)

• Das Einfügen oder Löschen eines Elements anhand eines Schlüssel innerhalb der Liste benötigt maximal (n-1) Schritte (Suche) → Θ(n)

Listen

• Bei der doppelt verketteten Liste ist aber Einfügen an beliebiger Stelle mit konstanter Laufzeit möglich wenn das Element an der entsprechenden Position bereits bekannt ist → Θ(1).
  • Bei der einfach verketteten Liste kostet aber das Einfügen immer Θ(n). Warum?

Weitere Listenoperationen

• Haskell bietet im Modul Data.List zwei weitere wichtige Operationen auf Listen an:

minimum [α] → α

Findet das kleinste Element einer Liste und gibt dieses als Ergebnis zurück (Wert, nicht Position!)

delete α → [α] → [α]

Löscht ein Element einer Liste. Der Wert des zu löschenden Elements muss angegeben werden, nicht die Position! Die modifizierte Liste wird zurück gegeben.

Sortieren von Listen

SelectionSort

• Der vermutlich einfachste Ansatz, eine Liste mit Elementen zu sortieren, ist

  • das kleinste Element aus der Liste zu entfernen,
  • es an die Ergebnisliste zu hängen und rekursiv fortzufahren
  • bis keine Elemente mehr übrig sind.

• Dieser Algorithmus wird als Selection Sort oder Sortieren durch Auswahl bezeichnet. Iterativ können wir den Algorithmus in etwa so angeben:

FOR i = 0 to n-1 DO
  FOR j=n-1 to i+1 DO 
    IF x[j-1] > x[j] THEN vertausche x[j-1] und x[j]

Sortieren von Listen

• In Haskell kann man unter Verwendung von minimum und delete die Sortierung rekursiv formulieren:

import Data.List
sSort :: (Ord a) => [a]->[a] 
sSort [] = [] 
sSort xs = m : sSort (delete m xs) 
  where m = minimum xs

• Laufzeitanalyse mittels Rekursion:

  • Das Finden des Minimums einer Liste ist in linearer Zeit zu schaffen.

  • Das Finden und damit auch das Löschen eines beliebigen Elements benötigt ebenfalls lineare Zeit.

  • T(0) = 1

  • T(n) = n + T(n-1)

  • ⇒ Θ_sSort(n²)

Sortieren von Listen

Sortieren von Listen

InsertionSort

• Ein weiterer Sortieralgorithmus ist das „Sortieren durch Einfügen“ oder kurz InsertionSort.

• Angenommen, eine Liste liegt bereits aufsteigend sortiert vor, dann ist das Einordnen eines neuen Elements einfach.

• Es wird solange von links beginnend überprüft, ob das aktuelle Element kleiner oder gleich dem Einzufügenden ist, bis die korrekte Position ermittelt ist.

• An diese Stelle wird das Element eingefügt und die Liste bleibt sortiert

Sortieren von Listen

• Die Sortierung mit InsertionSort beginnt mit einer leeren Liste und fügt mit der Funktion einfügen nacheinander alle Elemente aus der zu sortierenden Liste ein:

einfuegen :: Ord a => a -> [a]-> [a] 
einfuegen x [] = [x] 
einfuegen x (y:ys) 
  | x<=y = x:y:ys 
  | otherwise = y:(einfuegen x ys)
 
iSort :: Ord a => [a]-> [a] 
iSort [] = [] 
iSort (x:xs)= einfuegen x (iSort xs)

Sortieren von Listen

Sortieren von Listen

• Laufzeitanalyse:

  • Im schlechtesten Fall benötigt dieses Verfahren ebenfalls eine quadratische Laufzeit, da das Auffinden der richtigen Stelle zum Einfügen im schlechtesten Fall lineare Zeit benötigt und die Liste für die Rekursion nur um eins verkürzt wird.

  • Im besten Fall ist InsertionSort, anders als bei SelectionSort, allerdings sehr viel schneller.

  • Der best-case tritt ein, wenn die Startliste umgekehrt sortiert vorliegt. Dann ist die richtige Stelle zum Einfügen immer ganz vorn zu finden und das benötigt konstante Zeit. Es wird also n-mal ein konstanter Aufwand betrieben, so dass Θ(n) Operationen gebraucht werden.

Sortieren von Listen

QuickSort

• Der QuickSort-Algorithmus ist ein typisches Beispiel für Algorithmen die auf dem Teile-und-Herrsche-Prinzip basieren → Top-down Ansatz

• In jedem Schritt, beginnend mit der gesamten Liste, wird ein Element ausgewählt → Pivotelement

• Die Liste wird dann dort zweigeteilt.

  • In der linken Liste sind die Elemente enthalten, die kleiner oder gleich dem Pivotelement sind und
  • in der rechten die größeren Elemente.

• Das Pivotelement verbleibt dabei in der Mitte und hat seinen endgültigen Platz in der sortierten Liste bereits eingenommen.

Die Auswahl des Pivotelements ist zentral in diesem Algorithmus und kann auf verschiedene Weisen erfolgen. Z.B.: Immer Auswahl des ersten Elements einer Teilliste

Sortieren von Listen

Sortieren von Listen

• In Haskell lässt sich der QuickSort-Algorithmus durch die einfache automatische Erzeugung von Listen wieder rekursiv mit einigen wenigen Zeilen formulieren:

qSort :: Ord a => [a]-> [a] 
qSort [] = []
qSort (x:xs)= 
  qSort [y | y<-xs, y<=x]++[x]++ 
  qSort [y | y<-xs, y> x]

• Die Laufzeit hängt dabei stark davon ab, wie das Pivotelement gewählt wird. Im besten Fall wird die Liste in jedem Rekursionsschritt halbiert.

  • T(0)= 1

  • T(n)= n+2 T(n/2)

  • Im besten Fall erreicht man Θ(n log(n))

Sortieren von Listen

• Im schlechtesten Fall gehört das Pivotelement nicht in die Mitte der sortierten Liste, sondern an einen der Ränder.
• Dann benötigt man in jedem Rekursionsschritt weiterhin einen linearen Aufwand, aber die Größe des rekursiven Aufrufs wird nur um eins reduziert, genau wie bei Selection- und InsertionSort.
• Im schlechtesten Fall fällt die Laufzeit von QuickSort also auf Θ(n²)

• Aber: Parallelisierung durch Map-Reduce Partitionierung einfach möglich!!!
  • Es gibt keine tiefere Datenabhängigkiet zwischen den Teillisten und weiteren Sortierungen → geringer Kommunikationsaufwand!

Sortieren von Listen

MergeSort

• QuickSort ist ein effizientes Sortierverfahren, hat jedoch im schlechtesten Fall quadratische Laufzeit.

• MergeSort ist ein weiteres Sortierverfahren, das dem Teile-und-Herrsche-Prinzip folgt → aber Bottom-up Ansatz.

• Annahme: Es ist kostengünstig, aus zwei sortierten Listen eine neue sortierte Liste zu erzeugen.

  • Dazu werden nur die jeweils ersten Elemente der beiden sortierten Listen verglichen und das kleinere von beiden in die Ergebnisliste geschrieben.

• Beim MergeSort-Algorithmus werden zunächst einelementige Listen rekursiv erzeugt und diese sortierten Listen anschließend mit zusammengefasst, bis nur noch eine Liste vorhanden ist

Sortieren von Listen

Sortieren von Listen

• In Haskell lässt sich MergeSort wieder rekursiv definieren.
• Die Idee von MergeSort ist, die zu sortierende Liste zu halbieren, die beiden Hälften rekursiv zu sortieren und die sortierten Teile wieder zusammenzufügen:

merge [] ys = ys 
merge xs [] = xs 
merge (x:xs)(y:ys) 
  | x <= y = x:(merge xs (y:ys))
  | otherwise = y:(merge (x:xs) ys)
 
mSort :: Ord a => [a]-> [a] 
mSort [] = [] 
mSort [x]=[x] 
mSort xs = merge (mSort erste)(mSort zweite) 
  where 
  (erste, zweite) = splitAt haelfte xs 
  haelfte = div (length xs) 2

Sortieren von Listen

• Laufzeitanalyse:

  • Die Laufzeit der merge Funktion ist linear zu der Länge der beiden Listen.

  • Wenn die Listen die Längen m und n haben, ist die Laufzeit Θ(m+n).

  • Da bei diesem Verfahren die Listen garantiert halbiert werden und in einem Rekursionsschritt nur linearer Aufwand betrieben wird, ist die Laufzeit auf jeden Fall Θ(n log(n))

Stack

(Stapelspeicher / Kellerspeicher)

• Ein Stack ist eine lineare Liste (oder Array) mit zwei speziellen Operationen, die das Hinzufügen und Entfernen von Elementen in Last-In First-Out Reihenfolge ermöglicht:

push s el → s

Ein Element el wird auf dem Stapelspeicher als oberstes Element abgelegt (top)

pop s → (el,s)

Das oberste Element wird vom Stapelspeicher entfernt

• Stapelspeicher finden bei Funktionen und Funktionsaufrufen Anwendung

  • Auf dem Stapel werden bei einem Funktionsaufruf i.A. die Funktionsparameter abgelegt, der Rückgabewert der Funktion, und interne Informationen die die bei der Terminierung der Funktion erforderlich sind.

• Ein Stapelspeicher unterstützt keine Konkatenation!

Stack

Stack

• Stapelspeicher kann direkt mit Haskell Listen implementiert werden

• Laufzeit für Einfügen und Entfernen ist immer O(1)

data Stack a = S [a]
create () =  []
push (S s) el = el:s
pop S (el:tail) = (el,tail)

Warteschlange (Queue)

Warteschlange (Queue)

• Eine Warteschlange ist ebenfalls eine Liste mit speziellen Operationen die das Einfügen und Entfernen von Elementen in First-In First-Out Reihenfolge ermöglicht

enqueue el → q

Ein Element am Ende der Liste einfügen

dequeue q → (el,q)

Ein Element vom Anfang der Liste (Kopf) entfernen

• Als abstrakter Datentyp ist eine Warteschlange ein Containertyp Queue α, der mehrere Elemente des Typs α enthalten kann.

• Warteschlangen sind für viele bekannte Algorithmen wichtig.

• Als erste Idee für die Implementierung einer Warteschlange könnte der Datentyp Liste angedacht werden.

  • Der Test auf eine leere Liste und das Entfernen des ersten Elements funktionieren bei Listen schnell.
  • Um ein Element an eine Liste anzuhängen, benötigen wir allerdings eine Laufzeit von Θ(n)

Warteschlange (Queue)

class Queue a where
  -- Test auf leere Warteschlange 
  empty :: a b -> Bool
  -- Einreihen eines Objekts am Ende 
  enqueue :: b -> a b -> a b
  -- Entfernen des Kopfes 
  dequeue :: a b -> (b,a b)

• Alternativ können zwei Listen verwendet werden.
  • Eine Liste bildet dabei den Anfang einer Warteschlange ab und ermöglicht so eine effiziente Entfernung eines Elements.
  • Durch die zweite Liste wird das effiziente Anhängen eines Elements realisiert.

Warteschlange (Queue)

• Wenn ein Element aus der Warteschlange herausgenommen wird, kann es das letzte Element der ersten Liste sein.
  • Dann müssen die Elemente aus der zweiten Liste umgekehrt an die Stelle der ersten Liste geschrieben werden!

data Queue a = Q [a][a]
 
empty :: Queue a -> Bool 
empty (Q [] []) = True 
empty _ = False
 
create () = Q [] []
 
enqueue :: a -> Queue a -> Queue a 
enqueue a (Q x y)= Q x (a:y)
 
dequeue :: Queue a -> (a, Queue a) 
dequeue (Q [] y)     = (y1, Q ys []) 
  where (y1:ys) = reverse y
dequeue (Q [x] y)    = (x, Q (reverse y) [])
dequeue (Q (x:xs) y) = (x, Qxs y)

Warteschlange (Queue)

Warteschlange (Queue)

• Die Laufzeit der Zweilistenimplementirung ist nicht generell konstant, denn im schlechtesten Fall hat dequeue einen linearen Aufwand O(n), um die zweite Liste umzudrehen.

• Anschließend kann dequeue allerdings n-mal mit konstantem Aufwand aufgerufen werden.

  • Es scheint als würde der gelegentlich auftretende, höhere Aufwand damit ausgeglichen.

Amortisierte Laufzeitanalyse

• Da die Operationen enqueue und dequeue aber im Mittel gleich häufig verwendet werden ist eine armortisierte Laufzeitanalyse sinnvoll, d.h. die mittleren Kosten bei Verwendung der beiden Operationen

• Man kann die Laufzeit einer Sequenz der Länge n von enqueue und dequeue Funktionsaufrufen betrachten.

  • Wenn die Gesamtlaufzeit O(f(n)) ist, dann ist es sinnvoll, die amortisierte Laufzeit der einzelnen Aufrufe als O(f(n)/n) anzugeben.

Warteschlange (Queue)

Bankiermethode

Eine Möglichkeit die amortisierten Laufzeiten zu bestimmen, ist die so genannte Bankiermethode (banker’s method).

• Dabei werden den Operationen nicht nur die tatsächlichen Kosten zugewiesen, wie es bei der normalen Laufzeitanalyse gemacht wird.

• Es werden zusätzlich noch Kredite hinterlassen oder vorhandene Kredite konsumiert.

• Jeder enqueue Aufruf benötigt Laufzeit O(1) und hinterlässt einen Kredit in Höhe 1, was die armotisierten Kosten auf 2 erhöht!

• Ein dequeue Aufruf mit nicht leerer erster Liste benötigt nur O(1)

• Ein dequeue Aufruf mit leerer erster Liste erfordert reverse und benötigt O(1) um ein Element zu entfernen und O(m) um die Liste umzudrehen

• Die teure Operation verbraucht m Kredite!

• Die armortisierte Laufzeit der Warteschlange wäre dann O'(1)!!! Aber Datenstrukturen sind in Haskell persistent, d.h. unveränderlich, und in der Realität kann die armortisierte Laufzeit größer sein!

Warteschlange (Queue)

Lazy Evaluation

Lazy Evaluation: Ausdrücke werden nur bei Bedarf ausgewertet bzw. Operationen ausgeführt

• Hier: Kritisch, dass es bereits zu spät ist, die zweite Liste erst dann umzudrehen, wenn die erste Liste bereits leer ist

• Stattdessen muss dafür gesorgt werden, dass immer genügend Elemente vorhanden sind.

  • Dazu werden zwei Zähler eingeführt, die die Länge der beiden Listen beinhalten.
  • Wann immer die zweite Liste länger wird als die erste, drehen wird sie umgedreht und hinten an die erste Liste angehängt.

Warteschlange (Queue)

data Queue a = Q Int [a] Int [a]
 
empty :: Queue a -> Bool 
empty (Q 0 _ _ _)= True 
empty _ = False
 
queue n x m y 
  | n > m     = Q n x m y 
  | otherwise = Q (n+m) (x++reverse y) 0 []
 
enqueue :: a -> Queue a -> Queue a 
enqueue a (Q n x m y) = queue n x (m+1) (a:y)
 
dequeue :: Queue a -> (a, Queue a) 
dequeue (Q n (x:xs) my)=(x, queue (n-1) xs m y)

• Auch bei einem persistenten Gebrauch der Listen ist die amortisierte Laufzeit konstant!

Bäume

• Die Datenstruktur Baum liegt vielen Algorithmen zu Grunde.

• Ein Baum ist ein spezieller Graph (zyklenfrei)

• Bäume bestehen aus

  • Knoten (enthält Daten) und
  • Kanten (realisiert die Struktur).

• Der Startknoten wird als Wurzel bezeichnet.

• Daten können nur in den Endknoten (Blättern) enthalten sein → die Zwischenknoten dienen nur zum Auffinden der Daten

• In den Knoten und an den Kanten können bei Bedarf zusätzliche Informationen gespeichert werden.

• Alle kreisfreien Datenstrukturen, wie beispielsweise Listen, lassen sich durch Bäume repräsentieren.

Bäume

Bäume

Bäume

• Interessant sind schon wie bei den vorhergehenden Datenstrukturen das Einfügen und das Löschen von Elementen und deren Laufzeitkosten.

• Beide Operationen lassen sich auf das Zusammenfügen von Bäumen zurückführen.

• Wenn man ein Element in einen existierenden Baum einfügt, wird ein Baum mit einem Element zu einem neuen Baum zusammengeführt.

• Wenn ein Element gelöscht wird, dann erhält man zunächst viele Bäume die wieder miteinander sinnvoll zu einem neuen Baum verbunden werden müssen.

• Abstrakter Datentyp Baum:

data Baum a = 
   Nil
 | Knoten { key :: a, inhalt :: b, lT, rT :: (Baum a)}

Bäume

• Wichtiges Kriterium eines Baumes ist seine Höhe (die Anzahl der Ebenen):

height :: Baum -> Int 
height Nil =0 
height x = max (height (lT x)) (height (rT x)) + 1

• Nur ein balanzierter Baum hat die geringste Höhe

• Die größte Höhe entsteht beim Grenzfall lineare Liste!

• Bei vielen Anwendungen ist es wichtig, dass die Höhe des Baumes möglichst gering bleibt, dieser also bestmöglich balanciert ist.

• Suche eines Elements kostet beim balanzierten Binärbaum Θ(log n)!

  • Bei der Suche kann ein abzählbarer und eindeutiger Schlüssel verwendet werden
  • Ist der aktuelle Knoten nicht der gesuchte, wird im Binärbaum der linke Teilbaum durchsucht wenn key < key_i, ansonsten der rechte Teilbaum bei key > key_i

Bäume

search :: Baum -> a -> Maybe b 
search Nil _ = Nothing 
search x k 
  | (key x) == k = x 
  | (key x) < k = (lT x)
  | (key x) > k = (rT x) 

• Für ein Zusammenfügen von Bäumen kann die Speicherung der Anzahl der Teilknoten anzahl sinnvoll sein.

data Baum a = 
   Nil
 | Knoten { anzahl :: Int, key :: a, inhalt :: b, 
            lT, rT :: (Baum a)}

• Die Rekursionstiefe des Verschmelzens von Bäumen ist abhängig von der Tiefe des entstehenden Baums und umgekehrt.

Bäume

• Beim Zusammenfügen sollte möglichst gleich ein balanzierter Baume entstehen → bestenfalls mit Laufzeit Θ(log n)). Dazu wird der Parameter anzahl verwendet.

merge :: Baum a -> Baum a -> Baum a 
merge Nil x = x 
merge x Nil = x 
merge x y | 
 size x >= size y = x { 
   elems = size x + size y, 
   -- das kleine Kind rekursiv mergen 
   lT=(merge s y), 
   -- das größere Kind nicht anfassen 
   rT = b}
| otherwise = merge y x where 
  (s,b)= 
    if (size (lT x) <= size (rT x)) then (lT x, rT x) 
    else (rT x, lT x)

Bäume

Balancierung

• Nachträgliche Balancierung durch Kombination aus Rechts-Links Rotationen möglich

Graphen

Lost & Found

Laufzeiteigenschaften von Algorithmen

• Performanz von Algorithmen kann auf zwei Arten bestimmt werden:

  • Experimentell: Laufzeitmessung unter realen Bedingungen → Abhängig von Rechnerarchitektur und Eingabedaten (Monte Carlso Simulation erforederlich) → von Computer zu Computer unterschiedlich usw.
  • Analytisch: Abschätzunge der Anzahl der primitiven Operationen die ein Prozessor durchführen muss

• Was genau als primitive Operation festgelegt wird, ist im Allgemeinen nicht wichtig.

• Stattdessen geht es um die Abschätzung der Laufzeit in Abängigkeit von der Größe der Eingabedaten N → Problemgröße.

• Die Laufzeitanalyse ist wichtig, um möglichst effiziente Lösungen zu finden. Das ist trotz der immer schneller werdenden Computer sehr wichtig. Vergleichen

Laufzeiteigenschaften von Algorithmen

Vergleich der Laufzeitklassen

• Eine gute Laufzeit(klasse) ist wichtiger als ein schneller Computer!

Landau-Symbole

Obere Schranken O

Eine Funktion f ist eine asymptotische obere Schranke einer Funktion g, wenn es eine Stelle n₀ und eine Konstante c > 0 gibt, so dass für alle natürlichen Zahlen n>n₀ stets g(n) ≤ c · f(n) gilt.

Mit Quantorennotation kann man schreiben: ∃n₀, ∃c, ∀n>n₀ : g(n) ≤ c · f(n)

• Das bedeutet, dass ab dem Wert n₀ für alle folgenden n gilt: g(n) ist immer kleiner/ gleich c · f(n).

• Es gibt für ein g(n) eine sehr große Menge von Funktionen f(n), die diese Bedingung erfüllen.

  • Eine asymptotische oberen Schranke ist definiert durch die Menge O(f).

Landau-Symbole

Untere Schranken Ω

Im umgekehrten Fall kann man eine asymptotische unteren Schranke definieren. Man schreibt g ∈ Ω(f), wenn es eine Stelle n₀ und eine Konstante c > 0 gibt, so dass gilt:

g ∈ Ω(f) ⇔ ∃c, ∃n₀, ∀n ≥ n₀ : g(n) ≥ c · f(n)

Starke obere Schranken o

Die Definition ist ganz ähnlich, lediglich die Konstante c kann nun nicht mehr frei gewählt werden. Die Ungleichung muss für alle c gelten:

g ∈ o(f) ⇔ ∀c, ∃n₀, ∀n>n₀>0: g(n) ≤ c · f(n)

Asymptotisch gleichesWachstum Θ

Es gibt auch eine Notation, um auszudrücken, dass zwei Funktionen asymptotisch gleich schnellwachsen. Das ist genau dann der Fall, wenn sie sowohl obere als auch untere Schranke voneinander sind:

g ∈ O(f) ∧ g ∈ Ω(f) ⇔ g ∈ Θ(f)

Landau-Symbole

Umgang mit Schranken und Regeln

1. Multiplikation mit Konstanten: Für alle k >0 gilt: k · f(n) ∈ Θ(f(n))

2. Summen und Produkte. Es gilt:
   f₁(n) ∈ O(g₁(n)) ∧ f₂(n) ∈ O(g₂(n)) ⇒ f₁(n) + f₂(n) ∈ O(g₁(n)+g₂(n))

3. Potenzen. Größere Potenzen sind starke obere Schranken von kleineren Potenzen. Es gilt:
   a < b ⇒ n^a ∈ o(n^b)

4. Polynome. Es gilt:
   (n+a)^b ∈ Θ(n^b)

5. Logarithmen. Alle Logarithmen (mit einer Basis > 1) unterscheiden sich nur um eine Konstante, daher gilt:
   log_a n ∈ Θ(log_b n)

6. Logarithmen gegen Potenzen: Potenzen von Logarithmen wachsen langsamer als normale Potenzen. Es gilt:
   (log n)^a ∈ o(n^b)

Landau-Symbole

7. Potenzen gegen Exponentialfunktionen: Potenzen wachsen immer langsamer als Exponentialfunktionen. Es gilt:
   n^a ∈ o(bⁿ)

Landau-Symbole

Vergleich der Schranken

Laufzeiteitanalyse

Best, Worst und Average Case

• Bei der Analyse von Algorithmen wird zwischen verschiedenen Fällen unterschieden. So dauert z.B. die Suche in Listen unterschiedlich lange in Abhängikeit von der Position.

• Weiterhin kann Optimeirung wie Lazy Evaluation oder Memoization das tatsächliche Laufzeitverhalten (Klasse) nach unten beeinflussen

  • Die Funktion f n = [1..n] scheint Θ(n) viele Schritte zu benötigen. Wird sie im Kontext g n = head (f n), wird sie eventuell mit Θ(1) optimiert abgearbeitet, da nur das erste Element benötigt wird und die restliche Liste gar nicht erst produziert wird (Lazy Evaluation).

Laufzeiteitanalyse

• Man unterscheidet drei Fälle:

  • Best case. Das Element befindet sich gleich am Anfang.
  • Worst case. Im schlechtesten Fall steht es ganz am Ende und die ganze Liste muss durchlaufen werden, bevor es gefunden wird.
  • Average Case. Im Mittel müssen ungefähr die Hälfte der Elemente angesehen werden.

• Um eine Komplexitäts­klasse zu bezeichnen, gibt man immer die einfachste Funktion an, die geeignet ist, die jeweilige Komplexitäts­klasse zu repräsentieren. Tatsächlich handelt es sich bei O(2n² + 7n – 10) und O(n²) um dieselben Mengen, man wählt aber O(n²) als Bezeichnung.

• Analyse von Funktionen wird unter der Annahme einer strikten Auswertung erfolgen (keine Lazy Evaluation)

Laufzeiteitanalyse

Beispiel: Fakultätsfunktion

fakul 0 = 1 
fakul n = n * fakul (n-1)

• Der Rekursionsanker (Terminierungsausdruck Zeile 1) benötigt nur konstante Zeit, also Θ(1).

• Annahme: Multiplikationen und Subtraktionen sind primitive Operationen und benötigen konstante Zeit, also Θ(1)

• Die Laufzeit T(n) der Fakultätsfunktion als Rekursionsgleichung aufgeschreiben:

• Der Aufwand ist dann (n+1) · Θ(1) = Θ(n+1) ∈ Θ(n)

Laufzeiteitanalyse

Beispiel: Elemente in einer Liste finden

suche :: Eq a => a -> [a]-> Maybe a 
suche _ [] = Nothing 
suche a (x:xs) 
 | a == x = Just a 
 | otherwise = suche a xs