Eine Galerie von Anwendungen: Huffmann-Verschlüsselung, Mustererkennung in Texten, Erzeugung eines Parsers
In diesem Kapitel werden wir zunächst zwei klassische Beispiele besprechen, nämlich zum einen die Huffmann-Kodierung, zum anderen einen Algorithmus zur Mustererkennung in Texten. Die Huffmann-Kodierung repräsentiert einen Text binär, also durch Nullen und Einsen. Diese Repräsentation soll möglichst gut sein, wobei Optimalitätskriterien zu diskutieren sind. Wir achten darauf, daß häufig vorkommende Zeichen eine kurze, weniger häufig vorkommende eine längere Darstellung bekommen, zudem soll die Darstellung präfixfrei sein, die Kodierung eines Zeichens soll also kein Präfix eines anderen sein. Binäre Bäume gehen hier wesentlich ein, so daß wir hier ein gutes Exerzierfeld für diese algebraischen Datentypen finden. Das zweite Beispiel betrifft die Suche nach Mustern in Texten. Hier wird zunächst ein wenig mathematische Theorie betrieben, wir zeigen, wie ein Automat konstruiert wird, mit dessen Hilfe die Suche stattfindet. Auch das ist ziemlich klassischer Stoff, interessant hier ist einmal die elementare mathematische Theorie, zum anderen aber auch der Übergang von der formalen Repräsentation in die Darstellung in Haskell. Leser, die mit den Java oder C++-Lösungen für diese Probleme vertraut sind, werden sicherlich mit Interesse die Unterschiede in den Zugangsweisen und Darstellungen der objekt-orientierten und der funktionalen Sprache bemerken.
Im letzten Abschnitt dieses Kapitels besprechen wir die Erzeugung eines Parsers, also eines Hilfsmittels zur Erzeugung von Übersetzern für Programmiersprachen. Die Idee besteht darin, die Grammatik selbst als Spezifikation für die syntaktische Analyse heranzuziehen, also aus der Grammatik ein Programm zu gewinnen, mit dessen Hilfe ein vorgelegtes Wort syntaktisch analysiert werden kann. Der Ansatz geht so vor, daß der grundlegende Mechanismus, ein Automat mit einem Stack, sprachspezifisch parametrisiert wird; die Zustandsübergänge und das Geschehen auf dem Stack werden durch Tabellen beschrieben, die erzeugt werden müssen. Die zugrundeliegende Theorie kommt aus der Theorie formaler Sprachen und wird hier nur soweit berührt, wie es notwendig ist. Uns interessiert die Erzeugung der Tabellen, und hierfür sind Algorithmen bekannt. Wir zeigen, wie sich diese Algorithmen für einfache kontextfreie Grammatiken in Haskell umsetzen lassen - die Darstellung legt nahe, daß eine Erweiterung des Verfahrens auf komplexere Grammatiken ohne großen Aufwand möglich ist.
Die Bearbeitung dieses Beispiels rückt Haskell in die Nähe einer Sprache zum explorativen Prototyping: Die grundlegenden Ideen sind recht nahe am mathematischen Modell ausformuliert, und es geht darum, die zugehörigen Algorithmen zu implementieren, sei es, weil man damit experimentieren möchte, sei es, um die Machbarkeit festzustellen, sei es, um eine effiziente Implementierung vorzubereiten.
In diesem Kapitel werden wir zunächst zwei klassische Beispiele besprechen, nämlich zum einen die Huffmann-Kodierung, zum anderen einen Algorithmus zur Mustererkennung in Texten. Die Huffmann-Kodierung repräsentiert einen Text binär, also durch Nullen und Einsen. Diese Repräsentation soll möglichst gut sein, wobei Optimalitätskriterien zu diskutieren sind. Wir achten darauf, daß häufig vorkommende Zeichen eine kurze, weniger häufig vorkommende eine längere Darstellung bekommen, zudem soll die Darstellung präfixfrei sein, die Kodierung eines Zeichens soll also kein Präfix eines anderen sein. Binäre Bäume gehen hier wesentlich ein, so daß wir hier ein gutes Exerzierfeld für diese algebraischen Datentypen finden. Das zweite Beispiel betrifft die Suche nach Mustern in Texten. Hier wird zunächst ein wenig mathematische Theorie betrieben, wir zeigen, wie ein Automat konstruiert wird, mit dessen Hilfe die Suche stattfindet. Auch das ist ziemlich klassischer Stoff, interessant hier ist einmal die elementare mathematische Theorie, zum anderen aber auch der Übergang von der formalen Repräsentation in die Darstellung in Haskell. Leser, die mit den Java oder C++-Lösungen für diese Probleme vertraut sind, werden sicherlich mit Interesse die Unterschiede in den Zugangsweisen und Darstellungen der objekt-orientierten und der funktionalen Sprache bemerken.
Im letzten Abschnitt dieses Kapitels besprechen wir die Erzeugung eines Parsers, also eines Hilfsmittels zur Erzeugung von Übersetzern für Programmiersprachen. Die Idee besteht darin, die Grammatik selbst als Spezifikation für die syntaktische Analyse heranzuziehen, also aus der Grammatik ein Programm zu gewinnen, mit dessen Hilfe ein vorgelegtes Wort syntaktisch analysiert werden kann. Der Ansatz geht so vor, daß der grundlegende Mechanismus, ein Automat mit einem Stack, sprachspezifisch parametrisiert wird; die Zustandsübergänge und das Geschehen auf dem Stack werden durch Tabellen beschrieben, die erzeugt werden müssen. Die zugrundeliegende Theorie kommt aus der Theorie formaler Sprachen und wird hier nur soweit berührt, wie es notwendig ist. Uns interessiert die Erzeugung der Tabellen, und hierfür sind Algorithmen bekannt. Wir zeigen, wie sich diese Algorithmen für einfache kontextfreie Grammatiken in Haskell umsetzen lassen - die Darstellung legt nahe, daß eine Erweiterung des Verfahrens auf komplexere Grammatiken ohne großen Aufwand möglich ist.
Die Bearbeitung dieses Beispiels rückt Haskell in die Nähe einer Sprache zum explorativen Prototyping: Die grundlegenden Ideen sind recht nahe am mathematischen Modell ausformuliert, und es geht darum, die zugehörigen Algorithmen zu implementieren, sei es, weil man damit experimentieren möchte, sei es, um die Machbarkeit festzustellen, sei es, um eine effiziente Implementierung vorzubereiten.