Listenkomprehension und Typenklassen anhand von Haskell

Proseminar an der TU MünchenMartin Levihn

05.07.2007

GliederungListenkomprehension

Einleitung und Motivation Syntax Beispiele und Arbeitsweise mit einem Generator Beispiele und Arbeitsweise mit mehreren Generatoren Übersetzung von Listenkomprehension

Typklassen Begriffserklärung und Einleitung Deklarationen

Klassendeklaration Kontext eines Typs Instanzen deklarieren Abgeleitete Klassen

Praktische Anwendung Vergleich zu OOP

2

ListenkomprehensionListenkomprehension ähnlich

Mengenbeschreibung in der Mathematik

Erstelle Liste als Beschreibung in Bezug auf eine andere Liste[ x | x <- xs]„Erstelle die Liste aus allen x, wobei x Element

der Liste xs“

3

SyntaxAllgemein [ Ausdruck | q1, q2, … , qk]

Ausdruck kann beliebige Funktion sein

Qualifikatoren q1 bis qk können sein: Generator p <- xs, wobei p Variable / Variablen

Tupel und xs Listenausdruck Test, boolscher Ausdruck zum „Auswählen“

4

Einfache Beispiele (ein Generator)Verdoppeln jedes Elementes in einer Int Liste

double :: [Int] -> [Int]double xs = [ 2*x | x <- xs]

Aufruf double [2,3,4] [4,6,8]

Nur die geraden Werte aus einer Int Liste auswählengerade :: [Int ] -> [ Int]gerade xs = [x | x <- xs, mod x 2 == 0 ]

Aufruf gerade [2,3,4] [2,4]

5

Einfache Beispiele (ein Generator)map :: (a -> b ) -> [a] -> [b] Funktion rekursiv

map f [] = []map f (x:xs) = f x : map f xs

mit Listkomprehensionmap f xs = [ f x | x <- xs]

filter :: (a -> Bool) -> [a] -> [a] Funktion rekursivfilter p [] = []filter p (x:xs) = | p x = x : filter p xs|otherwise = filter p xs

mit Listkomprehensionfilter p xs = [ x | x <- xs, p x]

6

Arbeitsweise allgemein (ein Generator)Format: [f x | x <- xs, p1 x, p2 x , … , pk x]

1) xs wird von links nach rechts durchlaufen2) ist p1 für x erfüllt, teste p2 … pk

a) sind alle „erfüllt“, füge x in Ergebnislisteb) sonst lasse x unberücksichtigt

3) fahre mit nächstem Element fort

7

Einfache Beispiele (mehrere Generatoren)Bilde Tupel (x, y) mit x aus xs und y aus ys

pairs :: [a] -> [b] -> [(a, b)]pairs xs ys= [ (x,y)| x <- xs, y <- ys]

Aufruf pairs [1,2,3] [4,5] [(1,4), (1,5), (2,4), (2,5), (3,4), (3,5)]

Bilde pythagoräische Triple pyTriple n :: Int -> [(Int,Int, Int)]pyTriple n = [ (x, y, z) | x <- [2 .. n], y<-[x .. n], z<-

[y .. n], x*x+y*y == z*z]

Aufruf pyTrible 15 [(3,4,5),(5,12,13),(6,8,10),(9,12,15)]

8

Arbeitsweise Allgemein (mehrere Generatoren)Format: [ f x | x <- xs, y <- ys , ... z <- zs, p1 , ... pk]

1) erste Element von xs wird x zugewiesen2) für dieses feste x wird das erste y von ys zugewiesen

usw.3) für diese festen Werte wird z nun von links nach

rechts durchlaufen und die Tests werden duchgeführt4) es wird der Wert vor dem z erhöht usw.

anschaulich: for (int i1=0; i1<length(xs); i1++){

for (int i2=0; g1<length(ys); i2++){ ….

for(int in=0; in<length(zs); in++){ ….}…}}

9

Übersetzung von Listenkomprehension[e | True ] [e][e | t, Q] if t then [e | Q] else [][e | p<- xs, Q] concatMap fq xs where fq p = [e | Q]

concatMap:: (a -> [b]) -> [a] -> [b]concatMap f [] = []concatMap f (x:xs) = f x ++ concatMap f xs

10

Übersetzung von Listenkomprehension

pyTriple n = [ (x, y, z) | x <- [2 .. n], y<-[x .. n], z<-[y .. n], x*x+y*y == z*z]

pyTriple n = concatMap f1 [2 .. n]where f1 x = concatMap f2 [x .. n]where f2 y = concatMap f3 [y .. n]where f3 z = if (x*x + y*y == z*z) then [(x,y,z)]

else []

11

TypenklassenPolymorphismus

ist, wenn eine Funktion unabhängig von dem Datentyp arbeitet:length :: [a] -> Intlength []= 0length (_:xs) = 1 + length xs

Ad-hoc Polymorphismusim Sinne von Überladen. Es also für gleichen Operator

unterschiedliche Implementierungen gibt (Beispiel + Operator in Java)

Hindley-Milner TypsystemTypinferenzen werden vom System automatisch erkannt

-> typisiertes Lambda-Kalkühl

12

TypklassenOperationen nur auf Typen mit einer

gewissen SemantikBeispiel:

elem :: a -> [a] -> Boolelem x [] = Falseelem x (y:ys) = (x==y) || (elem x ys)

nur möglich wenn == für a definiertMittelweg zwischen Polymorphismus und

