3.4 Typdefinitionen

Typabkürzungen. Hier werden neue Namen als Abkürzungen für komplexe, evtl. parametrisierte Typausdrücke eingeführt. Hier gibt es keinen speziellen semantischen Gehalt. Diese Typen werden auch transparente Typen genannt. Alle Auftreten des neuen Typnamens sind äquivalent zu seinem definierenden Ausdruck.

- type intpair = int * int;
type  intpair = int * int
- fun f(x:intpair) = let val (l,r)=x in l end;
val f = fn : intpair -> int
- f(3,2);
val it = 3 : int
- type 'a pair = 'a * 'a;
type  'a pair = 'a * 'a
- type boolpair = bool pair;
type  boolpair = bool pair

Neue Datentypen. In Datentypdeklarationen können neue (rekursive, polymorphe) Typen von Konstruktortermen definiert werden. Folgende Definitionen führen 3 nullstellige Konstruktoren für einen neuen Typ color ein bzw. zeigen, wie man den vordefinierten Typ bool selbst definieren könnte.

- datatype color = red | green | blue;
datatype  color
  con blue : color
  con green : color
  con red : color
- red;
val it = red : color
- datatype bool = true | false;
datatype  bool
  con false : bool
  con true : bool
val like = fn : color -> bool
- fun like red = true
=   | like green = false
=   | like blue = true;
val like = fn : color -> bool
- like blue;
val it = true : bool

Wir sehen, daß Typdefinitionen dieser Art den Aufzählungstypen von Pascal entsprechen. Konstruktoren müssen nicht nullstellig sein:

type  rbg_color = color
- datatype cmy_color = cyan | magenta | yellow;
datatype  cmy_color
  con cyan : cmy_color
  con magenta : cmy_color

  con yellow : cmy_color
- datatype color = rbg of rbg_color | cmy of cmy_color;
datatype  color
  con cmy : cmy_color -> color
  con rbg : rbg_color -> color

Hier ist rbg ein Konstruktor vom Typ rbg color -> color und cmy ein Konstruktor vom Typ cmy color -> color. Zusammen bilden sie alle Möglichkeiten, Terme vom (redefinierten) Typ color zu konstrieren.

Wir kommen nun zu rekursiven Typen und definieren als erstes (unmarkierte) Binärbäume.

- datatype btree = empty | leaf | node of btree * btree;
datatype  btree
  con empty : btree
  con leaf : btree
  con node : btree * btree -> btree
- fun countleaves(empty) = 0
    | countleaves( leaf) = 1
    | countleaves(node(subtree1,subtree2)) =
                 countleaves(subtree1)+countleaves(subtree2);
val countleaves = fn : btree -> int
- countleaves(node(node(leaf,leaf),leaf));
val it = 3 : int

Es ist nur natürlich, daß Funktionen auf rekursiven Datentypen selbst rekursiv sind und daß die Rekursionen oft parallel verlaufen. Mathematisch steht hier das Prinzip der strukturellen Induktion im Raum, welches wir im Abschnitt ?? rekapitulieren wollen.

Als nächstes Beispiel zeigen wir, wie wir die Listen selbst definieren können.

- datatype 'a list = nil | :: of 'a * 'a list;
datatype  'a list
  con :: : 'a * 'a list -> 'a list
  con nil : 'a list

Da es sich hier um einen polymorphen Typ handelt, müssen wir den Parameter auf der linken Seite der Typdeklaration ebenfalls angeben. list ist also ein Typkonstruktor, der aus Argumenttypen α Listen typen αlist konstruiert. Hier eine Variation der Binärbäume so, daß sie an Blättern Information tragen.

- datatype 'a tree = empty | leaf of 'a | node of 'a tree * 'a tree;
datatype  'a tree
  con empty : 'a tree
  con leaf : 'a -> 'a tree
  con node : 'a tree * 'a tree -> 'a tree
- fun frontier empty = []
    | frontier (leaf(x)) = [x]
    | frontier (node(t1,t2)) = append (frontier(t1),frontier(t2));
val frontier = fn : 'a tree -> 'a list
- frontier(node(leaf("a"),node(node(leaf("b"),empty),leaf("a"))));
val it = "a" :: "b" :: "a" :: nil : string list

Abstrakte Datentypen Abstrakte Datentypen verstecken die Implementierungsstruktur von Daten. Hierdurch werden Impementierungsaspekte unabhängig von der Verwendung des Typs. Insbesondere kann die Implementierung geändert werden, ohne daß Anwendungen reimplementiert werden müssen, solange die exportierten Funktionen des Typs, genannt die Schnittstelle, sich in ihren beobachtbaren Eigenschaften nicht ändern. Wir machen ein Beispiel, in dem 4-Bit RGB-Farben definiert werden.

abstype color = blend of int*int*int
with val white = blend(0,0,0)
      and   red = blend(15,0,0)
      and green = blend(0,15,0)
      and  blue = blend(0,0,15)
      fun mix(parts:int,blend(r,g,b),parts':int,blend(r',g',b')) =
      if parts<0 orelse parts'<0 then white
      else let val tp=parts+parts'
               val rp = ((parts*r+parts'*r') div tp) mod 16
               and gp = ((parts*g+parts'*g') div tp) mod 16
               and bp = ((parts*b+parts'*b') div tp) mod 16
            in blend(rp,gp,bp)
           end
end;
type color
val white = - : color
val red = - : color
val green = - : color
val blue = - : color
val mix = fn : int * color * int * color -> color
- val black = mix(1,red,1,mix(1,green,1,blue));
val black = - : color

Man beachte:

• Die Typgleichung hinter ”abstype“ hat dieselbe Syntax, wie die, die wir vorher kennengelernt haben. Also können hier auch neue Typkonstruktoren eingeführt werden.

• Die nach außen sichtbare Schnittstelle des abstrakten Datentyps besteht aus dem Namen des Typs und den Namen der zwischen with und end eingeführten Werte und Funktionen.

• Die Implementierung der Schnittstellenobjekte bleibt verborgen. Technisch bedeutet das insbesondere, daß der Typ verschieden ist von allen anderen Typen und daß seine Konstruktoren außen nicht sichtbar sind. Daher kann man insbesondere keine musterorientierten Funktionen auf einem abstrakten Type schreiben. Zudem ist die Gleichheit = nicht definiert für Werte eines abstrakten Datentyps. Soll es eine Gleichheitsfunktion geben, so muß man die implementieren und in der Schnittstelle zur Verfügung stellen.

• Innerhalb der Definition Abstrakten Datentyps sind die Konstruktoren natürlich sichtbar und können zu musterorientierten Definitionen verwendet werden.

Diese Art von abstrakten Datentypen in SML ist historisch bedingt und sollte angesichts der erweiterten Möglichkeiten von Abstraktion mit Hilfe der Konzepte von Strukturen und Funktoren eigentlich nicht mehr verwendet werden.