Softwaredesign: Mengen und Verzeichnisse

Potenzmenge	Sei t eine Variable für einen Datentyp
Set t	ist der Wertebereich aller endlichen Mengen mit Elementen vom Typ t

Beispiele
Typen	Set Bool Set Int Set Item {- oder -} Set (String, Int) Set (Set Bool)
Werte	{}, {False}, {True}, {False, True} {}, {1,2,3,4} {("abc",123)} {}, {{}}, {{False}}, {{False}, {False, True}}
vordefinierte Funktionen	==, /=, ∈, ∩ ∪ ... {f x \| x ∈ m} {f x \| x ∈ m, p x}
Implementierung	in Haskell
	im Gegensatz zu Listen nicht in der Sprache vordefiniert, sondern in einem Modul der Basisbibliothek vordefiniert.
	type Set a = ... -- implementation is hidden
Relationstypen	Relationen sind Mengen von Tupeln
	Relationstypen können also durch Kombination von Set und (,) gebildet werden
Beispiel	Set (Int, Int) Set (String, Int, Double)

Maps	Seien k und v Variablen für Datentypen (Wertebereiche)
Map k v	ist der Wertebereich aller Maps mit Schlüssel vom Typ k mit Wert (Attribut) vom Typ v

	Verzeichnisse sind spezielle Mengen
	Sie werden aber so häufig verwendet, dass es sich lohnt, sie extra zu behandeln
	type Map' k a = Set (k, a) invMap' :: Set (k, a) -> Bool invMap' m = ∀ (k1,a1) ∈ m ⋅ ∀ (k2,a2) ∈ m ⋅ k1 == k2 => a1 == a2
	Zusätzliche Konsistentbedingungen werden durch Datentyp-Invarianten beschrieben.
	Solche Invarianten sind Funktionen von einem Wertebereich in die Wahrheitswerte
	Eine mögliche Definition
	type Invariant a = a -> Bool
	Die im Beispiel verwendete Notation ist eine mathematische, nicht die Standard-Haskell Notation, sie kann aber 1-1 in Haskell umgesetzt werden
	invMap' :: (Eq k, Eq a) => Set (k, a) -> Bool invMap' m = and [ not (k1 == k2) \|\| a1 == a2 \| (k1, a1) <- elems m, (k2, a2) <- elems m ]
Implementierung	analog zu Mengen
	im Gegensatz zu Listen nicht in der Sprache vordefiniert, sondern in einem Modul der Basisbibliothek vordefiniert.
	type Map k v = ... -- implementation is hidden
Beispiele
Typen	Map String Int Map Int Bool Map String (Int -> Int)
Werte	{ "abc" :-> 25, ... } { 1 :-> False, 2 :-> True, ...} { "sqr" :-> \x -> x * x }
vordefinierte Operationen	wie bei den Mengen, außerdem noch lookup, insert, keys, ...
	Felder können durch Maps modelliert werden.
	Der Schlüssel ist der Index.
	-- Pascal Syntax type A = array[min..max] of String type A = Map Int String invA :: Map Int String -> Bool invA m = keys m == {min .. max}
	Listen können durch Maps modelliert werden. In Datenbanken von Bedeutung.
	Relationen mit einer Schlüsselkomponente können durch Maps modelliert werden.
	type Rel = Set (Name, SurName, Age, Salary) -- die ersten beiden Komponenten bilden den Schlüssel -- die letzen beiden die funktional abhängigen Attribute type Rel = Map (Name, SurName) (Age, Salary)
	Felder und Relationen sind Spezialfälle von Maps

Mengen und Verzeichnisse

Mengen

Verzeichnisse, Tabellen, endliche Abbildungen, Maps