Einleitung

Deklarative Formen der deklarativen Programmierung

(= fortgeschrittene) • funktionale Programmierung: foldr (+) 0 [1,2,3]
Programmierung foldr f z l = case l of
Vorlesung [] -> z ; (x:xs) -> f x (foldr f z xs)
• logische Programmierung: append(A,B,[1,2,3]).
WS 09,10; SS 12–14, 16
append([],YS,YS).
append([X|XS],YS,[X|ZS]):-append(XS,YS,ZS).
Johannes Waldmann, HTWK Leipzig
• Constraint-Programmierung
17. Mai 2016 (set-logic QF_LIA) (set-option :produce-models true)
(declare-fun a () Int) (declare-fun b () Int)
(assert (and (>= a 5) (<= b 30) (= (+ a b) 20)))
(check-sat) (get-value (a b))
– Typeset by FoilTEX – – Typeset by FoilTEX – 1

Definition Softwaretechnische Vorteile

deklarativ : jedes (Teil-)Programm/Ausdruck hat einen Wert . . . der deklarativen Programmierung
(. . . und keine weitere (versteckte) Wirkung). • Beweisbarkeit: Rechnen mit Programmen wie in der
Werte können sein: Mathematik mit Termen
• “klassische” Daten (Zahlen, Listen, Bäume. . . )
• Sicherheit: es gibt keine Nebenwirkungen und Wirkungen
• Funktionen (Sinus, . . . ) sieht man bereits am Typ

• Aktionen (Datei schreiben, . . . ) • Wiederverwendbarkeit: durch Entwurfsmuster (=

Funktionen höherer Ordnung)

• Effizienz: durch Programmtransformationen im Compiler,

• Parallelisierbarkeit: durch Nebenwirkungsfreiheit

– Typeset by FoilTEX – 2 – Typeset by FoilTEX – 3

Beispiel Spezifikation/Test Beispiel Verifikation

import Test.SmallCheck app :: forall t . [t] -> [t] -> [t]
app x y = case x of
append :: forall t . [t] -> [t] -> [t] [] -> y
append x y = case x of h : t -> h : app t y
[] -> y Beweise
h : t -> h : append t y app x (app y z) == app (app x y) z
Beweismethode: Induktion nach x.
associative f =
\ x y z -> f x (f y z) == f (f x y) z • Induktionsanfang: x == [] . . .

• Induktionsschritt: x == h : t . . .
test1 = smallCheckI
(associative (append::[Int]->[Int]->[Int]))
Übung: Kommutativität (formulieren und testen)
– Typeset by FoilTEX – 4 – Typeset by FoilTEX – 5

