Stand: 23.11.2000
© 2001 François Bry
Dieses Lehrmaterial wird ausschließlich zur privaten Verwendung
angeboten. Eine nichtprivate Nutzung (z.B. im Unterricht
oder eine Veröffentlichung von Kopien oder Übersetzungen) dieses
Lehrmaterials bedarf der Erlaubnis des Autors.
Zeitplan: Das Kapitel 5 kann in den 10. und 11. Sitzungen behandelt werden.
Überblick:
In jeder Programmiersprache sind einige "Basisdatentypen" vordefiniert, üblicherweise die Datentypen "ganze Zahl", "reelle Zahl", "Boole'sche Werte", "Zeichen" und "Zeichenfolge". In diesem Kapitel werden zunächst die vordefinierten Basistypen von SML behandelt, die aus früheren Kapiteln und Übungsaufgaben schon bekannt sind. Ziel ist es, einen umfassenden Überblick über die Basistypen von SML zu geben. Ferner wird die Zusammensetzung von Typen in SML eingeführt.
Inhalt:
Ein Typ (oder Datentyp) ist eine Menge von Werten. Mit einem Typ werden Operationen, oder Prozeduren, zur Bearbeitung der Daten des Typs angeboten.
Eine n-stellige Operation über einem Typ T ist eine Funktion T^n ---> T wobei T^n für T × ... × T (n Mal) steht. Die ganzzahlige Addition ist z.B. eine binäre (d.h. zweistellige) Operation über dem Typ "ganze Zahl".
Ein Typ kann vordefiniert sein, d.h. von der Programmiersprache als Wertmenge angeboten werden. Mit einem vordefinierten Typ bieten Programmiersprachen die Operationen, Funktionen oder Prozeduren an, die zur Bearbeitung von Daten des Typs üblich sind.
Moderne Programmiersprachen ermöglichen auch, dass der Programmierer selber Typen definiert wie z.B. einen Typ "Wochentag" mit Wertmenge
{Montag, Dienstag, ..., Sonntag}
einen Typ "Uhrzeit" mit einer Wertmenge
{h:m:s | h in N, 0 <= h < 24, m in N, 0 <= m < 60, s in N, 0 <= s < 60}
einen Typ "komplexe Zahl" mit Wertmenge
{a + ib | a und b vom Typ "reelle Zahlen"}
oder einen Typ "Übungsgruppe" zur Bündelung der folgenden Merkmale einer Übungsgruppe:
Offenbar verlangt die Spezifikation von Typen wie "komplexe Zahlen" und "Übungsgruppen" Mittel zur Zusammensetzung von Typen wie "ganze Zahl" (zur Bildung des Typs "Uhrzeit"), "reelle Zahl" (zur Bildung des Typs "komplexe Zahl"), "Zeichenfolge" und "Uhrzeit" (zur Bildung des Typs "Übungsgruppe").
Die Bildung von neuen Typen wird in den Kapiteln 8 " Abstraktionsbildung mit neuen Datentypen" und 9 " Rekursive Datentypen" behandelt. In diesem Kapitel werden die vordefinierten Typen von SML behandelt. Die vordefinierten Typen von SML bilden eine sehr "klassische" Auswahl an vordefinierten Typen, die sich von dem Angebot an vordefinierten Typen in anderen Programmiersprachen nur unwesentlich unterscheidet.
Der SML-Typ int (integer) steht für die "ganzen Zahlen".
Das Minusvorzeichen der negativen ganzen Zahlen wird in SML ~ geschrieben: z.B. ~89.
| Führende Nullen sind in SML erlaubt: z.B. 007 | 089 | ~002. |
Über dem Typ int bietet SML die folgenden binären Operationen an:
| + | (infix) | Addition |
| - | (infix) | Substraktion |
| * | (infix) | Multiplikation |
| div | (infix) | ganzzahlige Division |
| mod | (infix) | Rest der ganzzahligen Division |
SML bietet über dem Typ int die folgenden Vergleichsoperatoren an:
| = | (infix) | gleich |
| <> | (infix) | nicht gleich |
| < | (infix) | echt kleiner |
| <= | (infix) | kleiner-gleich |
| > | (infix) | echt größer |
| >= | (infix) | größer-gleich |
Die Vergleichsoperatoren des Typs int sind Funktionen vom Typ int * int -> bool.
Die Funktion real vom Typ int -> real dient zur Konvertierung einer ganzen Zahl in eine Gleitkommazahl mit demselben mathematischen Wert.
Der SML-Typ real bezeichnet die Gleitkommazahlen, die auch inkorrekterweise "reelle Zahlen" genannt werden. Was Gleitkommazahlen genau sind, wird in der Grundstudiumsvorlesung Informatik 3 erläutert. Im Grunde stellen Gleitkommazahlen rationale Zahlen dar, aber nur eine endliche Teilmenge davon und mit Gesetzmäßigkeiten der Arithmetik, die stark von den mathematischen Gesetzmäßigkeiten abweichen können.
Zur Darstellung in SML von Gleitkommazahlen können zwei Konstrukte (zusammen oder nicht zusammen) verwendet werden:
In der Mantisse-Exponent-Notation kann das "e" sowohl groß als auch klein geschrieben werden.
SML läßt führende Nullen in Dezimalbruchzahlen sowie in Mantissen und Zehnerexponenten zu. Vor dem Punkt einer Dezimalbruchzahl verlangt SML eine Ziffer: z.B. lässt SML die Schreibweise .89 nicht zu.
Über dem Typ real bietet SML die folgenden binären Operationen an:
| + | (infix) | Addition |
| - | (infix) | Substraktion |
| * | (infix) | Multiplikation |
| / | (infix) | Division |
Achtung: die Arithmetik mit Gleitkommazahlen folgt ihren eigenen Gesetzmäßigkeiten und führt oft zu anderen Ergebnissen als die Arithmetik mit rationalen Zahlen oder gar reellen Zahlen im mathematischen Sinn:
- 1234567890.0 + 0.005;
val it = 1234567890.01 : real
- 1234567890.0 + 0.0005;
val it = 1234567890.0 : real
Aus diesen Gründen ergeben arithmetische Berechnungen mit Gleitkommazahlen im Allgemeinen bestenfalls Approximationen der tatsächlichen Werte. Oft sind sorgfältige Analysen mit Methoden der numerischen Mathematik erforderlich, um sicherzustellen, dass die Ergebnisse überhaupt in der Nähe der tatsächlichen Werte liegen und nicht einfach völlig falsch sind.
SML bietet über dem Typ real die folgenden Vergleichsoperatoren an:
| < | (infix) | echt kleiner |
| <= | (infix) | kleiner-gleich |
| > | (infix) | echt größer |
| >= | (infix) | größer-gleich |
Die Funktion floor vom Typ real -> int konvertiert eine Gleitkommazahl in eine ganze Zahl und rundet sie dabei nach unten. Die Funktionen ceil vom gleichen Typ rundet nach oben. Die Funktion trunc vom gleichen Typ rundet in Richtung Null, indem sie einfach alle Nachkommastellen weglässt.
Der SML-Typ real enthält außer den "normalen" Gleitkommazahlen noch einige spezielle Werte, die als Ergebnis bestimmter Operationen auftreten können:
- 1.0 / 0.0;
val it = inf : real
- 0.0 / 0.0;
val it = nan : real
- Math.sqrt(~1.0);
val it = nan : real
- 1.0 + (1.0 / 0.0);
val it = inf : real
- 1.0 + (0.0 / 0.0);
val it = nan : real
Dabei steht inf für infinite, also unendlich, und nan für not-a-number, also kein Zahlenwert. Wie die letzten beiden Beispiele andeuten, sind alle Operationen des Typs real auch definiert, wenn diese speziellen Werte als Argument auftreten. Die Einzelheiten dieser Definitionen folgen einem internationalen Standard für Gleitkommazahlen in Programmiersprachen (IEEE standard 754-1985 und ANSI/IEEE standard 854-1987).
Der SML-Typ bool (Boole'sche Werte) besteht aus der Wertmenge {true, false}.
Über dem Typ bool bietet SML die folgenden Operatoren an:
| not | (präfix, unär) | Negation |
| andalso | (infix, binär) | Konjunktion |
| orelse | (infix, binär) | Disjunktion |
Die Operatoren andalso und orelse sind in SML keine Funktionen:
Der SML-Typ string ist die Menge der endlichen Zeichenfolgen.
In SML werden Zeichenfolgen eingeklammert zwischen zwei " geschrieben. "" bezeichnet in SML die leere Zeichenfolge.
Das Zeichen " wird in SML innerhalb einer Zeichenfolge \" geschrieben: z.B "ab\"cd" bezeichnet in SML die Zeichenfolge ab"cd . Weitere "escape sequences", die mit dem Zeichen \ anfangen, dienen zur Darstellung von Sonderzeichen in SML:
| \n | newline |
| \t | tab |
| \\ | \ |
Die Folge:
\ gefolgt von white-space-Zeichen gefolgt von \
ermöglicht es, white-space-Zeichen wie newline, tab oder Leerzeichen, die zur lesbareren Darstellung eines Programms nützlich sind, innerhalb einer SML-Zeichenfolge zu ignorieren: z.B.
- "aaaa\ \b";
val it = "aaaab" : string
- "ccc\
=
=
= \d";
val it = "cccd" : string
Über dem Typ string bietet SML die folgenden Operationen an:
| size | (präfix, unär) | Länge einer Zeichenfolge |
| ^ | (infix, binär) | Konkatenation (Aneinanderfügen) zweier Zeichenfolgen |
SML bietet über dem Typ string die folgenden Vergleichsoperatoren an:
| = | (infix) | gleich |
| <> | (infix) | nicht gleich |
| < | (infix) | echt kleiner |
| <= | (infix) | kleiner-gleich |
| > | (infix) | echt größer |
| >= | (infix) | größer-gleich |
Diese Operatoren beziehen sich auf die sogenannte lexikographische Ordnung, nach der zum Beispiel "a" < "aa" < "b" ist.
Der SML-Typ char besteht aus der Menge der Zeichen. Man beachte den Unterschied zwischen Zeichen und Zeichenfolgen der Länge 1: Wie die einelementige Menge {2} nicht dasselbe wie die ganze Zahl 2 ist, so ist das Zeichen b nicht dasselbe wie die Zeichenfolge b.
Im SML wird ein Zeichen z als #"z" geschrieben, das ist # gefolgt von der Zeichenfolge z, also von "z".
Über dem Typ char bietet SML die folgenden Funktionen an:
| chr: int -> char | Für 0 <= n <= 255 liefert chr(n) das Zeichen |
| mit Code n. | |
| ord: char -> int | liefert den Code eines Zeichens z |
Zum Beispiel:
- chr(100);
val it = #"d" : char
- ord(#"d");
val it = 100 : int
- chr(ord(#"d"));
val it = #"d" : char
- ord(chr(89));
val it = 89 : int
Zur Konvertierung zwischen Zeichen und Zeichenfolgen bietet SML bzw. die Standardbibliothek von SML die unäre Funktion str und die binäre Funktion String.sub an:
- str(#"a");
val it = "a" : string
- String.sub("abcd", 0);
val it = #"a" : char
- String.sub("abcd", 2);
val it = #"c" : char
Der SML-Typ unit besteht aus der Wertmenge {()}. () wird oft unity ausgesprochen. Dieser einzige Wert des Typs unit wird als Wert von Prozeduraufrufen verwendet.
Sind n >= 0 und t1, t2, ..., tn SML-Typen und A1, A2, ..., An Ausdrücke der Typen t1, t2, ..., tn, so ist (A1, A2, ..., An) ein n-stelliger Vektor (oder n-Tupel) vom Typ t1 * t2 * ... * tn. (Dabei bezeichnet * in SML das kartesische Produkt von Typen).
Zum Beispiel:
- ("abc", 44, 89e~2);
val it = ("abc",44,0.89) : string * int * real
- (("abc", 44), (44, 89e~2));
val it = (("abc",44),(44,0.89)) : (string * int) * (int * real)
Man beachte, dass Komponenten von Vektoren selbst Vektoren sein dürfen.
Die Gleichheit über Vektoren (derselben Länge!) ist komponentenweise definiert:
- val eins = 1;
val eins = 1 : int
- val drei = 3;
val drei = 3 : int
- (eins, drei) = (1, 3);
val it = true : bool
Vektoren der Längen 1 und 0 stellen Ausnahmen dar:
- (3) = 3;
val it = true : bool
In SML hängen Vektoren und Argumente von "mehrstelligen" Funktionen wie folgt zusammen: In einer Funktionsanwendung f(a1, a2, a3) stellt (a1, a2, a3) einen Vektor dar, so dass die Funktion f einstellig ist (und auf dreistellige Vektoren angewandt wird). Z.B.:
- fun f(n:int, m:int) = n + m;
val f = fn : int * int -> int
- val paar = (1, 2);
val paar = (1,2) : int * int
- f paar;
val it = 3 : int
In SML sind also jede Funktion und die Werte von jedem Ausdruck einstellig.
Zur Selektion der Komponenten eines Vektors kann in SML der Musterangleich (pattern matching) verwendet werden:
- val tripel = (1, #"z", "abc");
val tripel = (1,#"z","abc") : int * char * string
- val (komponente1, komponente2, komponente3) = tripel;
val komponente1 = 1 : int
val komponente2 = #"z" : char
val komponente3 = "abc" : string
Zur Selektion der Komponenten eines Vektors können in SML auch die Funktionen #1, #2, usw. verwendet werden:
- #1("a", "b", "c");
val it = "a" : string
- #3("a", "b", "c");
val it = "c" : string
Einem Vektortyp t1 * t2 * ... * tn (hier bezeichnet * das kartesische Produkt) kann wie folgt ein Name gegeben werden:
- type punkt = real * real;
- fun abstand(p1: punkt, p2: punkt) =
let fun quadrat(z) = z * z
val delta_x = #1(p2) - #1(p1)
val delta_y = #2(p2) - #2(p1)
in
Math.sqrt(quadrat(delta_x) + quadrat(delta_y))
end;
val abstand = fn : punkt * punkt -> real
- abstand((4.5, 2.2), (1.5, 1.9));
val it = 3.01496268634 : real
Man beachte, dass punkt lediglich ein Synonym für real * real ist. In der Tat ist (real * real) * (real * real) der Typ des aktuellen Parameters der vorangehenden Funktionsanwendung (wie gesagt ist die Funktion einstellig, und ihr Argument ist somit ein Paar von Paaren von Gleitkommazahlen).
Wegen den Typ-Constraints p1: punkt und p2: punkt verlangt die Definition der lokalen Funktion quadrat keine Typ-Constraint, um die Überladung der Multiplikation aufzulösen.
Ein n-stelliger Vektor ist eine geordnete Zusammensetzung von n Komponenten, so dass die Komponenten durch ihre Position bestimmt werden. Man kann also einen 3-stelligen Vektor vom Typ string * char * int wie z.B. ("Bry", #"F", 2210) als eine Zusammensetzung von einer ganzen Zahl, einer Zeichenfolge und einem Zeichen beschreiben, so dass gilt:
Es bietet sich, anstatt von nummerierten Positionen Bezeichner zu verwenden wie etwa:
Diese Idee liegt den Verbunden (oder records) zu Grunde. Das vorangehende Beispiel kann wie folgt unter Verwendung eines SML-Verbunds dargestellt werden:
- val adressbucheintrag = {Nachname = "Bry",
Vornamenbuchstabe = #"F",
Durchwahl = "2210"};
val adressbucheintrag =
{Durchwahl="2210",Nachname="Bry",Vornamenbuchstabe=#"F"}
: {Durchwahl:string, Nachname:string, Vornamenbuchstabe:char}
Man beachte, dass die Reihenfolge der Komponenten eines Verbunds keine Rolle spielt. Dies folgt logisch daraus, dass die Komponenten eines Verbundes mit Bezeichnern identfiziert werden anstatt mit Positionen wie bei Vektoren.
Man beachte auch, dass die Bezeichner der Komponenten eines Verbundes im Typ des Verbundes vorkommen. Es ist eben logisch, dass die Verbunde {a = 1, b = 2} und {aaa = 1, bbb = 2} nicht den selben Typ haben:
- {a = 1, b = 2};
val it = {a=1,b=2} : {a:int, b:int}
- {aaa = 1, bbb = 2};
val it = {aaa=1,bbb=2} : {aaa:int, bbb:int}
Verbunde werden komponentenweise verglichen:
- {a=1, b=2} = {b=2, a=1};
val it = true : bool
Zur Selektion der Komponentenwerte mit Hilfe der Komponentenbezeichner eines Verbundes bietet SML die Funktion #Bezeichner an:
- #bbb({aaa=1,bbb=2});
val it = 2 : int
- #a({a = 1, b = 2});
val it = 1 : int
SML bietet auch die folgende Kurzschreibweise für Deklarationen an:
- val info1dozent = {Nachname = "Bry", Vorname = "François"};
val info1dozent = {Nachname="Bry",Vorname="François"}
: {Nachname:string, Vorname:string}
- val {Nachname, Vorname} = info1dozent;
val Nachname = "Bry" : string
val Vorname = "François" : string
So werden Variablen deklariert, die die selben Namen wie die Komponentenbezeichner haben. Das Folgende ist aber nicht möglich:
- val {nn, vn} = info1dozent;
stdIn:1.1-39.11 Error: pattern and expression in val dec don't
agree [tycon mismatch]
pattern: {nn:'Z, vn:'Y}
expression: {Nachname:string, Vorname:string}
in declaration:
{nn=nn,vn=vn} =
(case info1dozent
of {nn=nn,vn=vn} => (nn,vn))
Verbunde sind den "structures" der Programmiersprache C und den "records" der Programmiersprachen Pascal und Modula ähnlich.
Wie für Vektoren bietet SML die Möglichkeit an, einem Vektor- oder Verbundtyp einen Namen zu geben, wie z.B.:
- type complex = real * real;
- type dateieintrag = {Vorname:string, Nachname:string};
Der so vergebene Name ist lediglich ein Synonym für den Verbundtyp.
In SML sind Vektoren Verbunde mit besonderen Komponentenbezeichnern, wie die folgende Sitzung zeigt:
- {1="abc", 2="def"};
val it = ("abc","def") : string * string
- fun vertauschen {1 = x:string, 2 = y:string} = {1=y, 2=x};
val vertauschen = fn : string * string -> string * string
- val paar = ("abc", "def");
val paar = ("abc","def") : string * string
- vertauschen paar;
val it = ("def","abc") : string * string
Der Begriff "Liste" kommt in den meisten Programmiersprachen und in vielen Algorithmen -- mit einigen unwesentlichen Unterschieden vor allem in der Syntax -- vor. Wir wollen zunächst den Begriff "Liste" unabhängig von jeglicher Programmiersprache erläutern. Danach werden wir den SML-Typ "Liste" einführen.
Eine Liste ist eine endliche geordnete Folge von Elementen. Listen werden oft wie folgt dargestellt: [1, 2, 3] oder ["a", "bcd", "e", "fg"]. Die leere Liste ist möglich, sie wird [] dargestellt.
Der Typ Liste verfügt über eine Funktion, cons für "list constructor" genannt, um Listen wie folgt aufzubauen:
Angewandt auf einen Wert W und eine Liste L bildet cons die Liste, deren ersten (d.h. am weitesten links stehendes) Element W ist und deren weiteren Elemente die Elemente der Liste L (in der selben Reihenfolge) sind.
Angewandt auf 5 und die Liste [9, 8] bildet also cons die Liste [5, 9, 8]. In anderen Worten ist [5, 9, 8] der Wert von cons(5, [9, 8]). Die Funktion cons wird oft infix geschrieben. Man schreibt also 5 cons [9, 8] statt cons(5, [9, 8]).
Aus der Definition von cons folgt, dass eine Liste wie [5, 9, 8] auch
5 cons (9 cons (8 cons []))
notiert werden kann. Ist zudem die Infixfunktion cons rechtsassoziativ, was in vielen Programmiersprachen der Fall ist, so kann eine Liste wie [5, 9, 8] auch wie folgt notiert werden:
5 cons 9 cons 8 cons []
Die meisten Programmiersprachen bieten eine Notation wie [5, 9, 8] als Ersatz (syntaktischer Zuchker) für den weniger lesbaren Ausdruck 5 cons 9 cons 8 cons [].
Der Typ Liste verfügt zudem über zwei Funktionen, womit auf Werte aus einer Liste zugegriffen werden kann: head und tail:
Angewandt auf eine nicht leere Liste L liefert head das erste (d.h. das am weitesten links stehende) Element von L.
Angewandt auf eine nicht leere Liste L liefert tail die Liste, die sich aus L ergibt, wenn das erste Element von L gestrichen wird.
Angewandt auf [5, 9, 8] liefern also head den Wert 5 und tail den Wert [9, 8].
Die Funktionen head und tail sind auf Listen nicht total, weil sie für die leere Liste nicht definiert sind.
Weil sie ermöglichen, Listen zu zerlegen (to decompose), werden die Funktionen head und tail oft "decomposers" genannt. In Anlehnung an die Bezeichnung "constructor" werden head und tail auch "destructors" genannt.
Wie kann man unter Verwendung von head und tail eine Funktion spezifieren, die das letzte Element einer nicht-leeren Liste liefert? Selbstverständlich unter Anwendung der Rekursion:
Das letzte Element E einer nicht-leeren Liste L ist definert als: Falls L die einelementige Liste [A] ist, so ist A das letzte Element. Andernfalls ist das letzte element von L das letzte Element der Liste tail(L).
Der Test, ob eine Liste nur ein Element enthält, lässt sich ebenfalls einfach wie folgt spezifizieren:
Eine Liste L enthält (genau) ein Element genau dann, wenn tail(L) = [] ist.
Listenelemente können allgemein die Werte von atomaren oder zusammengesetzten Ausdrücken sein. So ist z.B. der Wert des Ausdrucks [eins, zwei] die Liste [1, 2], wenn 1 der Wert von eins ist und 2 der Wert von zwei.
Selbstverständlich sind Listen von Listen wie etwa [[1,2],[1,5]] möglich.
Die Gleichheit für Listen ist elementweise definiert: [a,b,c] = [d,e,f] genau dann, wenn a=d und b=e und c=f ist.
Eine SML-Liste ist eine endliche Folge von Werten des selben Typs. In SML ist es also nicht möglich, Listen von Werten aus verschiedenen Typen zu bilden.
Für jeden gegebenen Typ 'a ('a wird oft alpha ausgesprochen) bezeichnet in SML 'a list den Typ der Listen von Werten vom Typ 'a. Ist z.B. 'a der Typ int, so ist int list der Typ, der aus den Listen von ganzen Zahlen besteht.
SML bietet zwei Notationen für Listen:
- 0 :: 1 :: 2 :: 3 :: nil;
val it = [0,1,2,3] : int list
- 0 :: (1 :: (2 :: (3 :: nil)));
val it = [0,1,2,3] : int list
- [0,1,2,3];
val it = [0,1,2,3] : int list
Selbstverständlich dürfen beide Notationen zusammen verwendet werden:
- 0 :: 1 :: [2, 3];
val it = [0,1,2,3] : int list
Die Notation mit den Listenklammern [ und ] und dem , als Trennzeichen ist lediglich "syntaktischer Zucker", d.h. eine Kurzform für die Notation mit dem Listenkonstruktor :: (cons).
Der SML-Typ der leeren Liste nil (oder []) ist 'a list, was "Liste von Elementen eines beliebigen Typs" heißt:
- nil;
val it = [] : 'a list
- [];
val it = [] : 'a list
Dabei ist 'a (oft alpha gesprochen) eine Typvariable, d.h. eine Variable, die als Wert einen Typ erhalten kann. Man sagt, dass nil ein "polymorphes Objekt" ist, d.h. ein "Objekt", das mehreren Typen angehört. Dass nil ein polymorphes Objekt ist, hat den Vorteil, dass es nur eine leere Liste gibt. Wäre nil kein polymorphes Objekt, dann müsste für jeden möglichen Typ 'a eine leere Liste für den Typ 'a list geben, was ziemlich umständlich wäre.
SML bietet die Gleichheit für Listen:
- val eins = 1;
val eins = 1 : int
- val zwei = 2;
val zwei = 2 : int
- [eins, 2] = [1,zwei];
val it = true : bool
Ein Typausdruck wie 'a oder 'a list wird "polymorpher Typ" oder "Polytyp" genannt, weil der Ausdruck für mehrere (giechisch "poly") Typen steht: Mögliche Instanzen von 'a sind z.B. int, oder bool, oder int list; mögliche Instanzen von 'a list sind z.B. int list, bool list, (int list) list, oder (int * bool) list.
Ein Typ, der kein Polytyp ist, wird "Monotyp" genannt.
- fun laenge(nil) = 0
| laenge(_ :: L) = 1 + laenge(L);
val laenge = fn : 'a list -> int
- laenge([0,1,2,3]);
val it = 4 : int
- fun letztes_element(x :: nil) = x
| letztes_element(_ :: L) = letztes_element(L);
Warning: match nonexhaustive
x :: nil => ...
_ :: L => ...
val letztes_element = fn : 'a list -> 'a
- letztes_element([0,1,2,3]);
val it = 3 : int
Das SML-System erkennt, dass die Deklaration der Funktion letztes_element keinen Fall für die leere Liste hat, d.h. dass diese Funktion über einem Typ 'a list nicht total ist. Das SML-System gibt eine Warnung, weil nicht-totale Funktionen manchmal fehlerhaft sind. Da aber die Deklaration einer nicht-totalen Funktion in manchen Fällen -- wie hier -- notwendig ist, wird eine solche Deklaration nicht abgelehnt.
- fun kleinstes_element(x :: nil) = x : int
| kleinstes_element(x :: L) = let val y = kleinstes_element(L)
in
if x <= y then x else y
end;
Warning: match nonexhaustive
x :: nil => ...
x :: L => ...
val kleinstes_element = fn : int list -> int
Das Typ-Constraint x : int ist notwendig, weil der Boole'sche Operator <= überladen ist.
- fun ntes_element(1, x :: _) = x
| ntes_element(n, _ :: L) = ntes_element(n-1, L);
Über welcher Menge ist diese Funktion total?
- fun head(x :: _) = x;
Warning: match nonexhaustive
x :: _ => ...
val head = fn : 'a list -> 'a
SML bietet die vordefinierte Funktion hd an:
- hd([1,2,3]);
val it = 1 : int
- fun tail(_ :: L) = L;
Warning: match nonexhaustive
_ :: L => ...
val tail = fn : 'a list -> 'a list
SML bietet die vordefinierte Funktion tl an:
- tl([1,2,3]);
val it = [2,3] : int list
Die vordefinierte SML-Funktion append, infix @ notiert, dient dazu, zwei Listen aneinander zu fügen:
- [1,2,3] @ [4,5];
val it = [1,2,3,4,5] : int list
Die Funktion append kann wie folgt in SML implementiert werden:
- fun append(nil, L) = L
| append(h :: t, L) = h :: append(t, L);
val append = fn : 'a list * 'a list -> 'a list
- append([1,2,3], [4,5]);
val it = [1,2,3,4,5] : int list
Berechnungsschritte zur Auswertung von append([1,2,3], [4,5]):
append(1::(2::(3::nil)), 4::(5::nil))
1 :: append(2::(3::nil), 4::(5::nil))
1 :: (2 :: append(3::nil, 4::(5::nil)))
1 :: (2 :: (3 :: append(nil, 4::(5::nil))))
1 :: (2 :: (3 :: (4::(5::nil))))
Es gibt keinen Berechnungschritt mehr, 1 :: (2 ::(3 :: (4::(5::nil)))) ist die Liste [1, 2, 3, 4, 5].
Zeitbedarf von append:
Es ist naheliegend, als Zeiteinheit die Anzahl der Aufrufe der Funktion cons (::) oder aber die Anzahl der rekursiven Aufrufe von append zu wählen. Beide Zahlen stehen einfach miteinander in Verbindung: Wird zur Berechnung von append(L, L') die append-Funktion n+1 mal rekursiv aufgerufen, so wird die Funktion cons (::) n mal aufgerufen.
(*) Um eine Liste L der Länge n mit n >= 1 vor einer Liste L' einzufügen, ruft die Funktion append die Funktion cons (::) genau n Male auf.
Bemerkenswert ist, dass die Länge des zweiten Parameters L' den Zeitbedarf von append nicht beeinflusst.
Ist n die Länge des ersten Parameters von append, so gilt: append in O(n).
Mit der vordefinierten SML-Funktion reverse, rev notiert, kann aus einer Liste eine Liste im umgekehrter Reihenfolge erzeugt werden:
- rev([1,2,3]);
val it = [3,2,1] : int list
Eine Funktion reverse kann in SML wie folgt implementiert werden:
- fun naive_reverse(nil) = nil
| naive_reverse(h :: t) = append(naive_reverse(t), h :: nil);
- naive_reverse([1,2,3]);
val it = [3,2,1] : int list
Berechnungsschritte zur Auswertung von naive_reverse([1,2,3]):
naive_reverse(1::(2::(3::nil)))
append(naive_reverse(2::(3::nil)), 1::nil)
append(append(naive_reverse(3::nil), 2::nil), 1::nil)
append(append(append(naive_reverse(nil), 3::nil), 2::nil), 1::nil)
append(append(append(nil, 3::nil), 2::nil), 1::nil)
append(append(3::nil, 2::nil), 1::nil)
append(3::append(nil, 2::nil), 1::nil)
append(3::(2::nil), 1::nil)
3::append(2::nil, 1::nil)
3::(2::append(nil, 1::nil))
3::(2::(1::nil))
Zeitbedarf von naive_reverse:
Zur Schätzung der Größe des Problems "Umkehrung einer Liste" bietet es sich an, die Länge der Liste zu wählen.
Wie zur Schätzung des Zeitbedarfs der Funktion append bietet es sich an, als Zeiteinheit die Anzahl der rekursiven Aufrufe von naive_reverse oder die Anzahl der Aufrufe der Funktion cons (::) zu wählen.
Gegeben sei eine Liste L der Länge n mit n >= 1. Während des Aufrufes von naive_reverse(L) wird die Funktion naive_reverse n+1 mal rekursiv aufgerufen, zunächst mit einer Liste der Länge n-1 als Parameter, dann mit einer Liste um ein Element kürzer als Parameter bei jedem weiteren Aufruf. Wegen (*) (siehe die Schätzung des Zeitbedarfs von append) wird zur Zerlegung der Eingabeliste die Funktion cons (::) also
(n-1) + (n-2) + ... + 1
Male aufgerufen. Zum Aufbau der auszugegebenden Liste wird cons (::) zudem n mal aufgerufen. Die Gesamtanzahl der Aufrufe von cons (::) lautet also:
n + (n-1) + (n-2) + ... + 1 = n * (n+1) / 2
Ist n die Länge des Parameters von naive_reverse, so gilt:
naive_reverse in O(n * (n+1) / 2)
also
naive_reverse in O(n**2)
Der quadratische Zeitbedarf von naive_reverse ist nicht zufriedenstellend, weil, wie das Folgende zeigt, eine Liste in einer Zeit in umgekeherte Reihenfolge gebracht werden kann, die linear von der Listenlänge abhangt:
Man fängt mit zwei Listen an: die linke Liste, die die EingabelIste ist, und die rechte Liste, die anfangs leer ist. Nach und nach wird das erste Element der linken Liste von dieser Liste entfernt und am Anfang der rechten Liste eingefügt. Dabei werden nur Operationen verwendet, die der Typ Liste anbietet. Nach soviel Schritte, wie die Eingabeliste lang ist, ist die linke Liste leer und die rechte Liste die Liste in umgekehrten Reihenfolge, die aufzubauen war:
| Linke Liste | Rechte Liste |
| [1, 2, 3] | [] |
| [2, 3] | [1] |
| [3] | [2, 1] |
| [] | [3, 2, 1] |
Dieses Verfahren läßt sich einfach in SML wie folgt implementieren:
- fun aux_reverse(nil, R) = R
| aux_reverse(h::t, R) = aux_reverse(t, h::R);
val aux_reverse = fn : 'a list * 'a list -> 'a list
- aux_reverse([1,2,3], []);
val it = [3,2,1] : int list
- aux_reverse([1,2], [8,9]);
val it = [2,1,8,9] : int list
Die gewünschte einstellige reverse-Funktion folgt unmittelbar aus der Spezifikation von aux_reverse:
- fun reverse(L) = let fun aux_reverse(nil, R) = R
| aux_reverse(h::t, R) = aux_reverse(t, h::R)
in
aux_reverse(L, nil)
end;
val reverse = fn : 'a list -> 'a list
- reverse([1,2,3]);
val it = [3,2,1] : int list
Berechnungsschritte zur Auswertung von reverse([1,2,3]):
reverse(1::(2::(3::nil)))
aux_reverse(1::(2::(3::nil)), nil)
aux_reverse(2::(3::nil), 1::nil)
aux_reverse(3::nil, 2::(1::nil))
aux_reverse(nil, 3::(2::(1::nil)))
3::(2::(1::nil)))
Zeitbedarf von reverse:
Ist n >= 0 die Länge einer Liste L, so bedarf die Auswertung von aux_reverse(L, nil) n rekursiver Aufrufe sowie n Aufrufe der Funktion cons (::). Es gilt also:
aux_reverse in O(n)
Folglich gilt auch:
reverse in O(n)
Der zweite Parameter der Funktion aux_reverse, der der rechtne Liste von unserem Beispiel entspricht, ist ein sogenannter Akkumulator. Die Nutzung eines Akkumulators wurde bereits im Kapitel 4 (Abschnitt 4.3 Prozeduren contra Prozesse) erläutert, um die Berechnung der Fakultät einer natürlichen Zahl in einem iterativen Prozess zu berechnen.
Wie die Funktion fak_iter aus dem Kapitel 4 (Abschnitt 4.3 Prozeduren contra Prozesse) ist die Funktion reverse endrekursiv, so dass sie einen iterativen Berechnungsprozess auslöst.
Die Standardbibliothek von SML, die unter der URI
http://cm.bell-labs.com/cm/cs/what/smlnj/doc/basis/
zugreifbar ist, bietet für die Basistypen von SML Funktionen an, die herkömmliche Operationen über diesen Typen in SML implementieren.