Grundlagen der Funktionalen Programmierung: Typen und Klassen

Definition	Ein Typ bestimmt eine Menge von Werten.

Beispiel
Typ	Bool
Wertemenge	{False, True}
Notation	v :: T
	Die Variable v besitzt den Typ T
2. Beispiel
Typ	Bool -> Bool
Wertemenge	Alle einstelligen Funktionen über den Wahrheitswerten
	False :: Bool True :: Bool not :: Bool -> Bool
Notation	e :: T
	Der Ausdruck e besitzt den Typ T
	not False :: Bool not True :: Bool not (not False) :: Bool

Prinzip	Jeder Ausdruck e besitzt einen Typ T.
	T kann statisch (vor der Auswertung von e) berechnet werden.
	Diese Berechnung heißt Typ-Inferenz
Schlüssel	Regel zur Typ-Inferenz von Funktionsanwendungen

Konsequenz	Haskell ist typsicher
	Es gibt bei der Auswertung von Ausdrücken keine Typfehler
	Eine große Klasse von Fehlern kann so vor der Ausführung eines Programmms erkannt werden

Einfache Datentypen

Vordefiniert
Bool	{False, True}
Char	Zeichen (Unicode) {'a', 'b', ... '0', '1',...}
String	Zeichenreihen (Listen) über Char
Int	ganze Zahlen mit durch die Maschinenarchitektur beschränktem Wertebereich zum Beispiel {-2^63 .. 2^63-1}
Integer	ganze Zahlen ohne Einschränkung des Wertebereichs
Float	Fließkomma-Zahlen mit einfacher Genauigkeit
Double	Fließkomma-Zahlen mit doppelter Genauigkeit

Werte-Definitionen	Namen für Werte
Syntax	name :: Typ name = Ausdruck
Syntax	one :: Int one = 1 dieAntwort :: Integer dieAntwort = 6 * (3 + 4)
	Ein Haskell-Programm besteht aus einer Menge von Werte-Definitionen

Listen-Typen

Definition	Eine Liste besteht aus einer Folge von Elementen. Die Elemente besitzen alle den gleichen Typ.
Syntax	[False, True] :: [Bool] ['a','b','c'] :: [Char] -- String "abc" :: [Char] ["1", "2", "xyz"] :: [[Char]] -- [String] [] :: [a] -- ???

Tupel-Typen

Definition	Ein Tupel besteht aus einer endlichen Folge von Komponenten. Diese können von unterschiedlichen Typen sein.
Syntax	(False, True) :: (Bool, Bool) (False, 'a', one) :: (Bool, Char, Int) ("ja", True, 'a') :: ([Char], Bool, Char) ('a', (False, 'b')) :: (Char, (Bool, Char)) ([one, 2, 3], "xyz") :: ([Int], [Char])

Funktions-Typen

Definition	Eine Funktion ist eine Abbildung von Argumenten eines Typs auf Resultate eines (möglicherweise anderen) Typs.
Beispiele	vordefinierte Funktionen
	not :: Bool -> Bool isDigit :: Char -> Bool elem :: Char -> [Char] -> Bool
Funktionen	ohne Namen
	λ x -> x + 1 :: Int -> Int λ c -> c `elem` ['0'..'9'] :: Char -> Bool λ n -> [0..n] :: Int -> [Int]
Funktionen	mit Namen
	succ :: Int -> Int succ = λ x -> x + 1 isDigit :: Char -> Bool isDigit = λ c -> c `elem` ['0'..'9'] zeroTo :: Int -> [Int] zeroTo = λ n -> [0..n]
bequemere Syntax
	succ :: Int -> Int succ x = x + 1 isDigit :: Char -> Bool isDigit c = c `elem` ['0'..'9'] zeroTo :: Int -> [Int] zeroTo n = [0..n]
	Gleiche Bedeutung wie in der ersten Definition
	ASCII-Zeichen für λ: \

Regel	beim Entwickeln: Erst den Funktionstyp (Signatur) festlegen, dann die Funktionsdefinition
	Funktionen funktionieren nicht immer!
Definition	Eine Funktion ist total (vollständig) definiert, wenn sie für jeden Wert aus dem Argumenttyp einen Wert aus dem Resultattyp berechnet.
Definition	Eine Funktion ist partiell (nicht vollständig) definiert, wenn sie nicht total definiert ist.
Regel	beim Entwickeln: Partielle Funktionen dürfen nie mit Argumenten aufgerufen werden, für die die Funktion nicht definiert ist.
	Vor einem Aufruf einer partiellen Funktion muss sicher gestellt sein, dass die Funktion für das Argument definiert ist.
Beispiele	für partielle Funktionen
	head :: [a] -> a head (x : xs) = x head [] = error "head of empty list" -- tail analog div :: Int -> Int -> Int div x 0 = error "division by zero" div x y = ...

Funktionen mit mehreren Parametern
Vereinfachung	Zurückführen auf Funktionen mit einem Parameter

1. Lösung	Alle Argumente zu einem Tupel zusammen fassen
Beispiel	Addition
Funktions-Definition	add :: (Int, Int) -> Int add = λ (x, y) -> x + y
	Zugriff auf die formalen Parameter durch Zugriff auf Komponenten eines Tupels
Funktions-Aufruf	add (1, 2) -- 3
	Beim Aufruf Konstruktion eines Tupels. Alle Parameter werden zu einem Zeitpunkt übergeben.
	Wie bei C, Pascal, Java, ...

2. Lösung	"curried"-Funktionen
	benannt nach Haskell Curry
Idee	n-stellige Funktionen mit n > 1 zurückführen auf (n-1)-stellige Funktionen
Beispiel	Addition
Funktions-Definition	add' :: Int -> (Int -> Int) add' = λ x -> (λ y -> x + y)
	direkter Zugriff auf die formalen Parameter
