Funktionale Programmierung: Produkt- und Summen-Datentypen

Literatur

LYAH:
Tuples

Paare

kartesisches Produkt: A×B

Definition

data Pair a b = MkPair a b

polymorpher Datentyp

Datentyp mit Typparameter

Pair besitzt genau einen Konstruktor

Der Konstruktor ist eine Funktion mit 2 Parametern

MkPair :: a -> b -> Pair a b

Konvention

Konstruktoren beginnen immer mit einem Großbuchstaben

Konstruktoren dürfen in Mustern auftreten

Notation

vertrauter: Paar-Schreibweise (x, y)

(A, B)          -- der Wertebereich aller Paare
 
(x, y)          -- ein Paar

elementare Operationen

fst             :: (a, b) -> a
fst (x, y)      =  x
 
snd             :: (a, b) -> b
snd (x, y)      =  y

Werte

⊥
(⊥, ⊥)
(⊥, y)
(x, ⊥)
(x, y)

Anzahl Werte

data A  = A1 | A2 | ... | An
data B  = B1 | B2 | ... | Bm
 
type P  = (A, B)

Wieviele Werte besitzt P?

CPO für (Bool, Bool) ?

Beispiele

für Funktionen mit Paaren

pair            :: (a -> b, a -> c) -> a -> (b, c)
pair (f, g) x   =  (f x, g x)
 
cross           :: (a -> b, c -> d) -> (a, c) -> (b, d)
cross (f, g)    = pair (f . fst, g . snd)

cross

ist eine nichtstrikte Funktion

cross (f, g) ⊥ = (f ⊥, g ⊥)

Beweis

	cross (f,g) ⊥
=	{ definition cross }
	pair (f . fst, g . snd) ⊥
=	{ Definition pair }
	((f .fst) ⊥, (g . snd) ⊥)
=	{ Definition . }
	(f (fst ⊥), g (snd ⊥))
=	{ Striktheit von fst, snd }
	(f ⊥, g ⊥)

Eigenschaften
Gesetzte

für cross und pair

fst . pair (f, g)          = f
snd . pair (f, g)          = g
 
pair (f, g) . h            = pair (f . h, g . h)
cross (f, g) . pair (h, k) = pair (f . h, g . k)

Beweis der letzten Gleichung

	cross (f, g) . pair (h, k)
=	{ definition cross }
	pair (f . fst, g . snd) . pair (h, k)
=	{ 3. Gleichung }
	pair (f . fst . pair (h, k), g . snd . pair (h, k))
=	{ 1. und 2. Gleichung }
	pair (f . h, g . k)

Vergleiche von Paaren

instance (Eq a, Eq b) => Eq (a, b) where
  (x, y) == (u, v)  =  (x == u) && (y == v)
 
instance (Ord a, Ord b) => Ord (a, b) where
  (x, y) < (u, v)   =  (x < u) || (x == u && y < v)

gegeben

(1, undefined) < (2, undefined) = ?

Resultat

gegeben

(undefined, 1) < (undefined, 2) = ?
(undefined, 1) < (3,         2) = ?
(3,         1) < (undefined, 2) = ?

Resultat

Operatoren

für pair und cross: mit Currying

(&&&)   :: (a -> b) -> (a -> c) -> a -> (b, c)
(&&&)   = curry pair
 
(***)   :: (a -> b) -> (c -> d) -> (a, c) -> (b, d)
(***)   = curry cross
 
-- definiert in Control.Arrow

Wie definiert man einen Datentyp für Tripel und Quadrupel?

Definition	Vereinigung zweier Datentypen
	data Either a b = Left a \| Right b

	polymorpher Datentyp
	2 Konstruktor-Funktionen
	Left :: a -> Either a b Right :: b -> Either a b

Werte	⊥ Left ⊥ Left x Right ⊥ Right y

Beispiel	für eigenen Summentyp mit eigenen Konstruktoren
	data BoolOrChar = B Bool \| C Char

?	Wieviele Werte besitzt BoolOrChar oder Either Bool Char ?
	(2 + 1) + (# chars + 1) + 1

?	CPO für Either Bool Char ?

Funktionen	auf Either
	either :: (a -> c) -> (b -> c) -> Either a b -> c either f g (Left x) = f x either f g (Right y) = g y plus :: (a -> c) -> (b -> d) -> Either a b -> Either c d plus f g = either (Left . f) (Right . g)

?	Punktweise Definition von plus?
	-- einsetzen von either und . plus f g (Left x) = Left (f x) plus f g (Right y) = Right (g y)

Eigenschaften Gesetze	für either und plus
	either f g . Left = f either f g . Right = g h . either f g = either (h . f) (h . g) either f g . plus h k = either (f . h) (g . k)

	in Data.Either ist either vordefiniert
	Analogie zu den Eigenschaften von pair und cross?

Vergleiche	auf Summendatentypen
	instance (Eq a, Eq b) => Eq (Either a b) where Left x == Left y = (x == y) Left x == Right y = False Right x == Left y = False Right x == Right y = (x == y) instance (Ord a, Ord b) => Ord (Either a b) where Left x < Left y = (x < y) Left x < Right y = True Right x < Left y = False Right x < Right y = (x < y)

automatische Erzeugung	data Either a b = Left a \| Right b deriving (Eq, Ord)

?	Summendatentyp für drei Typen a, b, c?
	data Sum3 a b c = Case1 a \| Case2 b \| Case3 c

Sonderfall	optionaler Datentyp: Entweder ein Wert oder Nichts
	data Maybe a = Nothing \| Just a deriving (Eq, Ord)

?	Anzahl Werte?
	# Werte in a + 1 + 1

?	Analoge Funktionen zu either und plus?

maybe	analog zu either, nur mit Currying vordefiniert
	maybe :: c -> (b -> c) -> Maybe b -> c maybe x f Nothing = x maybe x f (Just y) = f y
just	analog zu plus
	just :: (b -> d) -> Maybe b -> Maybe d just f Nothing = Nothing just f (Just x) = Just (f x)
	just ist vordefiniert als fmap
Funktor	Maybe wird durch fmap zu einem Funktor (Vorwärtsreferenz)