Embed Size (px)
Citation preview
1
hs / alp1.3 1
3 Datentypen : Lernziele
• Datentypen und ihre Bedeutung in Programmiersprachen• wichtige elementare Datentypen kennenlernen
• Char, Bool, numerische Datentypen• Typklassen• Konstruierte („selbstdefinierte“) Typen
• Listen, Spezialfall Zeichenketten• Listenzusammenfassungen
• Polymorphie
hs / alp1.3 2
Typen in Programmiersprachen
Datentyp: • Menge von gleichartigen Werten, z.B. Int• dienen zur Festlegung von Argument- und Wertebereich (in funktionaler Programmierung) • wichtiges softwaretechnisches Konzept, da Zuverlässigkeit von Programmen erhöht wird• Strikt (strenge) typisierte Programmiersprache, wenn jeder Ausdruck der Sprache einen Typ hat. • Statisch typisiert, wenn jeder Ausdruck vor Ausfühung einen eindeutigen Typ hat
2
hs / alp1.3 3
Typen in Haskell
Jeder Ausdruck hat einen Typ -> streng typisiert
Typen müssen nicht explizit angegeben werden (!)Bsp.: quad :: Int -> Int quad x = x * x
kann weggelassen werden, ....sollte aber nicht!
Typ wird vor Auswertung durch „Typinferenz“- Algorithmusbestimmt -> statisch typisierte Sprache
hs / alp1.3 4
Die wichtigsten Typen und Typkonstruktoren
u Numerische Typen (Int, Float, ...)u data Bool = True | False
eine Datentypvereinbarung!u Zeichentyp Char
256 Zeichen des ASCII-Codes (Hugs, Haskell etwas allgemeiner)
Literalewie schreibt man Werte eines Typs auf?Wahrheitswerte: True, False nach DefinitionZahlen: wie üblich, Dezimalpunkt statt Komma (in erster Näherung)
Zeichen: 'A', 'B', ....'z' alle druckbaren Zeichen '\n', '\r', '\t', ... Sonderzeichen
3
hs / alp1.3 5
Aus dem Haskell-Report...
char -> '(graphic | space | escape)' escape -> \( charesc | ascii | decimal | o octal | x hexadecimal ) charesc -> a | b | f | n | r | t | v | \ | " | ' | & ascii -> ^cntrl | NUL | SOH | STX | ETX | EOT | ENQ | ACK | BEL | BS | HT | LF | VT | FF | CR | SO | SI | DLE | DC1 | DC2 | DC3 | DC4 | NAK | SYN | ETB | CAN | EM | SUB | ESC | FS | GS | RS | US | SP | DEL cntrl -> ASClarge | @ | [ | \ | ] | ^ | _ string -> " {graphic | space | escape | gap}"
gap -> \ whitechar {whitechar}\ space -> ...
Syntax in erweiterter Backus-Naur Form (BNF)als Regelsystem.
Syntaxregel:nichtterminales Symbol -> Ausdruck aus terminalen, nichterminalen Symbolen
Alternative: ( ...|...|...)
Wiederholung: { ...|...|...}
hs / alp1.3 6
Zeichen und Zahlen
u Auf Zeichen ist Ordnung definiert
z.B. 'A' < 'Z' < 'a'
(Willkürlich) festgelegt durch Folge der ASCII-Zeichen (Hugs) bzw. Unicode-Zeichen
8-Bit Zeichencode: American Standard Code for Information Interchange
16-Bit-Zeichencodierung
Wichtige Funktionen:
ord :: Char -> Int --- ord x liefert Position von x in ASCII-Folgechr :: Int -> Char --- char n liefert das n zugeordnete Zeichen in ASCII-Folge
4
hs / alp1.3 7
Typkonstruktoren
Konstruktoren mit eigener Syntax in Haskell:u Tupel
Zusammenfassen von n Werten ggf. unterschiedlichenTyps, (n /=1). Tupel: (x,y) mit dem Typ (:type x, :type y) Tripel, ..., n-Tupel Bsp: type Stud = (String, String, Int)
Zugriff auf Komponenten: fst liefert erste Komponente eines Tupels, snd zweite matrikel :: Stud -> Int matrikel (x,y,z) = z
Ein Typsynonym, wird genauso benutzt, wie Typ
hs / alp1.3 8
Typkonstruktoren
u ListenWichtigster Konstruktor in funktionalen Sprachen
Listen sind („repräsentieren“) Folgen - alle Werte haben gleichen Typ (Basistyp der Liste)
- es gibt leere, endliche, unendliche ListenListennotation: eckige Klammern [ und ][] -- leere Liste
[1,3,7] -- Typ: [Int]
[0..9] == [0,1,2,3,4,5,6,7,8,9]
['a'..''z'] --- Typ: [Char]
['H',E','L','L','O'] == "HELLO"
Zeichenketten sind Listen von Zeichen: :type String = :type [Char]
5
hs / alp1.3 9
Operationen auf Listen
Erstes Element einer nichtleeren Liste (Listenkopf): head' ['H',E','L','L','O'] == 'H' head':: [Char] -> Char
Listenrest: Liste ohne erstes Element tail' :: [Char] -> [Char] tail' ['H',E','L','L','O'] == [E','L','L','O']
Signaturen von head', tail' unangemessen speziell. Verallgemeinerbar?
Ja! Bei head', tail' kommt es auf den Basistyp gar nicht an
Wie kann man das ausdrücken?? ! Typvariablen a,b,c,.. (später mehr dazu)
hs / alp1.3 10
Operationen auf Listen
Liste konstruieren (!): Konstruktor (:) :: a -> [a] -> [a] Eine Liste vom Basistyp a wird mit : um ein Element vom Basistyp am Listenkopf erweitert
3:[4,5] == [3,4,5]Damit sogar Listenschreibweise entbehrlich:
1:(2:(3:(4:[]))) == [1,2,3,4]
Konstruktorschreibweise wird oft verwendet:
x:xrest bezeichnet eine Liste mit mindestens einem Element, xrest könnte leer sein, das (erste) Element x gibt es aber in jedem Fall.
6
hs / alp1.3 11
Sie haben jetzt eine volleMinute Zeit, Ihr Mobiltelefon* auszuschalten!
* ... wussten Sie eigentlich, dass die meisten Zeitgenossenpenetrante Handybenutzer für dumm, rücksichtslos und unsensibel halten?
hs / alp1.3 12
Gestern ...
... und heute:
• Konstruierte DatentypenLISTEN []
• map und filter • Listenzusammenfassungen• Programmeigenschaften (Laufzeit, Korrektheit) am Beispiel reverse • Programmentwicklung: Histogramme •Zusammenfassung von Listen: Falten
7
hs / alp1.3 13
map
Definieren Funktion, die jedes Element einer Liste einer Operation f unterzieht: [1,2,3] ---> [2,4,6] (verdoppeln) "aBcD" ---> "ABCD" (aus Klein- Großbuchstaben machen)
Algorithmus: wenn Liste leer ([]) fertig sonst wende f auf das erste Element an und verknüpfe es (:) mit der Liste, die entsteht, wenn man den den Algorithmus auf den Rest der Liste anwendet.
> map' :: (a -> b) -> [a] -> [b]> map' f [] = []> map' f (x:xrest) = f x : map f xrest
hs / alp1.3 14
Einfache Anwendungen von map
> capsText :: String -> String> capsText = map' caps'CapsEtc> capsText "ein merkwrdiger Test""EIN MERKWRDIGER TEST"
> ordList :: String -> [Int] > ordList = map ordCapsEtc> ordList "Hallo"[72,97,108,108,111]
Liste der echten Teiler einer Liste von Zahlen
> divList :: [Int] -> [[Int]]> divList = map divs'CapsEtc> divList [15,24][[3,5],[2,3,4,6,8,12]]
divs' :: Int -> [Int] soll für eine Zahl die Liste aller echten Teiler liefern. Definition??
8
hs / alp1.3 15
Filtern
divs' :: Int -> [Int]Idee: prüfe alle Zahlen x, die in Frage kommen, obsie n ohne Rest teilen (n `mod`x == 0 )
> divs' :: Int -> [Int]> divs' n = divs'' n [2..n `div` 2]
Hilfsfunktion
> divs'' n [] = []> divs'' n (x:xs) = > if (n `mod`x) == 0 then x:divs'' n xs> else divs'' n xs
Etwas unübersichtlich! Allgemeines Schema??
Prüfe alle Elemente einer Liste auf eine Eigenschaft, behalte die, die Eigenschaft erfüllen
hs / alp1.3 16
... Nach dem gleichen Schema
Bsp. 2: Eliminieren aller „Nichtbuchstaben“ aus einerZeichenkette removeSpecials :: String -> String removeSpecials [] = [] remove Specials (x:xx) = if p x then x : removeSpecials xs else removeSpecials xs where p x = (ord x >= ord 'A' && (ord x <= ord 'Z'))
(ord x >= ord 'a' && (ord x <= ord 'z'))Layout?? Ok!
Bsp. 3: Finde alle durch 47 teilbaren Zahlen einer Liste von Zahlen
mod47Is0 :: [Int] -> [Int] mod47Is0 [] = [] mod47Is0 (x:xs) = if p x then x : mod47Is0 xs else mod47Is0 xs where p :: Int -> Bool p x = \x -> (x `mod` 47) == 0
9
hs / alp1.3 17
filter
Gleiches Strickmuster:
filter :: -> [a] -> [a] filter p [] = [] filter p (x:xs) = if p x then x : filter p xs else filter p xs
(a -> Bool)
mod47Is0 = filter (\x -> (x `mod` 47) == 0 )
removeSpecials = filter p where p :: Char -> Bool p x = (ord x >= ord 'A' && (ord x <= ord 'Z')) || (ord x >= ord 'a' && (ord x <= ord 'z'))
Es geht noch einfacher...
hs / alp1.3 18
Listenzusammenfassungen (list comprehensions)
• Semantik ("Bedeutung"): [ f x | x <- xs , p x] == (map f . filter p) xs
•Typkorrekt, da: map f :: [a] -> [b] und filter p :: [a] -> [a] also :type (map f . filter p) ist [a] -> [b]
•Aus der Mathematik ist die Mengenschreibweise bekannt: { f(x) | x ∈ XS, P(x) } : "Menge aller f(x) wobei x ∈ XS, wenn gilt P(x)"z.B." Menge aller Quadrate von natürlichen Zahlen, die Primzahlen sind"
• Haskell-Schreibweise (Listenzusammenfassung) : [ f x | x <- xs , p x]
Generator Filter pTransformation
10
hs / alp1.3 19
Beispiele:
• Klein- in Großbuchstaben capsText2 xs = [ caps'' x | x <- xs ] where caps'' x = if isLower' x then ..... else x -- s.o.
CapsEtc> capsText'' "Text"
aber:> capsText3 xs = [ caps x | x <- xs, isLower x ]> where caps = shiftChar delta> delta = - (ord 'a' - ord 'A')
CapsEtc> capsText3' "Text""EXT"
CapsEtc> capsText2 "Text""TEXT"
hs / alp1.3 20
Beispiel "Liste der echten Teiler"
Schritt 1: Liste der echten Teiler einer ganzen Zahl:> divs2 :: Int -> [Int]> divs2 n = [x | x <- [2 .. (n `div` 2) ], n `mod` x ==0]
Schritt 2: Liste der Listen erzeugen:
> divList2 :: [Int] -> [[Int]]> divList2 xs = [divs2 x | x <- xs]
Argument kann in Generator und Filter verwendet werden
11
hs / alp1.3 21
Listenzusammenfassung
Beispiel: Anzahl von Vokalen in einer Zeichenkette
> numbVowels :: String -> Int> numbVowels xs = length [v| v <- xs, (vowel.caps'') v]> where vowel :: Char -> Bool> vowel c> | c == 'a' = True ...> | otherwise = False > caps'' :: Char -> Char > caps'' c =...-- wandelt Gross- in Kleinbuchstaben
numbVowels "ein klitzekleiner Text"8
hs / alp1.3 22
Mehrere Generatoren
Allgemeinere Listenzusammenfassungen:- mehrere Generatoren- mehrere Filter- Verbinden von Werten aus verschiedenen Generatoren
Einfaches Beispiel: [(x,y) | x <- xs, y <- ys] where xs = [1 .. 2]; ys=['a'..'c']
Ergebnis: [(1,'a'),(1,'b'),(1,'c'),(2,'a'),(2,'b'),(2,'c')]
Der n+1-te Generator verändert sich schneller, als der n-te !
12
hs / alp1.3 23
Mehrere Generatoren (2)
Pythagoräische Dreieicke: Gesucht (a,b,c) mit a2 + b2 = c2
Drei Generatoren: [(a,b,c) | a <-[1..9], b <-[1..9] , c <- [1..9], a^2 + b^2 == c^2]
[(3,4,5),(4,3,5)]
[(a,b,c) | a <-[1..9], b <-[a..9] , c <- [b..9], a^2 + b^2 == c^2]
Besser:
hs / alp1.3 24
Übersicht
3. Elementare und konstruierte Typen ....
• Listen• ....
• Programmeigenschaften: Laufzeit, Korrektheit• Effizientere Implementierung von reverse• Verallgemeinern: "Falten" von Listen• Linksfaltung und Rechtsfaltung• Anwendungen: Horner-Schema, Histogramme
13
hs / alp1.3 25
Reverse: Eigenschaften, Verbesserung, .... und nochmal: Abstraktion
• Wiederholungreverse' :: [a] -> [a]reverse' [] = []reverse' (x:xs) = reverse' xs ++ [x]
Die Liste, die nur das Element x enthält
(++) :: [a] -> [a] -> [a]
(++) [] ys = ys
(++) (x:xs) ys = x:(xs ++ ys)
reverse' [1,2,3]= (reverse' [2,3]) ++ [1] = ((reverse' [3]) ++ [2]) ++ [1]= (((reverse' [] ) ++ [3]) ++ [2]) ++ [1]= (([] ++ [3]) ++ [2]) ++[1] = ([3] ++[2]) ++ [1]= (3:([]++[2]) ++ [1]= 3:[2] ++ [1] = [3,2] ++ [1]= 3:([2] ++ [1])= 3:(2:([] ++ [1]))= 3:(2:(1:[])) = [3,2,1]
xs ++ ys benötigt soviel Reduktionen, wie der linke OperandElemente hat !
~ n2 Operationen fürListe der Länge n
hs / alp1.3 26
Verbesserung von reverse ?
> rev :: [a] -> [a]> rev xs = rev' [] xs> where rev' acc [] = acc -- accumulator> rev' acc (x:xs) = rev' (x:acc) xs
rev' [] (1:(2:(3:(4:[]))))= rev' (1:[]) (2:(3:(4:[])))= rev' (2:(1:[])) (3:(4:[])) = rev' (3:(2:(1:[]))) (4:[])= rev' (4:(3:(2:(1:[])))) []= (4:(3:(2:(1:[])))) = [4,3,2,1]
Reduktionen:
Anzahl Reduktionen proportional zur Länge der Liste,also ungefähr ~ nVIEL besser als n2
Beachte unterschiedlicheRekursionstypen. Hier: rekursiver Aufruf liefert ErgebnisErste Version: (++) nach dem Aufruf
Endrekursiv
14
hs / alp1.3 27
Laufzeit von Programmen.....
... hängt entscheidend vom Algorithmus ab, mit dem ein Problem gelöst wird.
• Ein um 10-mal schnellerer Rechner führt zur Beschleunigung um den Faktor 10 ("statt 1000 Zeiteinheiten nur noch 100")
• der "lineare" Algorithmus rev ist im Vergleich zum "quadratischen" Algorithmus für n = 1000 1000-mal schneller ("statt 1000000 Schritte nur noch 1000")
Fazit: es reicht nicht, sich den schnellsten Rechner zu kaufen, aber es lohnt sich, über Effizienz der Algorithmen nachzudenken!
Später dazu systematische Untersuchungen!
hs / alp1.3 28
Verallgemeinerung !?
sumL: Summe der (ganzzahligen) Elemente einer Liste sumL [3,4,8] == 0 + 3 + 4 + 8 = 15
> sumL :: [Int] -> Int> sumL xs = sumL' 0 xs> where sumL' :: Int -> [Int] -> Int> sumL' acc [] = acc> sumL' acc (x:xs) = sumL' (acc + x) xs
mulL: Produkt der (ganzzahligen) Elemente einer Liste mulL [3,4,8] == 1 * 3 * 4 * 8 = 96
> mulL :: [Int] -> Int> mulL xs = m 1 xs> where m :: Int -> [Int] -> Int> m acc [] = acc> m acc (x:xs) = m ( acc * x) xs
"Akkumulator" einführen, in dem Zwischenergebnis aufbewahrt wird. Akkumulator als zusätzlichesArgument!
15
hs / alp1.3 29
Verallgemeinerung (2)
> orList :: [Bool] -> Bool> orList xs = orL' False xs> where orL' :: Bool -> [Bool] -> Bool > orL' acc [] = acc> orL' acc (x:xs) = orL' (acc || x) xs
orList [False,True, False]
True
> rev :: [a] -> [a]> rev xs = rev' [] xs> where rev' :: a -> [a] -> arev' :: a -> [a] -> a> rev' acc [] = acc -- accumulator> -- rev' acc (x:xs) = rev' (x:acc) xs> rev' acc (x:xs) = rev' (acc `cons` x) xs> where cons :: [a] -> a> cons xs x = x:xs
x soll zweiter, acc ersterOperand des zweistelligenOperators sein.
hs / alp1.3 30
Übersicht
•"Falten" von Listen (Wiederholung) • Linksfaltung und Rechtsfaltung• Falten von nichtleeren Listen • Anwendungen: Horner-Schema, Histogramme
• Systematische Programmentwicklung (I) Top-Down / Bottom - Up
Grundsätzliches Vorgehen Beispiel
16
hs / alp1.3 31
Faltung von Listen
> foldl' :: (b -> a -> b) -> b -> [a] -> b> foldl' op a [] = a> foldl' op a (x:xs) = foldl' op (a `op` x) xs
Abstraktion von spezieller Verknüpfungsoperation:
.. und die Beispiele:
> sumL' = foldl' (+) 0> mulL' = foldl' (*) 1> orL' = foldl' (||) False> reverse = foldl' cons []> where cons xs x = x:xs
Oder :flip :: (a->b->c) -> (b->a->c)flip f = f' where f' y x = f x y
reverse = foldl' (flip (:)) []
hs / alp1.3 32
Noch ein Beispiel: Horner-Schema zur Berechung von Polynomen
Berechne p(x) = anxn + an-1xn-1 + ... a1x + a0 für Argument x
Naive Berechnung: n + (n-1) + (n-2) + ....+1 Multiplikation: teuer!
Umformen: (..(.(o*x+an)*x + an-1)*x + an-2)*x +.....+ a1)*x + a0Nur noch n+1 Multiplikationen!
> horner :: Int -> [Int] -> Int > horner x = foldl (horn x) 0> where horn :: Int -> Int -> Int -> Int> horn x e a = e*x + a
Mit foldl definieren:
Zu spezieller Typ: später allgemeineren auf beliebigen numerischen Typen
horner 2 [1,1,1,1, 1,1,1,1] 255
17
hs / alp1.3 33
Rechtsfaltung
> foldr' :: (a -> b -> b) -> b -> [a] -> b> foldr' op e [] = e> foldr' op e (x:xs) = x `op` (foldr' op e xs)
"Zusammenfassung von rechts" soll heißen:
foldr ⊗ e [x1,....xn-1,xn] = x1 ⊗ (x2 ⊗ (x3 ..... ⊗(xn ⊗ e) ....))
foldr' (+) 0 [1,2,3] = 1+(foldr' (+) 0 [2,3])= 1+(2+(foldr' (+) 0 [3])))= 1+(2+(3+(foldr' (+) 0 [])))= 1+(2+(3+0)) = ... = 6
Kein Unterschied zu Linksfaltung, wenn ⊗ kommutativ und assoziativ
hs / alp1.3 34
> length' :: [a] -> Int> length' = foldr' plusEins 0 > where plusEins x e = 1+e
> foldr' :: (a -> b -> b) -> b -> [a] -> b> foldr' op e [] = e> foldr' op e (x:xs) = x `op` (foldr' op e xs)
length' [5,6] = foldr' plusEins 0 [5,6]= 5 `plusEins` foldr plusEins 0 [6]= 5 `plusEins` (6 `plusEins` foldr plusEins 0 [])= 5 `plusEins` (6 `plusEins` 0)= 5 `plusEins` (1+0)= 1 + (1+0) = 2
18
hs / alp1.3 35
Map durch foldr ausdrücken... ?!
> map'' :: (a -> b) -> [a] -> [b]> map'' f = foldr' ((:) . f) []
map'' :: (a->b) -> [a] -> [b]also: f:: a -> b (:) b -> [b] -> [b]((:) . f) :: a -> ([b] -> [b])
Bsp: ((:) . f) x xs = (:) (f x) xs = f x : xs
hs / alp1.3 36
Rechtsfaltung: noch ein Beispielfoldr :: (a -> b -> b) -> b -> [a] -> b
faltet Liste mit Operator ⊗ schrittweise von rechts
foldr (*) [ 1, 2, 3] 1 Anfangswert
[ 1, 2]
3 ∗ 1
[ 1 ] 6
2 ∗ 3
1 ∗ 6
Anfangswert:- foldr soll total sein. Auch leere Listen können „gefaltet“ werden
- zwingend, wenn Basistyp und Ergebnistyp nicht überein- stimmen§
Dagegen: foldr1:: (a -> a -> a) -> [a] -> afoldr1 ⊗ e [x1,....xn-1,xn] = x1 ⊗ (x2 ⊗ (x3 ..... xn-1 ⊗ xn)...)
Partiell! Nicht definiert für leere Liste!
19
hs / alp1.3 37
Heute
• Nachtrag zu map mit foldr definiert
• Systematische Programmentwicklung: Beispiel Histogramm• Teilproblem: Sortieren
• Allgemeines zur Programmentwicklung• Zusammenfassung: wichtige Operationen auf Listen
• Zahldatentypen und Typklassen (ggf. Do.)
hs / alp1.3 38
Programmentwicklung: Beispiel Zeichenhistogramm
1. Repräsentation definieren
> type Text = [Char]> type HistoElem = (Char,Int)> type CharHisto = [HistoElem] -- Histogramm von Zeichen: > -- Liste von (Zeichen,Int)-Paaren
Top-Down-Entwurf:Lege Repräsentation der Daten fest. Zerlege Problem in Teilaufgaben und löse diese ggf. wieder durch Zerlegung.
Aufgabe: Histogramm der Buchstaben eines Textes erstellenEingabe: Text (Zeichenkette) mit beliebigen ASCII-.Zeichen Ausgabe: Histogramm für alle Buchstaben des Alphabets
(ohne Umlaute, ß) sortiert nach Häufigkeit. Groß- und Kleinbuchstaben werden nicht unterschieden.
20
hs / alp1.3 39
Beispiel
ch1 "Hallo!" = [('L',2), ('A',1), ('H',1), ('O',1)]
"Hallo!" --> "HALLO" Schritt 1: Normieren
"Hallo!" [] --> "ALLO" [('H',1)] --> "LLO" [('H',1),('A',1)] --> "LO" [('H',1),('A',1),('L',1)] --> "O" [('H',1),('A',1),('L',2)] --> "" [('H',1),('A',1),('L',2), ('O',1)]
Schritt 2: Histogramm erstellen
[('H',1),('A',1),('L',2) ('O',1)] --> [('L',2), ('A',1), ('H',1), ('O',1)]
Schritt 3: Sortieren
--> soll heißen " wird abgebildet auf" ( informelles Zeichen)
hs / alp1.3 40
Programmentwicklung (2)
2. Sonderzeichen filtern und in Grossbuchstaben wandeln> filterAndCapsLetter :: Text -> Text
3. Histogramm erstellen> histo :: Eq a => [a] -> [(a,Int)] -- Klasse Eq a später!
4. Histogramm sortieren nach Häufigkeit> mySort :: [a] -> [a]> -- etwas allgemeiner später
21
hs / alp1.3 41
Programmentwicklung (3)
5. Lösung durch verbinden der Teillösungen
> ch1 :: Text -> CharHisto -- Endbeutzerschnittstelle
> ch1 = (mySort . histo . filterAndCapsLetter)
Histogramm Filtern undzu Großbuch
staben
HistogrammerstellenSortieren
Eingabetext
map, filterFaltenZ.B. Falten ?!
hs / alp1.3 42
Programmentwicklung (4)
Teilaufgaben lösen:
Filtern und map anwenden (toUpper, isAlpha sind Bibliotheksfunktionen):> filterAndCapsLetter txt = [toUpper c|c <- txt,isAlpha c] histo: gleiches Definitionsmuster wie foldl :Prinzip: berücksichtige das nächste Zeichen der Eingabe; falls noch nicht vorgekommen: Anzahl 1 sonst bisherige Anzahl + 1
Sortieren: hier mit als "Suche durch Einfügen" (insertion Sort) Prinzip: füge jedes Element der zu sortierenden Liste unter Beachtung der Sortierreihenfolge in neue Liste ein
22
hs / alp1.3 43
Histogramm erstellen
"Hallo!" [] --> "ALLO" [('H',1)] --> "LLO" [('H',1),('A',1)] --> "LO" [('H',1),('A',1),('L',1)] --> "O" [('H',1),('A',1),('L',2)] --> "" [('H',1),('A',1),('L',2), ('O',1)]
Idee: um das gelesene Zeichen c im Histogramm h zu berücksichtigenfüge c mit dem Wert 1 in h ein: h ++ [(c,1)], wenn c bisher nicht vorkam sonst ersetze (c,n) in h durch (c,n+1)histo' :: CharHisto -> Text -> CharHistohisto' h [] = hhisto' ((y,n):ys) (x:xs) = if x==y then (y,n+1):ys
else (y,n): (enter x ys) where enter :: Char -> CharHisto -> CharHisto ...
Faltungsmuster!
> histo :: Eq a => [a] -> [(a,Int)]> histo = foldr enter []> where enter :: Eq a => a -> [(a,Int)] ->[(a,Int)]> enter x [] = [(x,1)]> enter x ((y,n):ys) = if x==y then ((y,n+1):xs> else (y,n):(enter x ys)
Entspricht nicht ganz obigem Beispiel,wieso?
hs / alp1.3 44
Sortieren durch Einfügen
[5,17,1,13] []
[17,1,13] [5]
[1,13] [17, 5]
[13] [ 1, 17, 5] [ 17, 1, 5] [17, 5, 1]
[] [13, 17, 5, 1] [17,13,5,1]
23
hs / alp1.3 45
HeuteHeute
• Verallgemeinerung: Sortierprogramm
• Allgemeines zur Programmentwicklung
• Zusammenfassung: wichtige Operationen auf Listen
• Typen und Typklassen
• Zahldatentypen und Typklassen
hs / alp1.3 46
Teilschritt: Sortieren
> mySort :: [(Char,Int)] -> [(Char,Int)] > mySort xs = mSort [] xs> where mSort :: [(Char,Int)] -> [(Char,Int)] -> [(Char,Int)]> mSort ys [] = ys> mSort ys (x:xs) = mSort (insert x ys) xs> insert :: (Char,Int) -> [(Char,Int)] -> [(Char,Int)]> insert x [] = [x]> insert x (y:ys) = > if x `ge` y then (x:y:ys) > else (y:insert x ys) > ge :: (Char,Int) -> (Char,Int) -> Bool> (x,n) `ge` (y,m) = (n >= m)
Eine etwas unübersichtliche Funktion!
24
hs / alp1.3 47
Sortieren: Sortieralgorithmus anwendungsunabhängig gestalten
> mySort xs = insertionSort [] xs>
Faltungsmuster!
insertionSort ys [] = ys insertionSort ys (x:xs) = insertionSort (insert x ys) xs
> insertionSort = foldr insert []> where insert :: (Char,Int) -> [(Char,Int)] -> [(Char,Int)]> insert x [] = [x]> insert x (y:ys) = > if x `ge` y then (x:y:ys) > else (y:insert x ys) > ge :: (Char,Int) -> (Char,Int) -> Bool> (x,n) `ge` (y,m) = (n >= m)
Vergleichoperator`ge` ??
Vergleichsoperatorals Argument derSortierfunktion!!
hs / alp1.3 48
Sortieren durch Einfügen
> mySort :: Ord a => [a] -[a] > mySort = insertionSort' (>=) -- oder eine andere > -- Ordnungsrelation
> insertionSort':: Ord a => (a -> a - Bool) -> [a] -> [a]> insertionSort' ge = foldr insert []> where -- insert::Ord a => a->[a]->[a]> insert x [] = [x]> insert x (y:ys) = > if x `ge` y then (x:y:ys) > else (y:insert x ys)
Damit:> ch1 :: Text -> CharHisto -- Endbenutzerschnittstelle
> ch1 = (mySort' . histo . filterAndCapsLetter)> where mSsort' = insertionSort' ge
25
hs / alp1.3 49
Programmentwicklung
Und Bottom up?
Bottom-Up-Entwicklung:Zerlege Problem grob in Teilprobleme (Sonderzeichen entfernen, Eintrag eines Elements in Histogramm, sortieren...) und entwickle für alle Teilprobleme Lösungen. Setze diese schrittweise zu komplexeren Programmen zusammen, bis Ausgangsproblem gelöst ist.
Vorteil: Einzelfunktionen können unabhängig während der Entstehung getestet werden. Nachteil: Man verliert leicht die Übersicht und erkennt den Wald vor lauter Bäumen nicht.
Funktionale Programmierung gut geeignet für Bottom-Up - Ansatz.
hs / alp1.3 50
Wie entwickelt man ein (kleines) Programm?(nach S. Thompson , angelehnt an G. Polya: How to solve it)
u Problem analysieren und verstehen
u Lösung planen: Programmentwurf
u Programmierung der Lösung
u Rückschau und Test
Allgemeines zur Programmentwicklung
26
hs / alp1.3 51
u Problem analysierenWas soll das Programm leisten?
(umgangssprachlich)Welche Eingaben (Argumente)und Ausgaben (Werte) ? => Typen, Programmname
Welche Teilprobleme ?Ggf. Diagramm, Beschreibung inUmgangssprache.
Spezielle Einschränkungen derEin- / Ausgaben?
Spezifikation des Programms?
u Bestimmung der relativenWorthäufigkeit in einemTextdokumentFür jedes signifikante Wort w (
oderTerm) eines Textes d soll|w| / t berechnet werden. |w| gibtan, wie oft w in d vorkommt, t ist dieAnzahl signifikanter Terme in d.
w ist signifikant, wenn es keinStoppwort ist. Eine Stoppwortlisteliegt vor.
relfreq :: Text -> [(Word, Float)]
(w,r) in relfreq t => 0 < = r < = 1
Lexikographisch nach w sortieren.Teilprobleme:Text in Wörter zerlegen, (Satzzeichen
eliminieren!), Stopwörter eliminierenAuf Kleinschreibung normieren.Absolute Worthäufigkeiten bestimmen.Sortieren.
hs / alp1.3 52
u Lösung planen
w Ähnliches Problem schon mal gelöst?w Allgemeineres, von dem dieses ein Spezialfall ist?w Teilprobleme präzisieren (Typen, Bezeichner!)w Wie lassen sich Ein- und Ausgabe über gelöste
Teilprobleme miteinander verbinden?w Alle Randbedingungen berücksichtigt?w Kann man ein Problem auf ein „kleineres“ zurückführen?
(Rekursive Lösungen!)w Diagramm der Lösungsschritte und Verbindungen
zwischen TeillösungenBottom up: Teillösungen und Verbindungen informell planenTop down: Teillösungen spezifizieren
27
hs / alp1.3 53
u Programmierungw Berücksichtigung der programmiersprachlichen
Konstrukte einer speziellen Sprache (erst hier!)w Wie verbindet man Teillösungen ? Funktionskomposition,
Aufruf von Funktionen mit Übergabe von Parametern.w Wie drückt man Fallunterscheidungen aus, Iteration,
Rekursion?w Welche nützlichen Bibliotheksfunktionen gibt es? („A library can make or break a language“, P. Wadler)w Prüfe jeden Einzelschritt: Tut er das, was er gemäß
Spezifikation (auch informeller) tun soll? Kann man dasbeweisen?
w Teste jeden Einzelschritt.
hs / alp1.3 54
u Rückschau und Testw Systematisch Ein- / Ausgabebeziehung testen
(Blackbox test)- Randwerte, sofern von der Spezifikation zugelassen- normale Werte- Werte außerhalb der erlaubten Eingaben
w Wie kann die Lösung verbessert werden?- Effizienz?- Erweiterbarkeit?
w Was würden Sie verändern, wenn Sie neu beginnenwürden?
w Kann die Lösung als Teil einer allgemeineren Aufgabeverwendet werden?
=> im Beispiel: - Ähnlichkeit von zwei Dokumentenauf Basis relativer Häufigkeiten, Histogramm-Erstellung
28
hs / alp1.3 55
Programmentwicklung: noch ein Beispielu Aufgabe: Die Wörter eines Textes sollen hinsichtlich ihrer "Bedeutung" in
dem Text gewichtet werden.Nützlich für Rangfolgebeziehung in Suchmaschinen!Umgangssprachliche Spezifikation :Eingabe: ASCII Zeichenkette (der Text)Ausgabe: Liste von Paaren (Wort, Gewicht)Gewicht w =
log 2 (Absolute Häufigkeit von w) / log 2 (Anzahl Wörter in d)Nebenbdingungen: keine Stopwörter (häufig vorkommende),
keine Unterscheidung Groß-/KleinbuchstabenSonderzeichen entfernen
hs / alp1.3 56
> module Texttools
> where
Beispiel f. systematische Programmentwicklung (VL)
==============================================
> type Word = String
> type Text = [Char]
> type Line = String
> relFreq :: Text -> [(Word,Float)]
> relFreq = sort . absToRelFreq . histoW . rmStopw .normalize . words'
29
hs / alp1.3 57
1. Zerlegung von Text in Wortfolgen===================================> words' :: Text -> [Word]
Entferne fuehrende "whitespaces", bestimme das erste Wort - bis zumnaechsten"whitespace" - und zerlege den Rest:
> words' "" = []> words' t = w1 : (words' (rest ))> where w1 = firstWord t'> rest = drop lw1 t'> t' = dropWhile whiteSpace t> lw1 = length w1
> firstWord :: Text -> Word> firstWord "" = []> firstWord (c:xs)> | whiteSpace c = []> | otherwise = c:(firstWord xs)
> whiteSpace c = c==' ' || c=='\n' || c=='\t'
hs / alp1.3 58
2. Normalisieren der Wörter und Stopwort-Eliminierung=====================================================
> normalize :: [Word] -> [Word]> normalize ws = map norm ws> where norm w = [toLower c | c <- w, isAlpha' c]> isAlpha' c = ('A' <= c && c <= 'Z') || > ('a' <= c && c <= 'z')
> rmStopw :: [Word] -> [Word] > rmStopw ws = filter (el stopwordList) ws> where el :: Ord a => [a] -> a -> Bool -- [a] ist sortiert!> el [] w = False> el (x:xs) w = x==w || el xs w
30
hs / alp1.3 59
3. Erstellen eines (Wort-) Histogramms======================================
> histoW :: [Word] -> [(Word,Int)]> histoW ws = mkHisto [] ws -- mache aus Wortliste Histogramm
> mkHisto :: Eq a => [(a,Int)] -> [a] -> [(a,Int)]> mkHisto h [] = h> mkHisto h (x:rest) = mkHisto (enter h x) rest> where enter :: Eq a => [(a,Int)] -> a -> [(a,Int)]> enter [] el = [(el,1)]> enter ((el,n):rest) x> | el == x = (el,n+1):rest> | otherwise = (el,n):(enter rest x)
hs / alp1.3 60
4. Bestimmung der relativen Wortfrequenzen======================================
> absToRelFreq :: [(Word,Int)] -> [(Word,Float)]> absToRelFreq xs = map (nfreq termNo) xs> where termNo = length xs> nfreq :: Int -> (Word,Int) -> (Word,Float)> nfreq n (w,absFreq)> = (w, logBase 2 absFreq' / logBase 2 n')> where absFreq' = fromInt absFreq> n' = fromInt n
31
hs / alp1.3 61
5. Sortieren============
> sort :: [(Word,Float)] -> [(Word,Float)]> sort xs = qsort le xs> where (x,f) `le` (x',f') = x <= x' --- lex Ordnung
> qsort :: (a -> a -> Bool) -> [a] -> [a]> qsort le [] = []> qsort le (x:ys) = qsort le [y | y <- ys, y `le`x] ++ [x]> ++ qsort le [y| y <- ys, not (y `le` x)]
> stopwordList = [....]
hs / alp1.3 62
Ergebnis für einen Text mit 4500 Wörtern ( 2300 Stopwörter) zurQualitätsbewertung von wissenschaftlichen Zeitschriften inWirtschaftswissenwissenschaften (Mangm. Inform. Syst.):
journal: 0.507052, : 0.438528, journals: 0.401829, mis: 0.380289, quality:0.327677, faculty: 0.294334, say: 0.294334, rankings: 0.294334, research:0.253526, isr: 0.253526, list: 0.253526, tend: 0.253526, based: 0.200914,rates: 0.200914, survey: 0.200914, surveys: 0.200914, business: 0.200914,website: 0.126763, networking: 0.126763, home: 0.126763, way: 0.126763,addition: 0.126763, jmis: 0.126763, misq: 0.126763, hawaii: 0.126763,university: 0.126763, problems: 0.126763, low: 0.126763, end: 0.126763,response: 0.126763, management: 0.126763, issue: 0.126763, today:0.126763, prestigious: 0.126763, highly: 0.126763, cacm: 0.126763, using:0.126763, computing: 0.126763, recently: 0.126763, good: 0.126763, pretty:0.126763, fact: 0.126763, date: 0.126763, problem: 0.126763, quite:0.126763, college: 0.126763, disciplines: 0.126763, school: 0.126763,looked: 0.126763, httpwwwcbahawaiiedupankods: 0.0, course: 0.0,httpwwwcbahawaiiedupankohumanerr: 0.0, error: 0.0, human: 0.0,
32
hs / alp1.3 63
Zusammenfassung: wichtige Operationen auf Listen (1)
Listenkonstruktor x:[] == [x] x1:(x2:(x3:[])) == [x1,x2,x3] -- nur andere Schreibweise
Listenlängelength :: [a] -> Intlength "abc" = 3
Listenkopf, Listenschwanz head :: [a] -> a head (x:xs) = x
tail [a] -> [a] tail (x:xs) = xs
Musterschreibweise (x:xs) bezeichnet in Definitionen eine nichtleere Liste. Sie enthältmindestens ein Element, das mit der Variablen x bezeichnet wird
Beachte Muster für
nichtleere Liste
Konstruktoren sindTeil der Sprache,alles anderedefinierbar!
hs / alp1.3 64
Zusammenfassung: wichtige Operationen auf Listen (2)
Listenabbildung mit mapAnwenden einer Funktion f auf jedes Element x der Liste. Die Werte f xsind die Elemente der Ergebnisliste.Beispiel:map:: (a -> b) -> [a] -> [b]map (>0) [1,-1,0] == [True, False, False]
Listen filtern mit Filterprädikat pDie Elemente einer Liste entfernen, die dem Prädikat nicht genügenBeispiel:filter :: (a -> Bool) -> [a] -> [a]filter (>0) [1,-1,0] == [1]
Listenzusammenfassung:Kombination von map und filter [ f x | x <- xs, p x] == (map f . filter p) xs
Vorsicht mit mehre-
ren Generatoren
33
hs / alp1.3 65
Zusammenfassung: wichtige Operationen auf Listen (3)
Listenfaltung:Zusammenfassung der Elemente einer Liste zu einem Wert vermöge einesOperators, der den Anfangswert sukzessive mit den Listenelementen verknüpft.
Beispiele für Links- und Rechtsfaltung:foldl (b -> a -> b) -> b -> [a] -> bfoldl (-) x [x1,x2,x3] == ((x - x1) - x2)- x3 --Linksfaltung
foldr (a -> b -> b) -> b -> [a] -> bfoldr (++) [] [[x0,x1,x2],[x3,x4]] = [x0,x1,x2]++([x3,x4]++[]) = [x0,x1,x2,x3,x4]Ähnlich: Faltung nichtleerer Listenfoldr1, foldl1 :: (a -> a -> a) -> [a] -> a
Beachte
unterschiedliche
Signatur von foldl,
foldr
hs / alp1.3 66
Zusammenfassung: wichtige Operationen auf Listen (4)
Reißverschlussfunktion zip: Paarbildung der i-ten Elemente von zwei Listenzip :: [a] -> [b] -> [(a,b)]zip [1,2,3,4] ['a','b','c'] == [(1,'a'),(2,'b'),(3,'c')]
Die ersten / letzten n Listenelementetake,drop :: Int -> [a]take 5 "Hello World" == "Hello"drop 5 "Hello World" == " World"Ähnlich: entnehmen / entfernen von Elementen, solange sie ein Prädikat perfüllen.takeWhile, dropWhile :: (a -> Bool) -> [a] -> [a]
Listenindex (!!)Liefert das n-te Listenelement einer nichtleeren Liste xs mit0 <= n <= length xs -1"Hello"!!1 == 'e'
34
hs / alp1.3 67
Typklassen und Zahldatentypen
Monomorphe Funktionen:Typ eindeutig bestimmtBeispiel: isLower :: Char -> Bool
Parametrisch polymorphe Funktionen:beliebigerTyp, verwende Typvariable ohne EinschränkungBeispiel: reverse :: [a] -> [a]
Parametrisch polymorphe Funktionen mit Einschränkung:beliebigerTyp, der Einschränkung genügtBeispiel: equal :: [a] -> [a] -- Geleichheit von ListenNebenbedingung (constraint): Die Elemente der Liste müssen mit ==vergleichbar sein.
Überladene Bezeichner (Funktionsbezeichner, Operatoren):Derselbe Bezeichner steht für VerschiedenesBeispiel: (+) :: Double -> Double (+) :: Int -> Int
In Haskell nur Operatoren
überladen
hs / alp1.3 68
Heute
• Typen und Typklassen (Wiederholung) • Default- Implementierungen
• Typumwandlung (coercion) • Bestimmung des Typs von Ausdrücken: Typableitung• Algebraische Typen
• Aufzählungstypen• Produkttypen• algebraische polymorphe Typen• rekursive Typen
35
hs / alp1.3 69
Typen und Operationen
Idee: Typen durch die Operationen charakterisieren, die aufihren Werten erlaubt sein sollen
Typklassen - sind durch Signaturen der erlaubte Operationen definiert - enthalten Typen oder andere Typklassen (Subtypen)
Beispiel:Class Num a where (+) :: a -> a -> a neg :: a -> a
Typen sind Elemente (instances) von Typklassen:instance Num Int where x+y = primAdd x y -- systemdefiniert neg x = primNegateInt x -- "
Typklasse: abstrakte
Schnittstelle für die
Werte ihrer Typen
hs / alp1.3 70
Subklassen
Typklassen können durch Sub(typ)klassen spezialisiert werden:Class T1 a => T1Sub a where (additionalOperator) :: a -> a -> a -- z.B.
T1Sub wird dadurch als Subklasse von T1 definiert (oder T1Super(typ)klasse von T1Sub).
Ein Typ T, der zur Subklasse T1Sub gehört, muss alle Operationen von T1implementieren (d.h. T muss instance von T1 sein) und zusätzlich die vonT1Sub (hier die eine additionalOperator:: ...). Das gilt für alledirekten und indirekten Superklassen von T1.TSub1 zugehörige Typen unterliegen damit stärkeren Nebenbedingungen(constraints) als T1.
T1 heißt Ober-(Superklasse) von T1Suboder T1Sub spezialisiert T1
36
hs / alp1.3 71
Numerische Typen und Typklassen
Fractional ist Subklasse von Num mit zusätzlicher Operation (/) und anderen.
Zu Fractional gehören die Gleitkommatypen Double, Floatund Ratio ( rationale Zahlen, Brüche).
Class Num a where (+) :: a -> a -> a neg :: a -> a
Class Num a => Fractional a where (/) :: a -> a -> a recip :: a -> a -- reziprok 1/x
hs / alp1.3 72
Mehrere Oberklassen
Ganze Zahlen sind sowohl aufzählbar (Enum) als auchnumerisch (Num).Integral Subklasse von Enum und Num
Beachte: nicht alle aufzählbaren Dinge sind numerisch - etwa Zeichen.
Class Enum a where fromEnum :: a -> Int toEnum :: Int -> a
Class Num a where (+) :: a -> a -> a neg :: a -> a
class (Enum a, Num a) => Integral a where quot, rem, div, mod :: a -> a -> a quotRem, divMod :: a -> a -> (a,a) even, odd :: a -> Bool toInteger :: a -> Integer toInt :: a -> Int
37
hs / alp1.3 73
Implementierung von Typen...
Class (Num a) => Fractional a where (/) :: a -> a -> a recip :: a -> a -- reziprok 1/x
instance Fractional Float where (/) = primDivFloat recip x = 1/x
Entbehrlich!recip kann sich für alle Typdefinitionen auf (/) abstützen. Deshalb recip als default-Implementierungin Class (num a) Fractional afestlegen!
recip x = 1/x
hs / alp1.3 74
Typwandlung (typ coercion)
Bezeichnet die Umwandlung eines Typs in einen anderen.Beispiel: 3.5 + (8 div 4)
Gleitkommazahl Ganze Zahl
-1 | + 0.35000000000000
+000000000000000000002
Summe??
In manchen Programmiersprachen: automatische Typwandlung (Typangleichung, coercion).In Haskell (und anderen Sprachen) muss Typangleichung explizit programmiert werden: z.B. fromInteger, fromInt
Typfehler in Haskell
Und warum ist
3.4 + 2
korrekt??
Beispiel: 3.5 + fromInt (8 div 4)analog z.B: toInt :: Integral a => a -> Int
38
hs / alp1.3 75
Typableitung (Typinferenz)
Zur Bestimmung des Typs einer Funktion muss es ein formales Verfahren- genauer: einen Algorithmus - geben.
Hier nur anhand einiger Beispiele:
a) Sei g x = ord x f y z = g y + z
(+) :: Num a => a->a->a ==> Num z und Num (g y) und Num (f y z)ord :: Char -> Int ==> Char x und Int (g x) ==> Int (g y) und Int z
==> f::Char -> Int -> Int
b) Sei g x = 3 f y z = g y + z
(+):: Num a => a->a->a ==> Num z und Num (g y) und Num (f y z) Num 3 ==> g:: Num b => a -> b -- Typ von x beliebig ==> f:: Num a => b -> a -> a
hs / alp1.3 76
Typableitung (2)
d) Bestimme Typ von: h = g.f
(.) :: (d -> e) -> (c -> d) -> c -> ed steht für (a,[Char]) und (Int, [u]) Frage: Kann man (a,[Char]) und (Int,[u]) angleichen (unifizieren) ?
c) Sei f(a,c) = (a,['a'..c]) g(m,li) = m + length li
['a'..c] ==> Char c(+) :: Num b => b->b->->b ==> Num m length :: [u] -> Int ==> [u] li und Int m ==> f :: (a,Char) -> (a,[Char]) g :: (Int, [u]) -> Int
Soll heißen: li ist vom Typ [u]
39
hs / alp1.3 77
Typangleichung (3)
Unifikationsalgorithmus: finde allgemeinsten Typ T, der dieTypen T1 , T2,..., Tn angleicht.Erforderlich: Regeln für erlaubte TypangleichungenBeispiele: Wenn a Typvariable und T Typ dann T/a (1) (sprich: a kann durch T ersetzt werden) Wenn [a] Typ und T Typ dann [T] Typ (Spezialfall von 1)
Wenn Unifikation fehlschlägt: Typfehler
Im Beispiel: Int/a und Char/u ( Substitutionen "Int für a" und "Char für u") allgemeinster Unifikator von (a,[Char]) und (Int, [u])
hs / alp1.3 78
Noch ein Beispiel: map
Gesucht: Signatur von map map -- oder: map f where f = map map:: (a -> b) -> [a] -> [b] -- ist bekannt
Im Ausdruck map map ist das erste Argument f wiederum map,f=map muss vom Typ (x -> y) für geeignete Typen x und y sein.
Bezeichnet man die Signatur von f = map mit map:: (c -> d) -> [c] -> [d] dann besteht die Aufgabe darin, (a -> b) mit (c -> d) -> [c] -> [d] zu unifizieren
Mit (c->d)/a, ([c]->[d]/b) erhält man die Lösung ( (c->d)-> [c] )/a, [d]/b nicht möglich, wegen Rechtsklammerung von ->)
40
hs / alp1.3 79
Heute
Klausurergebnisse etc.
AlgebraischeTypenAufzählungstypen (Wiederholung u. Ergänzung)Produkt- und VereinigungstypenPolymorphe algebraische Typen
Rekursive Typen Bäume (Einführung)
Darstellung und Auswertung arithmetischer Ausdrücke
hs / alp1.3 80
Scheinkriterien
1. Mindestens 50% der Übungen und2. Aktive Mitarbeit in den Tutorien und3.
a) Mindestens 50% der Punkte in jeder der beiden Klausuren oderb) Mindestens 40% der Punkte im Durchschnitt der beiden Klausuren
und mündliches Prüfungsgespräch (ca. 15 Minuten, ab Mitte März 2000 statt) oder
c) Mindestens 50 % der Punkte der Nachklausur oderd) Mindestens 40 % der Punkte der Nachklausur und mündliches Prüfungsgespräch (erste Woche des
Sommersemesters)
41
hs / alp1.3 81
3.n+1 Algebraische Typen
Bisher:• elementare Typen Int, Char, ...• Standardkonstruktoren: Listen-,Tupelkonstruktor (:) ,()• und daraus zusammengesezte:• histogramm :: [(Char,Int)]
10
Schwer als Typ auszudrücken:• Mengen gleichartiger Werte: Sonntag ... Samstag• Alternativen (Varianten) : Hausnummer = Int(4) | Char(4) ??• Nichtlineare Strukturen
7
3 9
15
16
hs / alp1.3 82
Aufzählungstypen
Endliche Menge von Werten kann in vielen Programmiersprachenals Aufzählungstyp definiert werden.
data Bool = True | False -- Typ und Konstruktoren -- mit großen Anfangsbuchstabendata Week = Su|Mo|Tu|We|Th|Fr|Sa deriving (Eq, Enum, Ord)
Kanonische Abbildung zwischen Werten des Typs undnatürlichen Zahlen 1.Wert <-> 0, 2. Wert <-> 1,...n-ter Wert <-> n-1 deshalb die Default-Implementierungen der OperationenfromEnum, toEnum der Typklasse Enum verwendbar.
42
hs / alp1.3 83
Operationen auf dem Typ Days
> weekend :: Week -> Bool> weekend x = x==Sa || x==Su
> nextDay :: Week-> Week> nextDay x = toEnum ((fromEnum x +1) `mod`7)
Main> nextDay MoERROR: Cannot find "show" function for:*** Expression : nextDay Mo*** Of type : Week
> instance Show Week where> show x > |x==Su = "Sonntag"> |x==Mo = "Montag"
> |otherwise = "weiß ich nicht" -- oder so...
Main> nextDay SuMontag
show:: Show t => t -> String
hs / alp1.3 84
Produkttypen
Wenn T1 und T2 Typen sind, dann istdata Prod = P T1 T2Produkttyp: Werte sind die Elemente des kartesischen Produktsvon T1 und T2, die durch P v w bezeichnet werden v aus T1, waus T2
Konstruktor
Beispiel: data People = P Name Age deriving (Eq, Ord)
type Name = String -- Typalias, kein neuer Typ!! type Age = Int
43
hs / alp1.3 85
Typkonstruktoren und Funktionen
Alternative: type People' = (Name, Age)Vor- / Nachteile?
+ Eigener Typ sicherer ("1001",5) ist legitimer Wert von People', nicht von People + Aussagekräftige Fehlermeldungen bei eigenem Typ - Generische Funktionen (fst, ...) nicht nutzbar
Kombination Produkttypen und Alternativen: VereinigungstypWie kann man Typ definieren, der z.B. Char und Int enthält?
data UnionCI = C Char | I Int deriving Eq
hs / alp1.3 86
Polymorphe Konstruktoren
Typkonstruktoren sind Funktionen ähnlich:
Su, Mo:: Days -- einstellige KonstruktorenP :: Name -> Age -> People -- zweistelliger Konstruktor
data Address = A Name Vorname PLZ Orttype Vorname = String usw.
Naheliegend, polymorphe algebraische Typen zulassen:Beispiel:data Pair a = P a adata Tuple a b = T a b
44
hs / alp1.3 87
Heute
u Algebraische Datentypen am Beispiel von Bäumenw Wiederholung: Definitionen, binäre Bäumew Algorithmen auf Bäumen, Durchlaufen der Knotenw Operatorbäumew Auswertung arithmetischer Ausdrücke mittels Operatorbaum
u Kapitel 4: Theorie und Praxisw Einführung: Grammatik und Syntaxanalysew Syntaxbaum für arithmetische Ausdrücke
Allen ein gutes, erfolgreiches, glückliches Jahr 2000 !
hs / alp1.3 88
Restprogramm
u Kapitel 4 Fortsetzungw Klassifizierung von rekursiven Funktionenw Entrekursivierungw Berechenbare Funktionen und Rekursion - eine Einführungw λ-Kalkül und funktionale Sprachenw Laufzeitabschätzung
u Kapitel 5: Algorithmische Grundmusterw Gierige Algorithmen ("greedy")w Backtrackingw Dynamisches Programmieren
u (Kapitel 6: Spezielle Aspekte funktionaler Programmierungw Programmieren mit unendlichen Listen, Ein-/Ausgabe, ... )
45
hs / alp1.3 89
Rekursive Typen...
... sind nichts Besonderes [ ] ist Liste wenn xs Liste und x Wert des Basistyps, dann auch x:xs
(Mit eigener Syntax in Haskell)
Rekursive Datenstrukturen wichtig, z.B. zurDarstellung arithmetischer Ausdrücke
3 ist arithmetischer Ausdruck (aA) (5-1) ist aA (5 -1) +3 ist aA Arithmetischer Ausdruck besteht aus
arithmetischen Ausdrücken!
Wie repräsentiert man arithmetische Ausdrücke so, dass sie leicht ausgewertet werden können?
hs / alp1.3 90
Wichtiger rekursiver Datentyp: Baum
Bäume
Baum: Ungerichteter Graph mit den Eigenschaften
(B1) eine Kante verbindet genau 2 Knoten(B2) höchstens eine Kante zwischen 2 Knoten(B3) zusammenhängend: von jedem Knoten kann man jeden anderen über einen Kantenzug erreichen(B4) Der Kantenzug ist eindeutig (d.h. Zwischen zwei Knoten gibt es höchstens einen, mit (B3) genau einen
Ungerichteter Graph: Menge von Knoten K undKanten ⊆ K X K
d
ab
c
e
fa
46
hs / alp1.3 91
Eigenschaften von Bäumen
Weitere Eigenschaften:
(i) Es gibt keine Zyklen (Kantenzüge mit gleichem Anfangs- und Endpunkt (klar wegen (B4) )(ii) Anzahl Knoten = Anzahl Kanten + 1
f
Wurzelbäume... sind Bäume mit einem ausgezeichneten Knoten (der Wurzel)
ab
c
f
ed ab
c
a
d
e
In der Informatikfast immerWurzelbäume
hs / alp1.3 92
Weitere Begriffe
Blatt:Knoten mit nur einer inzidenten Kante ("Anfangs-/Endpunkt
einer Kante ")Vorgänger, Nachfolger von Knoten x:
Knoten y ist Vorgänger von x , wenn er auf Kantenzug von der Wurzel zu x liegt (--> Wurzel Vorgänger von allen Knoten) y direkter Nachfolger von x, wenn (x,y) eine Kante Knoten y ist Nachfolger von x: x ist Vorgänger von y
==> Blätter haben keine Nachfolger
Binärbaum: Baum ist leer (!) oder ein Baum, in dem jeder knoten höchstens zwei direkte Nachfolger hat
47
hs / alp1.3 93
Selbstähnlichkeit von Bäumen
Bäume sind selbstähnlich:
ab
c
a
d
e
bcd
e
Baum enthält Bäume ("Unterbäume")
--> rekursiv definieren!
> data Tree a = Empty | N (Tree a) (Tree a) a
Als algebraischer Datentyp in Haskell:
hs / alp1.3 94
Einige Operationen auf Bäumen
> module Tree where>> data Tree a = Empty | N (Tree a) (Tree a) a > deriving Show> mkTree :: Tree a -> Tree a -> a -> Tree a> mkTree tl tr val = N tl tr val
Hier als Modul: ein Modul erlaubt - die Definition von Programmen in verschiedenen Dateien (gleich benannt wie das Modul !)- "Information Hiding" : unwichtige Definitionen müssen nicht "exportiert" werden (wird hier nicht verwendet)Nutzung eines Moduls: > import <Modulename>
> leftTree :: Tree a -> Tree a> -- retrieves left subtree> leftTree Empty = Empty> leftTree (N l r v) = l
Beispiel:
Main> leftTree (mkTree Empty Empty 27)Empty
48
hs / alp1.3 95
Durchlaufen der Knoten eines Baums
Erste Möglichkeit ("Preorder") : 1. Wurzel
2. Knoten des linken Teilbaums 3. Knoten des rechten Teilbaums
beachte: Unterscheidung links / rechts im Binärbaum wichtig. In Mehrwegbäumen: Anordnung der direkten Nachfolger
Beispiel: a, b, c, d, f, g, e (preorder)
bc
a
de
f
Zweite Möglichkeit ("Postorder") : 1. Knoten des linken Teilbaums
2. Knoten des rechten Teilbaums 3. Wurzel
Beispiel: b, f, g, d, e, c, a (postorder)
g
hs / alp1.3 96
Anwendung: Baumdarstellung arithmetischer Ausdrücke
4
3*
+
+
5 6
Arithmetischer Ausdruck (in erster Näherung): (i) Numerische Konstanten sind arithmetische Ausdrücke (ii) wenn e1 und e2 arithmetische Ausdrücke, dann auch e1 + e2, e1 - e2, e1 * e2, e1 / e2 (iii) wenn e arithmetischer Ausdruck, dann auch (e)
Beispiel: 3+5, 3*3+4, 3*(3+4) , 3+4*3
Beispiel: 3, 5. 17, ... (i)
Dritte Möglichkeit, die Knoten eines Baums zu durchlaufen ("Inorder") :1. Linker Teilbaum2. Wurzel3. Rechter Teilbaum
Beispiel: 3+5+6*4
Beachte: die durch Baumstruktur gegebene implizite Klammerung entspricht nicht dem arithmetischen Ausdruck:3+(5+6) * 4 /= 3+5+(6*4)Vorläufig: explizite Klammerung annehmen:(3 + ((5 + 6) * 4))
49
hs / alp1.3 97
Operatorbäume ...
... Am Beispiel arithmetischer Ausdrücke - Operanden: Gleitkommazahlen- Operatoren: +,-,*,/ (alle zweistellig)
... Repräsentation: Zahl oder Operator sein ==> Vereinigungstyp
> data Token = Opr Char | Oprd Double | Brack Char > deriving (Eq,Show)
Typ Tree a ist polymorph, also:
> type ExpTree = Tree Token -- Typalias für arith.> -- Operatorbäume
Beispiele:N Empty Empty (Oprd 3) -- repräsentiert die Zahl 3beachte: Reihenfolge der Knotenbestandteile: linker Teilbaum,
rechter Teilbaum, Knotenwert
->->
hs / alp1.3 98
...Operatorbäume
Beispiel:
> (N (N Empty Empty (Oprd 3)) > (N > (N (N Empty Empty (Oprd 5))> (N Empty Empty (Oprd 6))> (Opr '+') )> (N Empty Empty (Oprd 4))> (Opr '*')> )> (Opr '+')> )
3*
+
+
5 6
4
Auswertung: Um Operator der Wurzel auswerten zu können, müssen Werte beider Operanden bekannt sein.Dazu: Auswerten der beiden Unterbäume (rekursiv!) Rekursionsanker: Baum mit Unterbäumen Empty und Knotenwert (Oprd x)
50
hs / alp1.3 99
... auswerten
> evalE :: ExpTree -> Double> evalE Empty = error "empty Tree">> evalE (N x y (Opr '+'))> = evalE x + evalE y> evalE (N x y (Opr '-'))> = evalE x - evalE y> evalE (N x y (Opr '*'))> = evalE x * evalE y> evalE (N x y (Opr '/'))> = evalE x / evalE y> evalE (N x y (Oprd n)) = n -- der Rekursionsanker> evalE (N Empty y (Opr '-')) -- hier ist sogar > = - evalE y -- einstelliger Operator > -- erlaubt
hs / alp1.3 100
Zum Beispiel....
>main evalE(N (N Empty Empty (Oprd 3)) (N (N (N Empty Empty (Oprd 5)) (N Empty Empty (Oprd 6)) (Opr '+') ) (N Empty Empty (Oprd 4)) (Opr '*')) (Opr '+'))
47.0
Damit im Prinzip unendlich viele arithmetische Ausdrücke auswertbar - sofern sie als Operatorbaum vorliegen.
u Wie kommt man von einer konkreten Syntax zum Operatorbaum? Konkrete Syntax: z.B. Zeichenkette in Infix-Darstellung 3 + (5+6) * 4 oder: Postfix-Darstellung <-- Baum in Postorder -Folge durchlaufen
3 5 6 + 4 * + (Nachprüfen!) oder Präfix-Darstellung: + 3 * + 5 6 4u Zunächst aber: übersichtliche Ausgabe von Bäumen!
Fortsetzung in Kapitel 4
51
hs / alp1.3 101
Ausgabe von Binären Bäumen (type Tree)
u Um 90° gedreht geht's einfacher: w Beobachtung: Einrücken hängt von Tiefe des Knotens ab
(Tiefe von k = Anzahl Kanten auf Pfad von Wurzel nach k, siehe Übung 8)
w Rekursives Durchlaufen "rechter(!) Teilbaum, Wurzel, linker" liefert Knoten in der Reihenfolge, in der sie ausgegeben werden sollen
u Mitzählen der Höhe, entsprechendes Einrücken und Zeilenwechsel zwischen je zwei Ausgaben leistet das gewünschte
3*
+
+
56
4
hs / alp1.3 102
Einfache Implementierung
> showTreeSimple :: Show a => Tree a -> IO()> showTreeSimple (N l r wert) = putStr ( showTree (N l r wert) 0 )> where> showTree Empty depth > = replicate depth '\t' ++ "[]" ++ "\n "> showTree (N l r wert) depth > = showTree r (depth+1) > ++ replicate depth '\t' ++ show wert ++"\n "> ++ showTree l (depth+1) >
replicate i cListe mit 1 mal Zeichen c
[]
4.0 []
'*' []
6.0 []
'+' []
5.0 [] '+' []
3.0 []
parseTree0 "3+(5+6)*4"
Dahinter steckt showSimpleTreeund der Aufbau desBaums
putStr:: String -> IO()d.h. putStr gibt String aus
52
hs / alp1.3 103
Schönerer Baum
,- [-] ,- 0---< `- [-] ,- 5---< `- [-] ,- 7---< `- [-]|= 9---< ,- [-] ,- 4---< `- [-] `- 1---< ,- [-] ,- 1---< `- [-] `- 6---< `- [-]
Statt interner Darstellung: N (N (N (Empty) (N (Empty) (Empty) 1) 6) (N (Empty) (Empty) 4) 1) (N (Empty) (N (Empty) (N (Empty) (Empty) 0) 5) 7) 9
Programm von Sebastian Koskeauf Web-Server(erweiterte Version von Tree.lhs)
