CGI Programmierug mit Haskell

[ Seminarthemen SS 2001] ... [ Inhaltsverzeichnis ] ... [ CGI Library ]

Einführung in Haskell

Einführung in Haskell Für all die jenigen, die bislang noch nicht in einer funktionalen Sprache programmiert haben, möchte ich an dieser Stelle eine kleine Einführung in Haskell liefern. Es bleibt zu bemerken, daß diese Ausarbeitung allerdings nur einen geringen Teil der Möglichkeiten dieser mächtigen Sprache abdecken kann.

Funktionen

Eine Funktion ist eine Art Black Box, die aus belibig vielen Eingabewerten eine Ausgabe berechnet. In den meisten Fällen wird diese Funktion ihre Arbeit wieder an weitere Funktionen delegieren und nur deren Ausgabe geeignet verknüpfen. Eine Funktion ist eine Definition, die einen Namen (Bezeichner) mit einem Wert eines bestimmten Types verbindet. Eine der einfachsten denkbaren Deklarationen einer Funktion ist:

antwort :: Int antwort = 42

Hierbei wird der Bezeichner antwort vom Typ Int mit der Konstante 42 verknüpft.

Funktionsdeklaration

Die Deklaration (in objektorientierten Sprachen auch als Signatur bezeichnet) ist unterteilt in einen Funktionsbezeichner, der mit einem Kleinbuchstaben beginnen muß, einer optionalen Menge von formalen Parametern und einem zwingend vorgeschriebenen Rückgabetyp. Funktionsbezeichner und Parameter werden duch :: voneinander getrennt. Die einzelnen Eingabeparameter und der Rückgabetyp werden durch -> getrennt.

Beispielhaft läßt sich dies an der Funktionsdeklaration an der Funktion

    fac :: Int -> Int


erläutern. Aufgabe von fac ist es, die Fakultät einer beliebigen ganzen Zahl zu berechnen und das Ergebnis (ebenfalls eine ganze Zahl) zurückzuliefern.

Funktionsrumpf

Der Rumpf einer Haskell Funktion ist typischerweise sehr kurz, da entweder kleine elementare Operationen ausgeführt werden oder andere Funktionen aufgerufen werden.

Typischerweise besteht der Rumpf aus dem Funktionsbezeichner, den Namen der formalen Parameter, einem Gleichheitszeichen und der Berechnungsvorschrift. Die Funktion inc berechnet den Nachfolger einer ganzen Zahl. Sie kann wie folgt definiert werden. 

	inc :: Int -> Int
	inc n = n + 1
Die vollständige Definition der oben beschriebenen Funktion fac zeigt ein mächtiges Hilfsmittel von Haskell . Die Rede ist von Pattern Matching. Beim Pattern Matching werden die Parameter der Funktion ausgewertet, um in Abhängigkeit dieser Parameter alternative Berechnungsvorschriften aufzurufen. Wie bereits erwähnt ist die Rekursion wegen fehlender Schleifen ein integraler Bestandteil der funktionalen Programmierung. Am Beispiel der Funktion fac wird deutlich, warum Pattern Matching besonders für die Rekursion von großer Bedeutung ist. 
	fac :: Int -> Int
	fac 0 = 1
	fac n = n * fac (n - 1)

Die Berechnung der Fakultät erfolgt durch die Multiplikation der angegebenen Zahl n mit der Fakultät von n-1. Ist die Zahl n=0, wird durch Pattern Matching definitionsgemäß 1 zurückgegeben. Für alle n>0 wird die rekursive Berechnungsvorschrift aufgerufen.

Typen

Standard Datentypen

Es gibt eine Reihe von vordefinierten Datentype wie z.B. Char, Int, Bool, Float und String wobei String intern als eine Liste von Char representiert wird.

Benutzerdefinierte Datentypen

Es gibt in Haskell diverse Möglichkeiten, eigene Datentypen zu definieren. Im folgenden werde ich lediglich die algebraischen Datentypen (Aufzählungstyp und Produkttyp) und die Synonyme betrachten. Auf Grund der Komplexität kann auf Klassen hier nicht näher eingegangen werden.

Mit Hilfe von Synonymen lassen sich Programme lesbarer machen und zusammengesetzte Datentypen erstellen. Beispielsweise ist wie bereits erwähnt ein String eine Liste von Char und eine Person kann als Tupel aus Name und Alter aufgefaßt werden. Die Deklaration eines Synonyms erfolt durch das Schlüsselwort type, dem Typnamen, einem Gleichheitszeichen und der Definition. Alle Typnamen in Haskell beginnen mit einem Großbuchstaben. 

		type String	= [Char]
		type Person	= (String, Int)

Alle algebraischen Datentypen lassen sich durch das Schlüsselwort data, dem Typnamen, einem Gleichheitszeichen und der Definition erzeugen.

Ein Auzählungstyp ist ein Typ mit festem Wertebereich wie zum Beispiel die Monate eines Jahres. 

		data Monat = Jan | Feb | Mar | Apr | Mai | Jun | Jul |
		             Aug | Sep | Okt | Nov | Dez
Ein Produkttyp kann mit einem Pascal Record verglichen werden. Beliebig viele Daten unterschiedlichen Typs können zu einem Produkttyp zusammengefaßt werden. Diese Typen lassen sich ausschließlich durch definierte Konstruktoren erzeugen. Ein Beispiel für einen Produkttyp ist: 
		type Name = String
		type Alter = Int
		data Person = Teilnehmer Name Alter
Ein Datum des Typs Person läßt sich ausschließlich durch den Konstruktoraufruf erzeugen. Mit Hilfe von Produkttypen lassen sich auch Bäume und andere rekursive Datenstrukturen wie zum Beispiel 
		data Expr = Lit Int | Add Expr Expr | Sub Expr Expr