Monomorphismus

13

Klassendeklaration class Eq a where (==) :: a -> a -> Bool

Name der Klasse (Eq)Signatur der Klasse („fordert“ das (==)

implementiert ist)

class Name a where ...verlangte Singnatur...

14

Kontext eines Typs alleQual :: Int -> Int -> Int -> Bool allEqual m n p = (m==n) && (n==p)keine Beschränkung auf Int sondern auf ==,

Verallgemeinerung: alleQual :: Eq a => a -> a -> a -> BoolallEqual m n p = (m==n) && (n==p)

Bereich vor dem => heißt Kontext„Wenn der Typ a in der Kasse Eq ist, dann hat

allEqual den Typ a -> a -> a -> Bool.“

15

Kontext eines TypsListe aus Tupeln soll auf dem ersten Wert

sortiert werden und die zweiten Werte sollen ausgegeben werden.Hakell Prelude bietet Klasse Ord, definiert

Vergleichsoperatoren,sowie Visible:

class Visible a wheretoString :: a -> Stringsize :: a -> Int

16

Kontext eines Typsgeforderte Funktionalität durch Kontext

sichergestellt:

bSort :: (Ord a, Visible b) => [(a, b)] -> a -> String

Verletzen der constraints : nachfolger :: Int -> Int nachfolger = (+1)

Aufruf allEqual nachfolger nachfolger nachfolger ERROR: Int -> Int is not an instance of class “Eq”

17

Instanz einer Klasse Um einen Typ als Instanz einer Typklasse zu

deklarieren, müssen die in der Signatur geforderten Funktionen implementiert werden

Beispiel Bool als Instanz von Eq deklarieren: instance Eq Bool where True==True = True False==False = True _ == _ = False

18

Instanz einer Klasse Gleichheitstest auf Listen definieren

instance Eq [a] where[] == [] = Truex:xs == y:ys = x==y && xs==ys_ == _ = False

Ist == definiert?

19

Instanz einer Klasse Gleichheitstest nur auf Liste definiert,

deren Elemente selbst Instanzen von Eq sind

instance Eq a => Eq [a] where[] == [] = Truex:xs == y:ys = x==y && xs==ys_ == _ = False

können == als gegeben voraussetzen

20

Abgeleitete KlassenEine Art Vererbung

class Eq a => Ord a where(<), (<=), (>), (>=) :: a -> a -> Boolmax, min :: a -> a -> Boolcompare :: a -> a -> Orderingx <= y = (x < y || x==y)x > y = y < x

Eine Abgeleitete Klasse kann ebenfalls mehrere Basisklassen haben class (Num a, Ord a) => Real a where...

21

Praktische Anwendungdata Tag = So | Mo | Di | Mi | Do | Fr | SaUm Vergleiche zu machen, deklarieren wir Tag als Instanz

von Eq und OrdFühren Vergleich auf Vergleich von Ints zurück:

class Enum a wherefromEnum :: a -> InttoEnum :: Int -> a

instance Enum Tag wherefromEnum So = 0fromEnum Mo = 1fromEnum Di = 2...

toEnum analog22

Praktische Anwendunginstance Eq Tag where(x==y) = (toEnum x == toEnum y)

instance Ord Tag where(x<y) = (toEnum x < toEnum y)

Da dies ein häufiges Vorgehen ist, bietet Haskell dazu die Kurzschreibweise:data Tag = So | Mo | Di | Mi | Do | Fr | Sa deriving(Enum, Eq, Ord)

Instanzen werden automatisch erstellt

23

Vergleich zu OOPGemeinsamkeiten:

Um Instanz zu werden, sind Implementierungen nötig Interfaces in Java oder Basisklassen in C++ in C++ Default-Implementierungen

Selbstdefinierte Typen können auf Standardoperationen implementiert werden

24

Vergleich zu OOPUnterschiede

starke Trennung von Typdeklarationen, Typklassen- und InstanzdeklarationenHaskell: Klasse ist Sammlung von TypenC++ : Typen und Klassen synonym kein Zustand eines Objekts möglich

Kein dynamic binding möglich In OOP möglich

show :: ShowType -> String Bools , Chars wären sub-classes, [True, 'n', False] ::[ShowType]

In Java sind die implementierten Interfaces/Klassen bei der Klassendefinition anzugeben, bei Haskell späteres Hinzufügen möglich

25

Literatur [1] Simon Thompson, 1999. The Craft of Functional Programming,

second edition, Addison Wesley Longman, Great Britain [2] Richard Bird, 1998. Introduction to Functional Programming

using Haskell, second edition, Prentice Hallo, Great Britain [3] The Haskell 98 Report, December 2002,

http://www.haskell.org/onlinereport/exps.html#list-comprehensions

[4] D. Rösner, 2007. Einführung in Programmierparadigmen, Univ. Magedburg, http://wdok.cs.uni-magdeburg.de/studium-und-lehre/ lehrveranstaltungen/sommer2007/pgp/slides

[5] Uwe Schmidt, 2002. Abstrakte Datentypen und das Typsystem von Haskell, FH Wedel, http://www.fh-wedel.de/~si/seminare/ss02/Ausarbeitung/2. types/typhas3.html

[6] Peter Padawitz, 2005. Übersetzerbau, Univ. Dortmund http://fldit-www.cs.uni-dortmund.de/~peter/Kapitel1-2.pdf

26