Funktions-Aufruf	(add' 1) 2 -- schrittweises Aufrufen add' 1 :: Int -> Int add' 1 = λ y -> 1 + y (add' 1) 2 :: Int (add' 1) 2 = 1 + 2 -- 3 succ :: Int -> Int succ = add' 1 succ 2 :: Int succ 2 = 1 + 2 -- 3
	Bei Aufruf mit dem 1. Parameter wird eine Funktion berechnet. Beim Aufruf dieser Funktion mit dem 2. (dem letzten) Parameter findet die eigentliche Auswertung der Addition statt.
	Die Parameter können zu unterschiedlichen Zeitpunkten übergeben werden.
	Flexibilität, Erweiterbarkeit, Wiederverwendbarkeit
Beispiel	decr :: Int -> Int decr = add' (-1)

Syntax	Konventionen
.1	Funktionspfeil -> ist rechtsassosiativ
.2	λ-Parameter links vom =
.3	Parameterübergabe linksassoziativ

Beispiel	mal3 :: Int -> (Int -> (Int -> Int)) mal3 = λ x -> (λ y -> (λ z -> x * y * z)) ((mal3 2) 3) 5 -- wird zu mal3 :: Int -> Int -> Int -> Int mal3 x y z = x * y * z mal3 2 3 5

Typkonstruktoren

Konstruktion	von Problem-spezifischen Datentypen
	aus vordefinierten einfachen Typen durch Kombination von [], (,), (,,), ... und -> (Listen-, Tupel-, Funktions-Konstruktoren)
Definition	[], (,), (,,), (,,,), ..., -> heißen Typkonstruktoren

Polymorphe Datentypen

Polymorphie	griechisch: Vielgestaltigkeit
Beispiel	length [1, 2, 3] length ["ja", "nein"] length []
?	Typ von length
	length :: [a] -> Int
Definition	Typen mit Typvariablen heißen polymorphe Typen
Beispiele	Vordefinierte Funktionen
	fst :: (a, b) -> a snd :: (a, b) -> b null :: [a] -> Bool head :: [a] -> a (:) :: a -> [a] -> [a] (++) :: [a] -> [a] -> [a] take :: Int -> [a] -> [a] id :: a -> a const :: a -> b -> a map :: (a -> b) -> [a] -> [b] zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

Überladene Datentypen

Motivation	(+) berechnet die Summe zweier Zahlen des gleichen Typs
?	Typ von (+)
	(+) :: Int -> Int -> Int (+) :: Integer -> Integer -> Integer (+) :: Double -> Double -> Double (+) :: a -> a -> a

Lösung	Typ-Klassen (kurz: Klassen)
Definition	Eine Typ-Klasse ist ein Name für eine Schnittstelle. Eine Schnittstelle enthält eine Menge von Funktions-Deklarationen
Definition	Ein Typ ist eine Instanz einer Typ-Klasse, wenn er die Funktionen der Schnittstelle implementiert.
Beispiel	Num ist eine Typ-Klasse, die die Funktionen (Operatoren) (+), (-), (*), negate, abs, signum enthält
	(+) :: Num a => a -> a -> a
Definition	Ein Typ, der eine Klassen-Einschränkung (class constraint) enthält, ist ein überladener Typ
Elementare Klassen	class Eq a where (==) :: a -> a -> Bool (/=) :: a -> a -> Bool class Eq a => Ord a where compare :: a -> a -> Ordering (<) :: a -> a -> Bool (<=) :: a -> a -> Bool (>) :: a -> a -> Bool (>=) :: a -> a -> Bool max :: a -> a -> a min :: a -> a -> a class Num a where (+) :: a -> a -> a (-) :: a -> a -> a (*) :: a -> a -> a negate :: a -> a abs :: a -> a signum :: a -> a fromInteger :: Integer -> a

	Alle elementaren Typen (Bool, Char, Int, Integer, Float, Double, ...) besitzen eine Instanz von Eq und Ord
	Alle Listen-Typen, deren Element-Typ eine Instanz von Eq und Ord besitzt, besitzen eine Instanz von Eq und Ord
	Alle Tupel-Typen, deren Komponenten-Typen Instanzen von Eq und Ord besitzen, besitzen eine Instanz von Eq und Ord
	Funktions-Typen und Typen, die Funktions-Typen enthalten, besitzen keine Instanz von Eq und Ord

Ausgabe und Konversion in Strings	mit einer Typklasse Show
	class Show a where show :: a -> String
	Alle Typen, deren Werte ausgegeben werden sollen, benötigen eine Instanz von Show
	Alle elementaren Typen (Bool, Char, Int, Integer, Float, Double, ...) besitzen eine Instanz von Show
	Alle Listen-Typen, deren Element-Typ eine Instanz von Show besitzt, besitzen eine Instanz von Show
	Alle Tupel-Typen, deren Komponenten-Typen Instanzen von Show besitzen, besitzen eine Instanz von Show
	Funktions-Typen und Typen, die Funktions-Typen enthalten, besitzen keine Instanz von Show

Eingabe und Konversion aus Strings	mit einer Typklasse Read
	read :: Read a => String -> a
	Alle Typen, deren Werte aus Zeichenreihen (Strings) konstruiert werden sollen, müssen eine Instanz von Read besitzen.
	Alle elementaren Typen (Bool, Char, Int, Integer, Float, Double, ...) besitzen eine Instanz von Read
	Alle Listen-Typen, deren Element-Typ eine Instanz von Read besitzt, besitzen eine Instanz von Read
	Alle Tupel-Typen, deren Komponenten-Typen Instanzen von Read besitzen, besitzen eine Instanz von Read
	Funktions-Typen und Typen, die Funktions-Typen enthalten, besitzen keine Instanz von Read

Beispiele zum Kapitel

module Types
where
-- ----------------------------------------
l1 = [False, True]
l2 = ['a', 'b', 'c']
l3 = ["abc", "xyz", "123"]
l4 = []
-- ----------------------------------------
p1 = (False, True)
p2 = (False, 'a', True)
p3 = ("ja", True, 'a')
-- ----------------------------------------
c1 = ('a', (False, 'b'))
c2 = (['a'],['b'])
c3 = [("abc", False)]
-- ----------------------------------------
add :: (Int, Int) -> Int
add = \ (x,y) -> x + y
add' :: Int -> (Int -> Int)
add' = \ x -> (\ y -> x + y)
add'' :: Int -> Int -> Int
add'' x y = x + y
zeroto :: Int -> [Int]
zeroto = \ n -> [0 .. n]
mul3 :: Int -> (Int -> (Int -> Int))
mul3 = \ x -> (\ y -> (\ z -> x * y * z))
mul3' :: Int -> Int -> Int -> Int
mul3' x y z = x * y * z
mul2 = mul3 2
succ' = add' 1
pred' = add' (-1)

Typen und Klassen

Grundlagen

Einfache Datentypen

Listen-Typen

Tupel-Typen

Funktions-Typen

Typkonstruktoren

Polymorphe Datentypen

Überladene Datentypen

Beispiele zum Kapitel

Die Quelle