abbilden. Es gibt drei mögliche Ausprägungen des Typs Expr. Entweder handelt es sich um ein Blatt (einer Zahl) oder einen Knoten (entweder Add oder Sub). Erzeugt wird ein Rechnbaum für den Ausdruck (3-1)+2 durch: 
		Add (Sub (Lit 3) (Lit 1)) (Lit 2)

Sowohl die vordefinierten Typen als auch benutzerdefinierte Typen und Synonyme sind gültige formale Parameter und Rückgabewerte von Funktionen.

Listen

Ein großer Vorteil von Haskell gegenüber anderen Sprachen (in diesem Fall besonders gegenüber C) liegt im Umgang mit Listen, denn sie sind in Haskell von zentraler Bedeutung. ein Listentyp wird definiert durch das Einschließen eines Typs in eckige Klammern. Alle Listenoperationen arbeiten unabhängig vom Typ der in der Liste enthaltenen Werte. 

   
    length [1, 2, 3]		==> 3 
    length ['a', 'b', 'c']	==> 3 
    length [Jan, Feb, Mar]	==> 3

Wie oben verdeutlicht, arbeitet die Funktion length auf jeder Art von Liste. Man bezeichnet sie deshalb auch als polymorph. Die Funktionsdeklaration sieht wie folgt aus: length [a] -> Int. Im Sprachumfang von Haskell sind noch eine Reihe weiterer Listenoperationen vorgesehen. Kurz erwähnt seien an dieser Stelle die später benutzen Funktionen : (ein Element an den Anfang einer Liste hängen), ++ (zwei Listen gleichen Typs zu einer vereinen) und !! (indizierter Zugriff auf ein Element einer Liste.

 

Ausdruck Ergebnis 
'W' : "ort"
 
"Wort"
 
"Wo" ++ "rt"
 
"Wort"
 
"Wort" !! 2
 
'r'

 

Besonderheiten

Higher Order Functions

Haskell bietet beim Umgang mit Funktionen eine Reihe von Möglichkeiten, die beim Programmieren in imperativen oder objektorientierten Sprachen fehlen oder nur umstänlich abzubilden sind. Hierzu zählt das Konzept der Higher-order functions. Funktionen sind höherer Ordnung wenn sie eine Funktion als Parameter oder als Rückgabetyp (oder beides) haben. Dies ermöglicht eine ganze Reihe von Anwendungen. Im folgenden werde ich mich auf die Funktion map berschränken.

Die Funktion wendet eine ihr gegebene Funktion (mit der Signatur ) auf jedes Element der Liste des Typs an und gibt als Erbegnis eine Liste des Typs zurück.

Zur Veranschaulichung hier ein einfaches Beispiel. Angenommen es existiert eine Funktion show, 

 show :: Int -> String
die eine Zahl in einen String umzuwandelt. Nun habe ich eine Liste von Zahlen 
 [1, 2, 3, 4, 42]
und möchte diese in eine Liste von entsprechenden Strings 
 ["1", "2", "3", "4", "42"]
transorfmieren. In Haskell läßt sich diese Aufgabe kurz durch 
 map show [1, 2, 3, 4, 42]
lösen. Die Funktion show wird auf jedes Element der Liste angewendet und das Resultat in einer Ergebnisliste gespeichert.

 

Lazy Evaluation

Lazy Evaluation bezeichnet die Fähigkeit zu erkennen, ob ein Ausdruck ausgewertet werden muß, um das Ergebnis zu berechnen oder ob darauf verzichtet werden kann. Beispielsweise ist jeder weitere Parameter einer boolschen OR Verknüpfung gleichgültig, wenn irgend ein anderer wahr ist. In Verbindung mit dem .-Operator lassen sich ohne auch nur eine Zeile eigenen Code Pipes, wie man sie aus der Unix Welt kennt, nachbauen.

Die Ausgabe einer Funktion producer wird als Eingabe einer Funktion consument verwendet, wobei zu beachten ist, daß Funktion producer nur so lange ausgeführt wird, wie die Funktion consument Eingaben benötigt. Dies sei wiederum an einem kurzen praktischen Beispiel verdeutlicht. 

 queens :: Int -> [[Int]]
 ...
 firstQueen :: Int -> [Int]
 firstQueen n = (head.queens) n
queens berechnet alle möglichen Lösungen für das Damenproblem für n Damen. Die Liste von Ergebnissen wird zur Eingabe für die Listenfunktion . Diese Funktion liefert das erste Element einer Liste. Da diese Funktion ausgewertet werden kann bevor alle Ergebnisse aus vorliegen, bricht auch die Ausführung von vorzeitig ab. Gerade bei großen n spart diese Art der Auswertung erheblich Rechenzeit, da nur die erste Lösung gefunden werden muß.

 

Lambda Notation

Eine weitere Möglichkeit von Funktionsdefinitionen sind Funktionen in Lambda-Notation. Dabei handelt es sich um anonyme Funktionen, die an der Stelle definiert werden an der sie verwendet werden. Sie werden definiert mit einem gefolgt von der Parameterliste, einem und der eigentlichen Definition. Hierzu ein Beispiel: 
		map (\n -> n + 1) [1, 2, 3, 4]

Wie wir gesehen haben, wendet die Funktion map eine ihr zu übergebende Funktion auf eine ihr zusätzlich zu übergebende Liste an. In diesem Beispiel wird allerdings kein Funktionsbezeichner übergeben sondern die Funktionsdefinition selbst. Die in Lambda Notation geschriebene Funktion hat einen Parameter, zu dem sie 1 addiert.

 

[ Seminarthemen SS 2001] ... [ Inhaltsverzeichnis ] ... [ CGI Library ]