homeSoftwaredesign Softwaredesign: Mengen und Verzeichnisse Prof. Dr. Uwe Schmidt FH Wedel

Mengen und Verzeichnisse


weiter

Mengen

Potenzmenge
Sei t eine Variable für einen Datentyp
Set t
ist der Wertebereich aller endlichen Mengen
mit Elementen vom Typ t
weiter
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)

weiter

Verzeichnisse, Tabellen, endliche Abbildungen, Maps

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
weiter
merke
Verzeichnisse sind spezielle Mengen
merke
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
merke
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
merke
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, ...
merke
Felder können durch Maps modelliert werden.
merke
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}
merke
Listen können durch Maps modelliert werden.
In Datenbanken von Bedeutung.
merke
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)
gut
Felder und Relationen sind Spezialfälle von Maps

Letzte Änderung: 13.04.2012
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel