Algebraische Datentypen, eigene Listen, Mengen und Cliquen
Wir haben bislang mit vordefinierten Datentypen gearbeitet, mit den eingebauten primitiven Typen und mit Listen. In diesem Kapitel wollen wir uns ansehen, wie wir eigene Typen definieren können. Das ist dann hilfreich, wenn ein komplexeres Problem gelöst werden soll und man sich um eine problemnahe Modellierung der Daten und der darauf operierenden Algorithmen bemüht. Hier können auch Gesichtspunkte der Effizienz eine Rolle spielen.
Zunächst betrachten wir Punkte und andere eher elementare Konstruktionen aus der Bauklötzchen\-welt. Sie machen uns mit den grundlegenden Mechanismen vertraut und zeigen, wie wir einen selbst definierten Datentyp zum Mitglied der wichtigen Typklassen Show und Eq machen können. Dann parametrisieren wir unsere Datentypen, machen sie also von einem bereits existierenden Datentyp abhängig. Nach der Diskussion der grundlegenden Eigenschaften definieren wir zur Illustration einen eigenen Listen- und einen eigenen Mengentyp. Mengen spielen auch eine Rolle, wenn wir mit ungerichteten Graphen arbeiten. Hier diskutieren wir die Berechnung aller Cliquen eines ungerichteten Graphen. Binäre Bäume, insbesondere binäre Suchbäume, dürfen nicht fehlen, sie werden mit ihren Durchlaufstrategien und den üblichen Operationen diskutiert. Den Abschluss bildet eine wichtige und populäre Anwendung, nämlich die Implementierung des Algorithmus von Kruskal zur Berechnung des minimalen Gerüsts eines ungerichteten und zusammenhängenden Kostengraphen.
Wir haben bislang mit vordefinierten Datentypen gearbeitet, mit den eingebauten primitiven Typen und mit Listen. In diesem Kapitel wollen wir uns ansehen, wie wir eigene Typen definieren können. Das ist dann hilfreich, wenn ein komplexeres Problem gelöst werden soll und man sich um eine problemnahe Modellierung der Daten und der darauf operierenden Algorithmen bemüht. Hier können auch Gesichtspunkte der Effizienz eine Rolle spielen.
Zunächst betrachten wir Punkte und andere eher elementare Konstruktionen aus der Bauklötzchen\-welt. Sie machen uns mit den grundlegenden Mechanismen vertraut und zeigen, wie wir einen selbst definierten Datentyp zum Mitglied der wichtigen Typklassen Show und Eq machen können. Dann parametrisieren wir unsere Datentypen, machen sie also von einem bereits existierenden Datentyp abhängig. Nach der Diskussion der grundlegenden Eigenschaften definieren wir zur Illustration einen eigenen Listen- und einen eigenen Mengentyp. Mengen spielen auch eine Rolle, wenn wir mit ungerichteten Graphen arbeiten. Hier diskutieren wir die Berechnung aller Cliquen eines ungerichteten Graphen. Binäre Bäume, insbesondere binäre Suchbäume, dürfen nicht fehlen, sie werden mit ihren Durchlaufstrategien und den üblichen Operationen diskutiert. Den Abschluss bildet eine wichtige und populäre Anwendung, nämlich die Implementierung des Algorithmus von Kruskal zur Berechnung des minimalen Gerüsts eines ungerichteten und zusammenhängenden Kostengraphen.