Beispiel Parallelisierung (Haskell) Beispiel Parallelisierung (C#, PLINQ)

Klassische Implementierung von Mergesort • Die Anzahl der 1-Bits einer nichtnegativen Zahl:
sort :: Ord a => [a] -> [a]
Func<int,int>f =
sort [] = [] ; sort [x] = [x] x=>{int s=0; while(x>0){s+=x%2;x/=2;}return s;}
sort xs = let ( left,right ) = split xs 26−1
2X
sleft = sort left
• f (x) Enumerable.Range(0,1<<26).Select(f).Sum()
sright = sort right
x=0
in merge sleft sright
wird parallelisiert durch Annotationen: • automatische parallele Auswertung, Laufzeitvergleich:
sleft = sort left Time(()=>Enumerable.Range(0,1<<26).Select(f).Sum())
‘using‘ rpar ‘dot‘ spineList Time(()=>Enumerable.Range(0,1<<26).AsParallel()
sright = sort right ‘using‘ spineList .Select(f).Sum())

vgl. http://thread.gmane.org/gmane.comp.lang. vgl. Introduction to PLINQ https://msdn.microsoft.

haskell.parallel/181/focus=202 com/en-us/library/dd997425(v=vs.110).aspx
– Typeset by FoilTEX – 6 – Typeset by FoilTEX – 7
 Softwaretechnische Vorteile Deklarative Programmierung in der Lehre
. . . der statischen Typisierung • funktionale Programmierung: diese Vorlesung
The language in which you write profoundly affects the • logische Programmierung: in Angew. Künstl. Intell.
design of programs written in that language. • Constraint-Programmierung: als Master-Wahlfach
For example, in the OO world, many people use UML to Beziehungen zu weiteren LV: Voraussetzungen
sketch a design. In Haskell or ML, one writes type
• Bäume, Terme (Alg.+DS, Grundlagen Theor. Inf.)
signatures instead. Much of the initial design phase of a
• Logik (Grundlagen TI, Softwaretechnik)
functional program consists of writing type definitions.
Anwendungen:
Unlike UML, though, all this design is incorporated
in the final product, and is machine-checked • Softwarepraktikum
throughout. • weitere Sprachkonzepte in Prinzipien v.
Programmiersprachen
Simon Peyton Jones, in: Masterminds of Programing, 2009;
http://shop.oreilly.com/product/9780596515171.do
• Programmverifikation (vorw. f. imperative Programme)

– Typeset by FoilTEX – 8 – Typeset by FoilTEX – 9

Konzepte und Sprachen Gliederung der Vorlesung

Funktionale Programmierung ist ein Konzept. • Terme, Termersetzungssysteme algebraische
Realisierungen: Datentypen, Pattern Matching, Persistenz
• in prozeduralen Sprachen:
• Funktionen (polymorph, höherer Ordnung),
– Unterprogramme als Argumente (in Pascal) Lambda-Kalkül, Rekursionsmuster
– Funktionszeiger (in C)
• in OO-Sprachen: Befehlsobjekte • Typklassen zur Steuerung der Polymorphie
• Multi-Paradigmen-Sprachen: • Bedarfsauswertung, unendl. Datenstrukturen
– Lambda-Ausdrücke in C#, Scala, Clojure (Iterator-Muster)
• funktionale Programmiersprachen (LISP, ML, Haskell)
• weitere Entwurfsmuster
Die Erkenntnisse sind sprachunabhängig.
• Code-Qualität, Code-Smells, Refactoring
• A good programmer can write LISP in any language.
• Learn Haskell and become a better Java programmer.
– Typeset by FoilTEX – 10 – Typeset by FoilTEX – 11

Softwaretechnische Aspekte Organisation der LV

• algebraische Datentypen, Pattern Matching, Termersetzungssysteme • jede Woche eine Vorlesung, eine Übung
Scale: case class, Java: Entwurfsmuster Kompositum, • Hausaufgaben (teilw. autotool)
immutable objects, das Datenmodell von Git
https://autotool.imn.htwk-leipzig.de/shib/
• Funktionen (höherer Ordnung), Lambda-Kalkül, Rekursionsmuster cgi-bin/Super.cgi
Lambda-Ausdrücke in C#, Entwurfsmuster Besucher Identifizierung und Authentifizierung über Shibboleth-IDP
Codequalität, code smells, Refaktorisierung des HTWK-Rechenzentrums, wie bei OPAL
• Typklassen zur Steuerung der Polymorphie • Prüfungszulassung: regelmäßiges (d.h. innerhalb der
Interfaces in Java/C# , automatische Testfallgenerierung jeweiligen Deadline) und erfolgreiches (ingesamt ≥ 50%
der Pflichtaufgaben) Bearbeiten von Übungsaufgaben.
• Bedarfsauswertung, unendl. Datenstrukturen
Iteratoren, Ströme, LINQ • Prüfung: Klausur (ohne Hilfsmittel)

– Typeset by FoilTEX – 12 – Typeset by FoilTEX – 13

Literatur Übungen
• Skripte: • im Pool Z430, vgl. http://www.imn.htwk-leipzig.
– aktuelles Semester http: de/˜waldmann/etc/pool/
//www.imn.htwk-leipzig.de/˜waldmann/lehre.html
• Beispiele f. deklarative Programmierung
– vorige Semester http://www.imn.htwk-leipzig.de/
– funktional: Haskell mit ghci,
˜waldmann/lehre-alt.html
– logisch: Prolog mit swipl,
• Entwurfsmuster: http://www.imn.htwk-leipzig. – constraint: mit mathsat, z3
de/˜waldmann/draft/pub/hal4/emu/ • Haskell-Entwicklungswerkzeuge
• Maurice Naftalin und Phil Wadler: Java Generics and – (eclipsefp, leksah, . . . , http://xkcd.org/378/)
Collections, O’Reilly 2006 – API-Suchmaschine http://www.haskell.org/hoogle/
• Commercial Uses of Functional Programming
• http://haskell.org/ (Sprache, Werkzeuge,
http://www.syslog.cl.cam.ac.uk/2013/09/22/
Tutorials), http://book.realworldhaskell.org/
liveblogging-cufp-2013/

– Typeset by FoilTEX – 14 – Typeset by FoilTEX – 15

 Daten Beispiele: Signatur, Terme
• Signatur: Σ1 = {Z/0, S/1, f /2}
Wiederholung: Terme
• (Prädikatenlogik) Signatur Σ ist Menge von • Elemente von Term(Σ1):
Funktionssymbolen mit Stelligkeiten Z(), S(S(Z())), f (S(S(Z())), Z())
ein Term t in Signatur Σ ist
– Funktionssymbol f ∈ Σ der Stelligkeit k • Signatur: Σ2 = {E/0, A/1, B/1}
mit Argumenten (t1, . . . , tk ), die selbst Terme sind.
• Elemente von Term(Σ2): . . .
Term(Σ) = Menge der Terme über Signatur Σ
• (Graphentheorie) ein Term ist ein
gerichteter, geordneter, markierter Baum
• (Datenstrukturen)
– Funktionssymbol = Konstruktor, Term = Baum

– Typeset by FoilTEX – 16 – Typeset by FoilTEX – 17

Algebraische Datentypen Datentyp mit mehreren Konstruktoren

data Foo = Foo { bar :: Int, baz :: String } Beispiel (selbst definiert)
deriving Show data T = A { foo :: Int }
Bezeichnungen (benannte Notation) | B { bar :: String, baz :: Bool }
deriving Show
• data Foo ist Typname
Bespiele (in Prelude vordefiniert)
• Foo { .. } ist Konstruktor data Bool = False | True
• bar, baz sind Komponenten data Ordering = LT | EQ | GT
x :: Foo
x = Foo { bar = 3, baz = "hal" }
Bezeichnungen (positionelle Notation)
data Foo = Foo Int String
y = Foo 3 "bar"

– Typeset by FoilTEX – 18 – Typeset by FoilTEX – 19

Mehrsortige Signaturen Rekursive Datentypen

• (bisher) einsortige Signatur data Tree = Leaf {}
| Branch { left :: Tree
Abbildung von Funktionssymbol nach Stelligkeit , right :: Tree }
• (neu) mehrsortige Signatur Übung: Objekte dieses Typs erzeugen
(benannte und positionelle Notation der Konstruktoren)
– Menge von Sortensymbolen S = {S1, . . .}
– Abb. von F.-Symbol nach Typ
– Typ ist Element aus S ∗ × S
Folge der Argument-Sorten, Resultat-Sorte
Bsp.: S = {Z, B}, Σ = {0 7→ ([], Z), p 7→ ([Z, Z], Z),
e 7→ ([Z, Z], B), a 7→ ([B, B], B)}.
• Term(Σ): konkrete Beispiele, allgemeine Definition?

– Typeset by FoilTEX – 20 – Typeset by FoilTEX – 21

Daten mit Baum-Struktur Bezeichnungen für Teilterme

• mathematisches Modell: Term über Signatur • Position: Folge von natürlichen Zahlen
• programmiersprachliche Bezeichnung: algebraischer (bezeichnet einen Pfad von der Wurzel zu einem Knoten)
Datentyp (die Konstruktoren bilden eine Algebra) Beispiel: für t = S(f (S(S(Z())), Z()))
• praktische Anwendungen: ist [0, 1] eine Position in t.
– Formel-Bäume (in Aussagen- und Prädikatenlogik) • Pos(t) = die Menge der Positionen eines Terms t
– Suchbäume (in VL Algorithmen und Datenstrukturen, in Definition: wenn t = f (t1, . . . , tk ),
java.util.TreeSet<E>) dann Pos(t) = {[]} ∪ {[i − 1]+ +p | 1 ≤ i ≤ k ∧ p ∈ Pos(ti)}.
– DOM (Document Object Model) dabei bezeichnen:
https://www.w3.org/DOM/DOMTR
• [] die leere Folge,
– JSON (Javascript Object Notation) z.B. für AJAX
http://www.ecma-international.org/ • [i] die Folge der Länge 1 mit Element i,
publications/standards/Ecma-404.htm • ++ den Verkettungsoperator für Folgen

– Typeset by FoilTEX – 22 – Typeset by FoilTEX – 23

 Operationen mit (Teil)Termen Operationen mit Variablen in Termen
• t[p] = der Teilterm von t an Position p • Term(Σ, V ) = Menge der Terme über Signatur Σ mit
Variablen aus V
Beispiel: S(f (S(S(Z())), Z()))[0, 1] = . . .
Beispiel: Σ = {Z/0, S/1, f /2}, V = {y},
Definition (durch Induktion über die Länge von p): . . .
f (Z(), y) ∈ Term(Σ, V ).
• t[p := s] : wie t, aber mit Term s an Position p
• Substitution σ: partielle Abbildung V → Term(Σ)
Beispiel: S(f (S(S(Z())), Z()))[[0, 1] := S(Z)]x = . . . Beispiel: σ1 = {(y, S(Z()))}
Definition (durch Induktion über die Länge von p): . . .
• eine Substitution auf einen Term anwenden: tσ:
Intuition: wie t, aber statt v immer σ(v)
Beispiel: f (Z(), y)σ1 = f (Z(), S(Z()))
Definition durch Induktion über t
– Typeset by FoilTEX – 24 – Typeset by FoilTEX – 25

Termersetzungssysteme Termersetzungssysteme als Programme

• Daten = Terme (ohne Variablen) • →R beschreibt einen Schritt der Rechnung von R,
• transitive und reflexive Hülle →∗R
• Programm R = Menge von Regeln beschreibt Folge von Schritten.
Bsp: R = {(f (Z(), y), y), (f (S(x), y), S(f (x, y)))} • Resultat einer Rechnung ist Term in R-Normalform
(:= ohne →R-Nachfolger)
• Regel = Paar (l, r) von Termen mit Variablen
dieses Berechnungsmodell ist im allgemeinen
• Relation →R ist Menge aller Paare (t, t0) mit • nichtdeterministisch R1 = {C(x, y) → x, C(x, y) → y}
– es existiert (l, r) ∈ R (ein Term kann mehrere →R-Nachfolger haben,
– es existiert Position p in t ein Term kann mehrere Normalformen erreichen)
– es existiert Substitution σ : (Var(l) ∪ Var(r)) → Term(Σ) • nicht terminierend R2 = {p(x, y) → p(y, x)}
– so daß t[p] = lσ und t0 = t[p := rσ]. (es gibt eine unendliche Folge von →R-Schritten,
es kann Terme ohne Normalform geben)
– Typeset by FoilTEX – 26 – Typeset by FoilTEX – 27

Konstruktor-Systeme Übung Terme, TRS

Für TRS R über Signatur Σ: Symbol s ∈ Σ heißt √
• Geben Sie die Signatur des Terms a · a + b · b an.
• definiert, wenn ∃(l, r) ∈ R : l[] = s(. . . )
• Geben Sie ein Element t ∈ Term({f /1, g/3, c/0}) an mit
(das Symbol in der Wurzel ist s)
t[1] = c().
• sonst Konstruktor.
mit ghci:
Das TRS R heißt Konstruktor-TRS, falls:
• data T = F T | G T T T | C deriving Show
• definierte Symbole kommen links nur in den Wurzeln vor
erzeugen Sie o.g. Terme (durch Konstruktoraufrufe)
Übung: diese Eigenschaft formal spezifizieren
Die Größe eines Terms t ist definiert durch
Beispiele: R1 = {a(b(x)) → b(a(x))} über Σ1 = {a/1, b/1}, P
|f (t1, . . . , tk )| = 1 + ki=1 |ti|.
R2 = {f (f (x, y), z) → f (x, f (y, z)) über Σ2 = {f /2}: √
definierte Symbole? Konstruktoren? Konstruktor-System? • Bestimmen Sie | a · a + b · b|.
Funktionale Programme sind ähnlich zu Konstruktor-TRS. • Beweisen Sie ∀Σ : ∀t ∈ Term(Σ) : |t| = | Pos(t)|.
– Typeset by FoilTEX – 28 – Typeset by FoilTEX – 29

Vervollständigen Sie die Definition der Tiefe von Termen: Abkürzung für Anwendung von 0-stelligen Symbolen:
anstatt Z() schreibe Z.

depth(f ()) = 0 • Für R = {f (S(x), y) → f (x, S(y)), f (Z, y) → y}

k > 0 ⇒ depth(f (t1, . . . , tk )) = . . . bestimme alle R-Normalformen von f (S(Z), S(Z)).
√
• Bestimmen Sie depth( a · a + b · b) • für Rd = R ∪ {d(x) → f (x, x)}
bestimme alle Rd-Normalformen von d(d(S(Z))).
• Beweisen Sie ∀Σ : ∀t ∈ Term(Σ) : depth(t) < |t|.
Für die Signatur Σ = {Z/0, S/1, f /2}: • Bestimme die Signatur Σd von Rd.
• für welche Substitution σ gilt f (x, Z)σ = f (S(Z), Z)? Bestimme die Menge der Terme aus Term(Σd), die
Rd-Normalformen sind.
• für dieses σ: bestimmen Sie f (x, S(x))σ.
• für die Signatur {A/2, D/0}:
Notation für Termersetzungsregeln: anstatt (l, r) schreibe
l → r. definiere Terme t0 = D, ti+1 = A(ti, D).
– Typeset by FoilTEX – 30 – Typeset by FoilTEX – 31
 Zeichne t3. Bestimme |ti| . über Signatur {A/1, B/1, E/0}:

• für S = {A(A(D, x), y) → A(x, A(x, y))} bestimme Normalform von Ak (B(E))

bestimme S-Normalform(en), soweit existieren, der für k = 1, 2, 3, allgemein.

Terme t2, t3, t4. Zusatz: von ti allgemein.
Abkürzung für mehrfache Anwendung eines einstelligen
Symbols: A(A(A(A(x)))) = A4(x)
• für {A(B(x)) → B(A(x))}
über Signatur {A/1, B/1, E/0}:
bestimme Normalform von Ak (B k (E))
für k = 1, 2, 3, allgemein.

• für {A(B(x)) → B(B(A(x)))}

– Typeset by FoilTEX – 32 – Typeset by FoilTEX – 33

Programme Pattern Matching

data Tree = Leaf | Branch Tree Tree
Funktionale Programme size :: Tree -> Int
. . . sind spezielle Term-Ersetzungssysteme. Beispiel: size t = case t of { ... ; Branch l r -> ... }
Signatur: S einstellig, Z nullstellig, f zweistellig. • Syntax allgemein:
Ersetzungssystem {f (Z, y) → y, f (S(x0), y) → S(f (x0, y))}. case t of { <Muster> -> <Ausdruck> ; ... }
Startterm f (S(S(Z)), S(Z)). • <Muster> enthält Konstruktoren und Variablen,
entsprechendes funktionales Programm: entspricht linker Seite einer Term-Ersetzungs-Regel,
data N = Z | S N <Ausdruck> entspricht rechter Seite
f :: N -> N -> N • Def.: t paßt zum Muster l: es existiert σ mit lσ = t
f x y = case x of
{ Z -> y ; S x’ -> S (f x’ y) }
• dynamische Semantik: für das erste passende Muster
Aufruf: f (S (S Z)) (S Z) wird rσ ausgewertet
Auswertung = Folge von Ersetzungsschritten →∗R • statische Semantik: jedes <Muster> hat gleichen Typ
Resultat = Normalform (hat keine →R-Nachfolger) wie t, alle <Ausdruck> haben übereinstimmenden Typ.

– Typeset by FoilTEX – 34 – Typeset by FoilTEX – 35

Eigenschaften von Case-Ausdrücken data und case

ein case-Ausdruck heißt typisches Vorgehen beim Verarbeiten algebraischer Daten
vom Typ T:
• disjunkt, wenn die Muster nicht überlappen
• Für jeden Konstruktor des Datentyps
(es gibt keinen Term, der zu mehr als 1 Muster paßt)
data T = C1 ...
• vollständig, wenn die Muster den gesamten Datentyp | C2 ...
abdecken
• schreibe einen Zweig in der Fallunterscheidung
(es gibt keinen Term, der zu keinem Muster paßt)
Bespiele (für data N = F N N | S N | Z) f x = case x of
C1 ... -> ...
-- nicht disjunkt:
C2 ... -> ...
case t of { F (S x) y -> .. ; F x (S y) -> .. }
-- nicht vollständig: • Argumente der Konstruktoren sind Variablen ⇒
case t of { F x y -> .. ; Z -> .. } Case-Ausdruck ist disjunkt und vollständig.
– Typeset by FoilTEX – 36 – Typeset by FoilTEX – 37

Peano-Zahlen Pattern Matching in versch. Sprachen

data N = Z | S N • Scala: case classes http://docs.scala-lang.org/
tutorials/tour/case-classes.html
plus :: N -> N -> N
plus x y = case x of • C# (7): https:
Z -> y //github.com/dotnet/roslyn/blob/features/
S x’ -> S (plus x’ y) patterns/docs/features/patterns.md
Aufgaben:
• Javascript?
• implementiere Multiplikation, Potenz
Nicht verwechseln mit regular expression matching zur
• beweise die üblichen Eigenschaften (Addition, String-Verarbeitung. Es geht um algebraische (d.h.
Multiplikation sind assoziativ, kommutativ, besitzen baum-artige) Daten!
neutrales Element)

– Typeset by FoilTEX – 38 – Typeset by FoilTEX – 39

 Übung Pattern Matching, Programme 3. case False of { False -> F F }
4. case G (F C) C (F C) of { G x y z -> F z }
• Für die Deklarationen 5. case F C of { F (F x) -> False }
6. case F C of { F x -> False ; True -> False }
-- data Bool = False | True (aus Prelude) 7. case True of { False -> C ; True -> F C }
data T = F T | G T T T | C 8. case True of { False -> C ; False -> F C }
9. case C of { G x y z -> False; F x -> False; C ->
entscheide/bestimme für jeden der folgenden Ausdrücke:
– syntaktisch korrekt? • Operationen auf Wahrheitswerten:
– statisch korrekt?
– Resultat (dynamische Semantik) import qualified Prelude
– disjunkt? vollständig? data Bool = False | True deriving Prelude.Show
not :: Bool -> Bool -- Negation
1. case False of { True -> C } not x = case x of
2. case False of { C -> True } ... -> ...
– Typeset by FoilTEX – 40 – Typeset by FoilTEX – 41

... -> ... data List = Nil | Cons Bool List deriving Prelude.S

Syntax: wenn nach of kein { folgt:

and :: List -> Bool
implizite { ; } durch Abseitsregel (layout rule).
and l = case l of ...
• (&&) :: Bool -> Bool -> Bool
x && y = case ... of ... entsprechend or :: List -> Bool
• (Wdhlg.) welche Signatur beschreibt binäre Bäume
Syntax: Funktionsname
(jeder Knoten hat 2 oder 0 Kinder, die Bäume sind; es
– beginnt mit Buchstabe: steht vor Argumenten,
gibt keine Schlüssel)
– beginnt mit Zeichen: zwischen Argumenten (als
Operator) • geben Sie die dazu äquivalente data-Deklaration an:
data T = ...
Operator als Funktion: (&&) False True,
Funktion als Operator: True ‘f‘ False. • implementieren Sie dafür die Funktionen

• Listen von Wahrheitswerten: size :: T -> Prelude.Int

– Typeset by FoilTEX – 42 – Typeset by FoilTEX – 43

depth :: T -> Prelude.Int Polymorphie

benutze Prelude.+ (das ist Operator), Definition, Motivation
Prelude.min, Prelude.max
• Beispiel: binäre Bäume mit Schlüssel vom Typ e
• für Peano-Zahlen data N = Z | S N
data Tree e = Leaf
implementieren Sie plus, mal, min, max
| Branch (Tree e) e (Tree e)
Branch Leaf True Leaf :: Tree Bool
Branch Leaf 42 Leaf :: Tree Int
• Definition:
ein polymorpher Datentyp ist ein Typkonstruktor
(= eine Funktion, die Typen auf einen Typ abbildet)
• unterscheide: Tree ist der Typkonstruktor, Branch ist ein
Datenkonstruktor
– Typeset by FoilTEX – 44 – Typeset by FoilTEX – 45

Beispiele f. Typkonstruktoren (I) Beispiele f. Typkonstruktoren (II)

• Kreuzprodukt: • binäre Bäume
data Pair a b = Pair a b data Bin a = Leaf
• disjunkte Vereinigung: | Branch (Bin a) a (Bin a)

data Either a b = Left a | Right b • Listen

• data Maybe a = Nothing | Just a data List a = Nil

| Cons a (List a)
• Haskell-Notation für Produkte:
(1,True)::(Int,Bool) • Bäume

für 0, 2, 3, . . . Komponenten data Tree a = Node a (List (Tree a))

– Typeset by FoilTEX – 46 – Typeset by FoilTEX – 47

 Polymorphe Funktionen Bezeichnungen f. Polymorphie
Beispiele: data List e = Nil | Cons e (List e)
• Spiegeln einer Liste: • List ist ein Typkonstruktor
reverse :: forall e . List e -> List e • List e ist ein polymorpher Typ
• Verketten von Listen mit gleichem Elementtyp: (ein Typ-Ausdruck mit Typ-Variablen)
append :: forall e . List e -> List e • List Bool ist ein monomorpher Typ
-> List e (entsteht durch Instantiierung: Substitution der
Knotenreihenfolge eines Binärbaumes: Typ-Variablen durch Typen)
preorder :: forall e . Bin e -> List e • polymorphe Funktion:
reverse:: forall e . List e -> List e
Def: der Typ einer polymorphen Funktion beginnt mit
All-Quantoren für Typvariablen. monomorphe Funktion: xor:: List Bool -> Bool
Bsp: Datenkonstruktoren polymorpher Typen. polymorphe Konstante: Nil::forall e. List e
– Typeset by FoilTEX – 48 – Typeset by FoilTEX – 49

Operationen auf Listen (I) Operationen auf Listen (II)

data List a = Nil | Cons a (List a) Die vorige Implementierung von reverse ist (für einfach
verkettete Listen) nicht effizient.
• append xs ys = case xs of
Besser ist:
Nil ->
Cons x xs’ -> reverse xs = rev_app xs Nil
mit Spezifikation
• Übung: formuliere und beweise: append ist assoziativ. rev_app xs ys = append (reverse xs) ys
Übung: daraus die Implementierung von rev_app ableiten
• reverse xs = case xs of
rev_app xs ys = case xs of ...
Nil ->
Cons x xs’ ->

• beweise:
forall xs . reverse (reverse xs) == xs

– Typeset by FoilTEX – 50 – Typeset by FoilTEX – 51

Operationen auf Bäumen Übung Polymorphie

data List e = Nil | Cons e (List e) Geben Sie alle Elemente dieser Datentypen an:
data Bin e = Leaf | Branch (Bin e) e (Bin e)
• Maybe ()
Knotenreihenfolgen
• preorder :: forall e . Bin e -> List e • Maybe (Bool, Maybe ())
preorder t = case t of ...
• Either (Bool,Bool) (Maybe (Maybe Bool))
• entsprechend inorder, postorder Operationen auf Listen:
• und Rekonstruktionsaufgaben • append, reverse, rev app
Adressierug von Knoten (False = links, True = rechts) Operationen auf Bäumen:
• get :: Tree e -> List Bool -> Maybe e • preorder, inorder, postorder, (Rekonstruktion)

• positions :: Tree e -> List (List Bool) • get, (positions)

– Typeset by FoilTEX – 52 – Typeset by FoilTEX – 53

Kochrezept: Objektkonstruktion y = Pair p q mit p :: Bool, q :: ()

Aufgabe (Bsp): • der Typ Bool hat Konstruktoren False | True, wähle
x :: Either (Maybe ()) (Pair Bool ()) p = False. der Typ () hat Konstruktor (), also q=()
Lösung (Bsp):
Insgesamt x = Right y = Right (Pair False ())
• der Typ Either a b hat Konstruktoren Vorgehen (allgemein)
Left a | Right b. Wähle Right b.
• bestimme den Typkonstruktor
Die Substitution für die Typvariablen ist
a = Maybe (), b = Pair Bool (). • bestimme die Substitution für die Typvariablen

x = Right y mit y :: Pair Bool () • wähle einen Datenkonstruktor

• der Typ Pair a b hat Konstruktor Pair a b. • bestimme Anzahl und Typ seiner Argumente

die Substitution für diese Typvariablen ist • wähle Werte für diese Argumente nach diesem
a = Bool, b = (). Vorgehen.
– Typeset by FoilTEX – 54 – Typeset by FoilTEX – 55
 Kochrezept: Typ-Bestimmung Lösung: ist gleich dem Typ der zugehörigen
Diskriminante p
Aufgabe (Bsp.) bestimme Typ von x (erstes Arg. von get):
• bestimme das Muster, durch das p deklariert wird
at :: Position -> Tree a -> Maybe a
at p t = case t of Lösung: at p t =
Node f ts -> case p of • bestimme den Typ von p
Nil -> Just f Lösung: durch Vergleich mit Typdeklaration von at (p ist
Cons x p’ -> case get x ts of das erste Argument) p :: Position, also
Nothing -> Nothing Cons x p’ :: Position = List N, also x :: N.
Just t’ -> at p’ t’ Vorgehen zur Typbestimmung eines Namens:
Lösung:
• finde die Deklaration (Muster einer Fallunterscheidung
oder einer Funktionsdefinition)
• bestimme das Muster, durch welches x deklariert wird.
Lösung: Cons x p’ -> • bestimme den Typ des Musters (Fallunterscheidung: Typ
• bestimme den Typ diese Musters der Diskriminante, Funktion: deklarierter Typ)
– Typeset by FoilTEX – 56 – Typeset by FoilTEX – 57

Statische Typisierung und Polymorphie Bsp. für Programm ohne statischen Typ (Javascript)
Def: dynamische Typisierung: function f (x) {
if (x>0) { return function () { return 42; } }
• die Daten (zur Laufzeit des Programms, im
else { return "foobar"; } }
Hauptspeicher) haben einen Typ
Dann: Auswertung von f(1)() ergibt 42, Auswertung von
Def: statische Typisierung: f(0)() ergibt Laufzeit-Typfehler.
• Bezeichner, Ausdrücke (im Quelltext) haben einen Type entsprechendes Haskell-Programm ist statisch fehlerhaft
(zur Übersetzungszeit bestimmt). f x = case x > 0 of
True -> \ () -> 42
• für jede Ausführung des Programms gilt: der statische False -> "foobar"
Typ eines Ausdrucks ist gleich dem dynamischen Typ
seines Wertes

– Typeset by FoilTEX – 58 – Typeset by FoilTEX – 59

Nutzen der statischen Typisierung: Von der Spezifikation zur Implementierung (I)
• beim Programmieren: Entwurfsfehler werden zu Bsp: Addition von Peano-Zahlen data N = Z | S N
Typfehlern, diese werden zur Entwurfszeit automatisch plus :: N -> N -> N
erkannt ⇒ früher erkannte Fehler lassen sich leichter aus der Typdeklaration wird abgeleitet:
beheben plus x y = case x of
Z ->
• beim Ausführen: es gibt keine Lauzeit-Typfehler ⇒ keine
S x’ ->
Typprüfung zur Laufzeit nötig, effiziente Ausführung
erster Zweig: plus Z y = 0 + y = y
Nutzen der Polymorphie: zweiter Zweig : plus (S x’) y = (1 + x’) + y =
• Flexibilität, nachnutzbarer Code, z.B. Anwender einer mit Assoziativität von + gilt
Collection-Bibliothek legt Element-Typ fest (Entwickler ... = 1 + (x’ + y) = S (plus x’ y)
der Bibliothek kennt den Element-Typ nicht) Bsp. (Ü): Multiplikation. Hinweis: benutze Distributivgesetz.

• gleichzeitig bleibt statische Typsicherheit erhalten

– Typeset by FoilTEX – 60 – Typeset by FoilTEX – 61

Von der Spezifikation zur Implementierung (II) • substitutiere xs = Cons x1 Nil, erhalte
Bsp: homogene Listen
maximum (append (Cons x1 Nil) ys)
data List a = Nil | Cons a (List a)
= maximum (Cons x1 ys)
Aufgabe: implementiere maximum :: List N -> N
= max (maximum (Cons x1 Nil)) (maximum ys)
Spezifikation: = max x1 (maximum ys)
maximum (Cons x1 Nil) = x1
maximum (append xs ys) = max (maximum xs) (maximum Damit kann
ys) der aus dem Typ abgeleitete Quelltext
maximum :: List N -> N
• substitutiere xs = Nil, erhalte
maximum xs = case xs of
maximum (append Nil ys) = maximum ys Nil ->
= max (maximum Nil) (maximum ys) Cons x xs’ ->
ergänzt werden.
d.h. maximum Nil sollte das neutrale Element für max Vorsicht: für min, minimum funktioniert das nicht so, denn
(auf natürlichen Zahlen) sein, also 0 (geschrieben Z). min hat für N kein neutrales Element.
– Typeset by FoilTEX – 62 – Typeset by FoilTEX – 63
 Unveränderliche Objekte Beispiel: Einfügen in Baum
• destruktiv:
Überblick
interface Tree<K> { void insert (K key); }
• alle Attribute aller Objekte sind unveränderlich (final)
Tree<String> t = ... ;
• anstatt Objekt zu ändern, konstruiert man ein neues
t.insert ("foo");
Eigenschaften des Programmierstils:
• persistent (Java):
• vereinfacht Formulierung und Beweis von
Objekteigenschaften interface Tree<K> { Tree<K> insert (K key); }
• parallelisierbar (keine updates, keine data races) Tree<String> t = ... ;
Tree<String> u = t.insert ("foo");
http://fpcomplete.com/
the-downfall-of-imperative-programming/ • persistent (Haskell):
• Persistenz (Verfügbarkeit früherer Versionen)
insert :: Tree k -> k -> Tree k
• Belastung des Garbage Collectors (. . . dafür ist er da)
– Typeset by FoilTEX – 64 – Typeset by FoilTEX – 65

Beispiel: (unbalancierter) Suchbaum Beispiel: Sortieren mit Suchbäumen

data Tree k = Leaf data Tree k = Leaf
| Branch (Tree k) k (Tree k) | Branch (Tree k) k (Tree k)
insert :: Ord k => k -> Tree k -> Tree k
insert k t = case t of ... insert :: Ord k => k -> Tree k -> Tree k
Diskussion:
build :: Ord k => [k] -> Tree k
• Ord k entspricht K implements Comparable<K>,
build = foldr ... ...
genaueres später (Haskell-Typklassen)
sort :: Ord k => [k] -> [k]
• wie teuer ist die Persistenz? sort xs = ... ( ... xs )
(wieviel Müll entsteht bei einem insert?)

– Typeset by FoilTEX – 66 – Typeset by FoilTEX – 67

Persistente Objekte in Git Objekt-Versionierung in Git

http://git-scm.com/ • Objekt-Typen:
• Distributed development. – Datei (blob),
– Verzeichnis (tree), mit Verweisen auf blobs und trees
• Strong support for non-linear development. – Commit, mit Verweisen auf tree u. commits (Vorgänger)
(Branching and merging are fast and easy.) git cat-file -p <hash>
• Objekte sind unveränderlich und durch SHA1-Hash (160
• Efficient handling of large projects. bit = 40 Hex-Zeichen) identifiziert
(z. B. Linux-Kernel, http://kernel.org/ ) • statt Überschreiben: neue Objekte anlegen
• jeder Zustand ist durch Commit-Hash (weltweit) eindeutig
• Toolkit design. beschrieben und kann wiederhergestellt werden
• Cryptographic authentication of history. Quelltexte zur Vorlesung: https://gitlab.imn.
htwk-leipzig.de/waldmann/fop-ss16
– Typeset by FoilTEX – 68 – Typeset by FoilTEX – 69

Funktionen Der Lambda-Kalkül

. . . als weiteres Berechnungsmodell,
Funktionen als Daten (vgl. Termersetzungssysteme, Turingmaschine,
bisher: Random-Access-Maschine)
f :: Int -> Int Syntax: die Menge der Lambda-Terme Λ ist
f x = 2 * x + 5
• jede Variable ist ein Term: v ∈ V ⇒ v ∈ Λ
äquivalent: Lambda-Ausdruck
f = \ x -> 2 * x + 5 • Funktionsanwendung (Applikation):
Lambda-Kalkül: Alonzo Church 1936, Henk Barendregt F ∈ Λ, A ∈ Λ ⇒ (F A) ∈ Λ
198*, . . . • Funktionsdefinition (Abstraktion):
Funktionsanwendung:
(\ x -> B) A = B [x := A] v ∈ V, B ∈ Λ ⇒ (λv.B) ∈ Λ
ist nur erlaubt, falls keine in A freie Variable durch ein Semantik: eine Relation →β auf Λ
Lambda in B gebunden wird. (vgl. →R für Termersetzungssystem R)
– Typeset by FoilTEX – 70 – Typeset by FoilTEX – 71
 Freie und gebundene Variablen(vorkommen) Semantik des Lambda-Kalküls: Reduktion →β
• Das Vorkommen von v ∈ V an Position p in Term t heißt Relation →β auf Λ (ein Reduktionsschritt)
frei, wenn darüber kein λv. . . . steht“ Es gilt t →β t0, falls
”
• ∃p ∈ Pos(t), so daß
• Def. fvar(t) = Menge der in t frei vorkommenden
Variablen (definiere durch strukturelle Induktion) • t[p] = (λx.B)A mit bvar(B) ∩ fvar(A) = ∅
• t0 = t[p := B[x := A]]
• Eine Variable x heißt in A gebunden, falls A einen
Teilausdruck λx.B enthält. dabei bezeichnet B[x := A] ein Kopie von B, bei der
jedes freie Vorkommen von x durch A ersetzt ist
• Def. bvar(t) = Menge der in t gebundenen Variablen
Ein (Teil-)Ausdruck der Form (λx.B)A heißt Redex.
Bsp: fvar(x(λx.λy.x)) = {x}, bvar(x(λx.λy.x)) = {x, y}, (Dort kann weitergerechnet werden.)
Ein Term ohne Redex heißt Normalform.
(Normalformen sind Resultate von Rechnungen.)

– Typeset by FoilTEX – 72 – Typeset by FoilTEX – 73

Semantik . . . : gebundene Umbenennung →α Umbenennung von lokalen Variablen

int x = 3;
• Relation →α auf Λ, beschreibt gebundene Umbenennung int f(int y) { return x + y; }
einer lokalen Variablen. int g(int x) { return (x + f(8)); }
• Beispiel λx.f xz →α λy.f yz. // g(5) => 16
(f und z sind frei, können nicht umbenannt werden) Darf f(8) ersetzt werden durch f [y := 8] ? - Nein:
int x = 3;
• Definition t →α t0: int g(int x) { return (x + (x+8)); }
– ∃p ∈ Pos(t), so daß t[p] = (λx.B) // g(5) => 18
–y∈ / bvar(B) ∪ fvar(B) Das freie x in (x + y) wird fälschlich gebunden.
– t0 = t[p := λy.B[x := y]] Lösung: lokal umbenennen
• wird angewendet, um bvar(B) ∩ fvar(A) = ∅ in Regel für int g(int z) { return (z + f(8)); }
→β zu erfüllen. dann ist Ersetzung erlaubt
int x = 3;
Bsp: betrachte den unterstrichenen Redex in int g(int z) { return (z + (x+8)); }
(λx.((λf.(λx.(x + f 8)))(λy.(x + y))))3 // g(5) => 16

– Typeset by FoilTEX – 74 – Typeset by FoilTEX – 75

Lambda-Terme: verkürzte Notation Ein- und mehrstellige Funktionen

• Applikation ist links-assoziativ, Klammern weglassen: eine einstellige Funktion zweiter Ordnung:
f = \ x -> ( \ y -> ( x*x + y*y ) )
Anwendung dieser Funktion:
(. . . ((F A1)A2) . . . An) ∼ F A1A2 . . . An
(f 3) 4 = ...
Beispiel: ((xz)(yz)) ∼ xz(yz) Kurzschreibweisen (Klammern weglassen):
Wirkt auch hinter dem Punkt: f = \ x y -> x * x + y * y ; f 3 4
(λx.xx) bedeutet (λx.(xx)) — und nicht ((λx.x)x) Übung:
gegeben t = \ f x -> f (f x)
• geschachtelte Abstraktionen unter ein Lambda schreiben:
bestimme t succ 0, t t succ 0,
t t t succ 0, t t t t succ 0, ...
(λx1.(λx2. . . . (λxn.B) . . . )) ∼ λx1x2 . . . xn.B
Beispiel: λx.λy.λz.B ∼ λxyz.B

– Typeset by FoilTEX – 76 – Typeset by FoilTEX – 77

Typen Beispiel für Typ-Bestimmung

für nicht polymorphe Typen: tatsächlicher Argumenttyp Aufgabe: bestimme den allgemeinsten Typ von λf x.f (f x)
muß mit deklariertem Argumenttyp übereinstimmen:
• Ansatz mit Typvariablen f :: t1, x :: t2
wenn f :: A → B und x :: A, dann (f x) :: B.
• betrachte (f x): der Typ von f muß ein Funktionstyp sein,
bei polymorphen Typen können der Typ von f :: A → B also t1 = (t11 → t12) mit neuen Variablen t11, t12.
und der Typ von x :: A0 Typvariablen enthalten. Dann gilt t11 = t2 und (f x) :: t12.
Beispiel: λx.x :: ∀t.t → t. • betrachte f (f x). Wir haben f :: t11 → t12 und (f x) :: t12,
Dann müssen A und A0 nicht übereinstimmen, sondern nur also folgt t11 = t12. Dann f (f x) :: t12.
unifizierbar sein (eine gemeinsame Instanz besitzen). • betrachte λx.f (f x).
Beispiel: (λx.x)True Aus x :: t12 und f (f x) :: t12 folgt λx.f (f x) :: t12 → t12.
benutze Typ-Substitution σ = {(t, Bool)}. • betrachte λf.(λx.f (f x)).
Bestimme allgemeinsten Typ von t = λf x.f (f x)), von (tt). Aus f :: t12 → t12 und λx.f (f x) :: t12 → t12
folgt λf x.f (f x) :: (t12 → t12) → (t12 → t12)

– Typeset by FoilTEX – 78 – Typeset by FoilTEX – 79

 Verkürzte Notation für Typen Lambda-Ausdrücke in C#
• Der Typ-Pfeil ist rechts-assoziativ : • Beispiel (Fkt. 1. Ordnung)
T1 → T2 → · · · → Tn → T bedeutet Func<int,int> f = (int x) => x*x;
(T1 → (T2 → · · · → (Tn → T ) · · · )) f (7);
• Übung (Fkt. 2. Ordnung) — ergänze alle Typen:
• das paßt zu den Abkürzungen für mehrstellige
??? t = (??? g) => (??? x) => g (g (x));
Funktionen:
t (f)(3);
λ(x :: T1).λ(x :: T2).(B :: T ) • Anwendungen bei Streams, später mehr
hat den Typ (T1 → (T2 → B)), (new int[]{3,1,4,1,5,9}).Select(x => x * 2);
(new int[]{3,1,4,1,5,9}).Where(x => x > 3);
mit o.g. Abkürzung T1 → T2 → T .
• Übung: Diskutiere statische/dynamische Semantik von
(new int[]{3,1,4,1,5,9}).Select(x => x > 3);
(new int[]{3,1,4,1,5,9}).Where(x => x * 2);

– Typeset by FoilTEX – 80 – Typeset by FoilTEX – 81

Lambda-Ausdrücke in Java(8) Lambda-Ausdrücke in Javascript

funktionales Interface (FI): hat genau eine Methode $ node
Lambda-Ausdruck ( burger arrow“) erzeugt Objekt einer
”
anonymen Klasse, die FI implementiert. > var f = function (x){return x+3;}
interface I { int foo (int x); } undefined
I f = (x)-> x+1;
System.out.println (f.foo(8)); > f(4)
vordefinierte FIs: 7
import java.util.function.*;

Function<Integer,Integer> g = (x)-> x*2;

System.out.println (g.apply(8));
Predicate<Integer> p = (x)-> x > 3;
if (p.test(4)) { System.out.println ("foo"); }
– Typeset by FoilTEX – 82 – Typeset by FoilTEX – 83

Beispiele Fkt. höherer Ord. Übung Lambda-Kalkül

• Haskell-Notation für Listen: • Wiederholung: konkrete Syntax, abstrakte Syntax,
data List a = Nil | Cons a (List a) Semantik
data [a] = [] | a : [a]
• Verarbeitung von Listen: • S = λxyz.xz(yz), K = λab.a, Normalform von SKKc
filter :: (a -> Bool) -> [a] -> [a] • (mit data N=Z|S N) bestimme Normalform von ttSZ
takeWhile :: (a -> Bool) -> [a] -> [a] für t = λf x.f (f x),
partition :: (a -> Bool) -> [a] -> ([a],[a])
• Vergleichen, Ordnen: • definiere Λ als algebraischen Datentyp data L = ...
nubBy :: (a -> a -> Bool) -> [a] -> [a] (3 Konstruktoren)
data Ordering = LT | EQ | GT implementiere size :: L -> Int,
minimumBy depth :: L -> Int.
:: (a -> a -> Ordering) -> [a] -> a
implementiere bvar :: L -> S.Set String,
– Typeset by FoilTEX – 84 – Typeset by FoilTEX – 85

fvar :: L -> S.Set String, Übung Fkt. höherer Ordnung

siehe Folie mit Definitionen und dort angegebene
• Typisierung, Beispiele in Haskell, C#, Java, Javascript
Testfälle
benutze import qualified Data.Set as S, compose ::
API-Dokumentation: https://hackage.haskell. compose = \ f g -> \ x -> f (g x)
org/package/containers/docs/Data-Set.html
• Implementierung von takeWhile, dropWhile
• autotool-Aufgaben Lambda-Kalkül

– Typeset by FoilTEX – 86 – Typeset by FoilTEX – 87

 Rekursionsmuster Rekursion über Bäume (Schema)
f :: Tree a -> b
Rekursion über Bäume (Beispiele) f t = case t of
data Tree a = Leaf Leaf -> ...
| Branch (Tree a) a (Tree a) Branch l k r -> ... (f l) k (f r)
summe :: Tree Int -> Int dieses Schema ist eine Funktion höherer Ordnung:
summe t = case t of fold :: ( ... ) -> ( ... ) -> ( Tree a -> b )
Leaf -> 0 fold leaf branch = \ t -> case t of
Branch l k r -> summe l + k + summe r Leaf -> leaf
preorder :: Tree a -> List a Branch l k r ->
preorder t = case t of branch (fold leaf branch l)
Leaf -> Nil k (fold leaf branch r)
Branch l k r -> summe = fold 0 ( \ l k r -> l + k + r )
Cons k (append (preorder l) (preorder r))

– Typeset by FoilTEX – 88 – Typeset by FoilTEX – 89

Rekursion über Listen Rekursionsmuster (Prinzip)

and :: List Bool -> Bool ein Rekursionsmuster anwenden = jeden Konstruktor
and xs = case xs of durch eine passende Funktion ersetzen.
Nil -> True ; Cons x xs’ -> x && and xs’ data List a = Nil | Cons a (List a)
length :: List a -> N fold ( nil :: b ) ( cons :: a -> b -> b )
length xs = case xs of :: List a -> b
Nil -> Z ; Cons x xs’ -> S (length xs’) Rekursionsmuster instantiieren = (Konstruktor-)Symbole
interpretieren (durch Funktionen) = eine Algebra angeben.
fold :: b -> ( a -> b -> b ) -> List a -> b length = fold Z ( \ _ l -> S l )
fold nil cons xs = case xs of reverse = fold Nil ( \ x ys -> )
Nil -> nil
Cons x xs’ -> cons x ( fold nil cons xs’ )
and = fold True (&&)
length = fold Z ( \ x y -> S y)

– Typeset by FoilTEX – 90 – Typeset by FoilTEX – 91

Rekursionsmuster (Merksätze) Rekursion über Listen (Übung)

aus dem Prinzip ein Rekursionsmuster anwenden = jeden das vordefinierte Rekursionsschema über Listen ist:
Konstruktor durch eine passende Funktion ersetzen folgt: foldr :: (a -> b -> b) -> b -> ([a] -> b)
• Anzahl der Muster-Argumente = Anzahl der
Konstruktoren (plus eins für das Datenargument) length = foldr ( \ x y -> 1 + y ) 0
Beachte:
• Stelligkeit eines Muster-Argumentes = Stelligkeit des
• Argument-Reihenfolge (erst cons, dann nil)
entsprechenden Konstruktors
• foldr nicht mit foldl verwechseln (foldr ist das richtige“)
• Rekursion im Typ ⇒ Rekursion im Muster ”
(Bsp: zweites Argument von Cons) Aufgaben:
• append, reverse, concat, inits, tails
• zu jedem rekursiven Datentyp gibt es genau ein mit foldr (d. h., ohne Rekursion)
passendes Rekursionsmuster

– Typeset by FoilTEX – 92 – Typeset by FoilTEX – 93

Weitere Beispiele für Folds Rekursionsmuster (Peano-Zahlen)

data Tree a = Leaf a | Branch (Tree a) (Tree a)
data N = Z | S N

fold :: ... fold :: ...

fold z s n = case n of
• Anzahl der Blätter
Z ->
• Anzahl der Verzweigungsknoten S n’ ->

• Summe der Schlüssel plus = fold ...

times = fold ...
• die Tiefe des Baumes

• der größte Schlüssel

– Typeset by FoilTEX – 94 – Typeset by FoilTEX – 95

 Übung Rekursionsmuster Hinweis: als Projektion auf die erste Komponente eines
fold, das Paar von Bool (ist AVL-Baum) und Int
• Rekursionsmuster foldr für Listen benutzen (filter, (Höhe) berechnet.
takeWhile, append, reverse, concat, inits, tails) – Baum (Tree Int) ist Suchbaum (ohne inorder )
• Rekursionmuster für Peano-Zahlen hinschreiben und Hinweis: als Projektion. Bestimme geeignete Hilfsdaten.
benutzen (plus, mal, hoch, Nachfolger, Vorgänger, minus) • Wende die Vorschrift zur Konstruktion des
• Rekursionmuster für binäre Bäume mit Schlüsseln nur in Rekursionsmusters an auf den Typ
den Blättern hinschreiben und benutzen – Bool
• Rekursionmuster für binäre Bäume mit Schlüsseln nur in – Maybe a
den Verzweigungsknoten benutzen für rekursionslose Jeweils:
Programme für:
– Typ und Implementierung
– Anzahl der Branch-Knoten ist ungerade (nicht zählen!) – Testfälle
– Baum (Tree a) erfüllt die AVL-Bedingung – gibt es diese Funktion bereits? Suche nach dem Typ mit
– Typeset by FoilTEX – 96 – Typeset by FoilTEX – 97

https://www.stackage.org/lts-5.17/hoogle

– Typeset by FoilTEX – 98