other stuff - haskell

2. Grundlegende Sprachkonzepte

2.1 Programmstruktur und Notation

2.1.1 Allgemeines

Sämtliche Bezeichner in Haskell sind case sensitiv. So sind etwa add, Add und aDd drei unterschiedliche Namen. Die Bezeichner für Variablen und Typvariablen (siehe unten) müssen mit einem Kleinbuchstaben oder einem Unterstrich beginnen, z.B. add, getChar, _y, [a]. Alle anderen Bezeichner beginnen mit einem Großbuchstaben. Hierbei kann es sich um Konstruktoren, Typkonstruktoren, Typklassen und Modulnamen handeln (wobei auf letztere im folgenden nicht eingegangen wird), z.B.: 

Integer, [Char], Eq, True.
Während Bezeichner stets mit einem Buchstaben oder Unterstrich beginnen und Buchstaben, den Unterstrich, Ziffern und das Anführungszeichen ´ enthalten dürfen, sind Operatoren aus Symbolen zusammengesetzt, z.B.: 
:  .  ->  @  ==  >>=
Auch sie können prinzipiell neu definiert werden. Zu beachten ist hierbei, dass Konstruktoren immer mit einem Doppelpunkt beginnen. Der einfache Doppelpunkt ist als Listenkonstruktor reserviert.

2.1.2 Typ- und Funktionsdeklarationen

Da Haskell eine funktionale Sprache ist, bestehen Programme im wesentlichen aus einer Aneinanderreihung von Deklarationen. Typsignatur-Deklarationen geben an, welchen Typ eine Variable oder ein Ausdruck haben soll. Sie bestehen aus dem zu erklärenden Ausdruck, gefolgt von einem doppelten Doppelpunkt und dem Typ. Im folgenden Beispiel sind die Typdeklarationen für eine Integer-Konstante, ein Paar und eine einstellige Funktion gegeben. 

5                       :: Integer
(´x´,True)              :: (Char,Bool)
inc                     :: Integer -> Integer
In der Regel ist es nicht nötig, derartige Typdeklarationen in einem Programm anzugeben, da zu jedem Ausdruck der Typ automatisch abgeleitet werden kann. Sie erhöhen aber unter Umständen die Lesbarkeit und werden, wenn vorhanden, auch vom System überprüft.

Die zweite wichtige Form von Deklarationen sind Gleichungen. Sie bilden das eigentliche Programm. Hier ist eine mögliche Definition der Funktion inc, die ihren Parameter inkrementiert, angegeben. 

inc n                   = n+1

2.1.3 Currifizierte Funktionen

Die Schreibweise von Funktionen in Haskell unterscheidet sich wesentlich von der, die in der Mathematik oder gängigen imperativen Programmiersprachen verwendet wird. Während man etwa für die zweistellige Addition add(x,y) zu schreiben gewohnt ist, was add im Prinzip als eine Abbildung auf dem Paar (x,y) ausweist, formuliert man in Haskell add x y. Dies wird als (add x) y interpretiert, wobei (add x) noch keine Zahl ist, sondern wiederum eine einstellige Funktion, die zu ihrem Argument x addiert. Die Anwendung von (add x) auf den Parameter y ergibt dann erst das gewünschte Ergebnis So betrachtet könnte man sagen, dass es in Haskell nur einstellige Funktionen gibt. Dafür ist es zulässig, dass eine Funktion wiederum eine andere Funktion als Ergebnis liefert. Dies drückt sich auch in der Typnotation für "mehrstellige" Funktionen aus, wie die folgenden Beispiele zeigen. 

add                     :: Integer->Integer->Integer
openFile                :: FilePath->IOMode->Handle
add ist also eine Funktion von einem Integer-Parameter auf eine weitere Funktion Integer->Integer. Auch das Beispiel openFile, eine Funktion die bei Angabe eines Pfades und Zugriffsmodus ein Dateihandle liefert, verdeutlicht diesen Sachverhalt.

2.1.4 Funktionen und Operatoren

Um ein hohes Maß an Flexibilität zu gewährleisten, ist es wünschenswert, dass sich auch Operatoren wie Funktionen definieren lassen. Diese Anforderung wird von vielen Programmiersprachen erfüllt. Eine Besonderheit von Haskell ist es, dass sich auch neue Operatoren aus den entsprechenden Sonderzeichen zusammensetzen lassen und dass Funktionen und Operatoren vollkommen austauschbar sind. Außer dem unären Minus gibt es in Haskell nur Infix-Operatoren, d.h. Operatoren sind in der Regel als alternative Schreibweise für zweistellige Funktionen aufzufassen. Wird ein Operator in runde Klammern eingeschlossen, kann er syntaktisch exakt wie ein Funktionsbezeichner verwendet werden, wie die folgenden Beispiele zeigen. 

(==)                    :: Integer->Integer->Bool
add                     = (+)
inc                     = (+1)
Umgekehrt kann man aber auch Funktionsbezeichner als Infixe einsetzen, wenn man sie in umgekehrte einfache Anführungszeichen setzt: 
x `add` y			= x+y
y `elem` ys
Dies bietet sich vor allem dann an, wenn es der Lesbarkeit des Programms dient, wie im zweiten dieser Beispiele, wo `elem` als Operator "ist Element von" die Verwandtschaft zum mathematischen ∈ Symbol suggerieren soll.

2.1.5 Kommentare und Layout

Wie auch in C gibt es in Haskell zwei Arten von Kommentaren. Ein doppeltes Minuszeichen weist den Rest der aktuellen Zeile als Kommentar aus. An beliebiger Stelle können (auch mehrzeilige) Kommentare eingefügt werden, die in geschwungene Klammern und Minuszeichen eingeschlossen sind. 

add x y	                  -- eine Addition
add x {- Kommentar -} y
In C werden einzelne Anweisungen, Deklarationen, etc. durch Semikolon getrennt, Blöcke werden durch geschwungene Klammern eingegrenzt. Auf ganz ähnliche Weise können Haskell-Programme strukturiert werden. 
let { y   = a*b
    ; f x = (x+y)/y
    }
in f c + f d
Ohne die Semantik der in diesem Beispiel verwendeten let-Struktur erläutern zu wollen, ist klar, dass mit { und } ein Block beschrieben wird, innerhalb dessen Einzeldefinitionen durch ; getrennt werden. In Haskell ist es nicht üblich, die Struktur auf diese Weise explizit zu machen. Statt dessen verwendet man eine als Layout bezeichnete Formatierungstechnik, die hierzu äquivalent ist. Dabei werden Blöcke durch gleiche Einrückungstiefe kenntlich gemacht. Einzelne Deklarationen werden durch Zeilenumbrüche getrennt. 
let y   = a*b
    f x = (x+y)/y
in f c + f d
Dennoch kann die Verwendung der expliziten Formatierung u.U. sinnvoll sein, z.B. wenn man mehrere Deklarationen in einer Zeile unterbringen möchte.

2.2 Typen und Funktionen

2.2.1 Tupel, Listen und Funktionen als Typen

Haskell ist anders als z.B. PERL eine typisierte Sprache. Tatsächlich ist es bei der Durchsetzung einer exakten Typübereinstimmung sogar wesentlich strenger als die meisten imperativen Sprachen. So ist etwa automatisches Type casting nicht möglich. Natürlich bietet Haskell die aus anderen Programmiersprachen bekannte Palette an Standardtypen, wie z.B.: 

Integer, Rational, Char, Bool
Dabei ist darauf hinzuweisen, dass etwa Integer ein idealisierter Ganzzahltyp ist, der prinzipiell keine Größenbeschränkung kennt.

Mit Tupeln wird ein strukturierter Typ zur Verfügung gestellt, der in etwa den record Strukturen in Pascal entspricht. Er ermöglicht es, Variablen (ggf. unterschiedlichen Typs) zusammenzufassen. Tupel werden in Runde Klammern eingeschlossen. 

(3,´x´)                 :: (Integer,Char)
(1,2,1)                 :: (Integer,Integer,Integer)
Wie auch in anderen funktionalen Sprachen spielen Listen in Haskell eine zentrale Rolle ein. Listen können eine Beliebige Anzahl von Elementen desselben Typs enthalten. Hier sind beispielhaft eine Liste von Integer und eine Liste von Listen von Char angegeben: 
[1,2,3]	                :: [Integer]
[[´a´],[´b´,´c´],[]]    :: [[Char]]
[] steht für die leere Liste. Eine Liste kann durch Verkettung von Elementen erzeugt werden, wobei die Kette durch die leere Liste abgeschlossen und der Doppelpunkt als Konstruktor verwendet wird. 
[1,2,3]	entspricht also	1:(2:(3:[]))
Da der Doppelpunkt rechtsassoziativ ist, können die Klammern weggelassen werden. Hier noch drei häufig gebrauchte Funktionen auf Listen: 
length []               = 0
length (y:ys)           = 1+length ys
head (y:ys)             = y
tail (y:ys)             = ys
length liefert die Länge einer Liste, head gibt das erste Element zurück und tail alles, was auf das erste Element folgt (wenn die Liste mindestens ein Element enthält).

Um einen Eindruck von den vielfältigen Möglichkeiten zu geben, Listen zu konstruieren, sind hier einige Beispiele für List comprehensions und Folgen gegeben: 

[ inc x | x <- [1,2,3] ]                    ⇒ [2,3,4]
[ (y,z) | y <- ys, z <- zs, y<z ] 
[1..10], [1,3..5], [1,3..]
Die Liste in der ersten Zeile wird erzeugt, indem der Ausdruck vor dem senkrechten Strich ("Wächter") für alle Elemente aus der angegebenen Liste [1,2,3] ausgewertet wird. Der Pfeil ⇒ steht metasprachlich für "ergibt sich zu". Die zweite Zeile zeigt denselben Mechanismus anhand eines komplexeren Beispiels. In einer imperativen Sprache würde man das mit dem Listenverknüpfungsoperator ++ in etwa formulieren: 
result=[];
for y in ys
  for z in zs
    if y<z then result=result++[(y,z)];
Die dritte Zeile obiger Beispiele ist im wesentlichen selbsterklärend, erwähnenswert ist aber die Möglichkeit, mit [1,3..] eine unendliche Liste zu definieren. Dass diese nicht unmittelbar nach der Definition erzeugt werden kann, ist klar, der Sinn einer solchen Definition ist im Zusammenhang mit verzögerter Auswertung zu sehen.

Schließlich muss noch festgestellt werden, dass auch Funktionen Typen wie alle anderen sind. Insbesondere können Funktionen selbst Funktionen als Parameter nehmen und wiederum Funktionen als Ergebnis liefern. Das bereits bekannte Beispiel einer "Variable vom Typ Funktion" ist: 

add                     :: Integer->Integer->Integer

2.2.2 Polymorphe Typen

Es kommt bisweilen vor, dass die Angabe eines genauen Typs für eine Variable oder eine Ausdruck nicht möglich oder wünschenswert ist. Ein Beispiel hierfür ist die oben definierte Funktion length, die zu einer Liste deren Länge liefert. Gemäß der Definition funktioniert length mit Listen beliebiger Elemente. Um dies zu verdeutlichen, benutzt man bei der Typsignatur-Deklaration anstatt eines konkreten Listentyps wie [Integer] oder [Char] einen allgemeineren, "polymorphen" Typ [a]. 

length                  :: [a] -> Integer
Dabei ist die Typvariable a als universal quantifiziert zu interpretieren, d.h. obige Deklaration ist gültig für alle Typen a. Diese Typsignatur-Deklaration von length gibt einen "passenden" Typ an, doch gibt es auch allgemeinere polymorphe Typen, denen die Definition von length ebenfalls gerecht wird. Beispiele hierfür sind etwa 
[a] -> b, a -> Integer, a -> b, a
Davon ist der letzte Typ, a, der allgemeinste. Jede denkbare Variable wird durch den polymorphen Typ a abgedeckt.

Umgekehrt gibt es polymorphe Typen, denen length nicht entspricht, z.B. 

[a] -> a
Der "wahre" Typ einer Variable oder eines Ausdrucks ist der speziellste, dem die Definition gerecht wird. Im obigen Beispiel ist dies eben genau [a] -> Integer. Dieser "wahre" Typ ist eindeutig bestimmt und wird von Haskells Typsystem automatisch ermittelt.

2.2.3 Definition eigener Typen

Selbstverständlich ist es möglich, eigene Typen, auch polymorphe, zu definieren. Vordefinierte Typen haben gegenüber diesen keine hervorgehobene Stellung. In diesem Unterabschnitt wird die Vorgehensweise zunächst an zwei einfachen Beispielen demonstriert, dann folgt mit der Struktur tree ein komplexeres Beispiel für eine rekursive Definition.

Typdefinitionen werden durch das Schlüsselwort data eingeleitet. Darauf folgt dann mit dem Typkonstruktor der "Name" des zu definierenden Typs. Rechts vom Gleichheitszeichen wird der (oder die) Datenkonstruktor(en) angegeben. 

data Bool               = False | True
In diesem Beispiel wird der nicht polymorphe Typ Bool definiert. Der Typkonstruktor Bool kann im folgenden überall dort auftauchen, wo ein Typ verlangt ist, also insbesondere in einer Typdeklaration rechts von :: . Die beiden Datenkonstruktoren False und True hingegen kann man als Konstanten vom Typ Bool auffassen. Bool ist ein einfacher enumerativer Typ, der nur zwei Werte kennt. Bereits etwas komplizierter ist der polymorphe Typ Point. 
data Point a            = Pt a a
Ein Point vom Typ a wird also konstruiert mit dem Datenkonstruktor Pt gefolgt von zwei Koordinaten vom Typ a. Ein konkreten Beispiel hierfür ist: 
Pt 3 5                  :: Point Integer
Da Typkonstruktoren und Datenkonstruktoren niemals an derselben Stelle verwendet werden können, besteht keine Verwechslungsgefahr. Daher ist es möglich, für beide denselben Bezeichner zu wählen. Dies kann die Lesbarkeit eines Programms verbessern. Eine alternative Typdefinition für Point wäre demnach: 
data Point a            = Point a a
Als Beispiel für eine komplexere Typdefinition soll hier noch eine polymorphe Baumstruktur konstruiert werden. 
data Tree a             = Leaf a | Branch (Tree a) (Tree a)
Zunächst fällt auf, dass die beiden Datenkonstruktoren Leaf und Branch anders als in den bisherigen Beispielen unterschiedliche Parameter erwarten. Ein Blatt Leaf erzeugt aus einem Argument vom Typ a einen Baum, ein Branch vereinigt zwei Teilbäume. Die Typen der Konstruktoren sind also: 
Branch                  :: Tree a -> Tree a -> Tree a
Leaf                    :: a -> Tree a
Um zu zeigen, wie man mit solch einem Typ arbeiten kann, sei hier noch die Definition einer Funktion fringe angegeben, die die Inhalte der Blätter eines solchen Baumes der Reihe nach in einer Liste ablegt. 
fringe                  :: Tree a -> [a]
fringe Leaf x           = [x]
fringe (Branch l r)     = fringe l ++ fringe r
Wie bereits erwähnt ist dient ++ der Verknüpfung zweier Listen.

2.2.4 Typenklassen

Neben der bisher vorgestellten Form von Polymorphismus, dem "parametrischen Polymorphismus", gibt es mit "ad-hoc Polymorphismus" oder überladen noch eine weitere wichtige Form, die in vielen Programmiersprachen (oft implizit) realisiert ist. Parametrischer Polymorphismus ist lässt sich dort einsetzen, wo der konkrete Typ wirklich keine Rolle bei Berechnungen spielt - man denke etwa an die obige Definition der Funktion fringe.

Mit dem Konzept der Typklassen, das hier nur kurz angerissen werden kann, stellt Haskell eine Möglichkeit bereit, kontrolliertes überladen zu nutzen. Dies soll am Beispiel des Gleichheits-Operators == verdeutlicht werden.

Angenommen, es soll eine Funktion elem definiert werden, die für einen Wert eines beliebigen Typs überprüft, ob er in einer Liste (desselben Typs) vorhanden ist. Die Definition einer solchen Funktion (hier in der Infix-Schreibweise, siehe oben) könnte so aussehen. 

x `elem` []    	        = False
x `elem` (y:ys)         = x==y || (x `elem` ys)
|| ist das logische oder. Hierbei tritt das Problem auf, dass die Gleichheit ==, die in der zweiten Zeile der Definition verwendet wird, nicht zwangsläufig auf jedem Typ definiert ist. elem soll demnach nur auf Typen verfügbar sein, für die == mit der gewünschten Semantik (also insbesondere als Operator mit Bool-Funktionswert) definiert ist. Solche Typen werden in einer sogenannten Typenklasse zusammengefasst. Diese gibt i.w. an, welche Operationen und Funktionen für einen Typ dieser Klasse wie definiert sein müssen. 
class Eq a where
      (==)              :: a -> a -> Bool
Alle Typen, die der Klasse Eq angehören, müssen also (==) in der beschriebenen Weise definieren (tatsächlich gehört die Klasse Eq zum Standardumfang von Haskell, ihre Definition ist aber etwas umfangreicher). Man sagt, (==) sei eine Methode von Eq. Nun kann man eine Typsignatur-Deklaration für elem angeben, die klar macht, dass die Definition von elem auf Typen der Klasse Eq beschränkt ist. 
elem                    :: (Eq a) => a -> [a] -> Bool
Um einen konkreten Typ (hier Integer) als zur Klasse Eq gehörig, anders ausgedrückt als eine Instanz von Eq, zu definieren, dient folgende Schreibweise: 
instance Eq Integer where
      x==y              = x `integerEq` y
Dies setzt natürlich die Definition einer geeigneten Funktion integerEq voraus.

2.2.5 Lambda Funktionen

Lambda Funktionen dienen dazu, Funktionen "anonym" definieren zu können, d.h. ohne ihnen einen Namen zuzuweisen. Die Schreibweise von Lambda Funktionen soll zunächst am Beispiel der beiden Funktionen 

inc x                   = x+1
add x y                 = x+y
gezeigt werden. Sie lassen sich alternativ definieren, indem man ihrem Namen die entsprechende Funktionsdefinition in Form eines Lambda- Ausdrucks zuweist. 
inc                     = \x -> x+1
add                     = \x -> \y -> x+y
Vereinfacht gesprochen ist eine Lambda Funktion durch einen Backslash \ und eine Zuordnungsvorschrift gegeben, also im Fall inc durch \x -> x+1. Falls es sich, wie bei add, um eine Funktion mehrerer Parameter handelt, kann man auf eine vereinfachte Schreibweise zurückgreifen. 
add                     = \x y -> x+y
Mit Hilfe dieser Lambda-Schreibweise lässt sich auch die schrittweise Auswertung currifizierter Funktionen mehrerer Parameter, die oben bereits erläutert wurde, gut verdeutlichen. 
add 3 4  ⇒  (\x -> 3+x) 4  ⇒  3+4
Doch wozu sind solche Lambda-Funktionen nütze? Zunächst ist ihre Existenz Ausdruck der Tatsache, dass Funktionen ebenso Typen wie Integer oder Listen sind. Denn genauso, wie man z.B. die Integer-Konstante 3 an beliebiger Stelle im Programm verwenden kann, ohne vorher meinInt=3 zu definieren, kann man so die Funktion \x->x+1 nutzen, ohne ihr vorher einen Namen zugewiesen zu haben. Dass dies nützlich sein kann, soll am Beispiel der Funktion map gezeigt werden, die eine Funktion und eine Liste als Parameter nimmt und die Funktionswerte aller Listenelemente - ebenfalls in einer Liste - zurückliefert. 
map                     :: (a->b) -> [a] -> [b]
So kann man map z.B. auf die Funktion inc und eine Integer-Liste anwenden. 
map inc [1,2,3]         ⇒ [2,3,4]
In diesem Fall ist die Funktion inc bereits vordefiniert. Im allgemeinen muss dies aber nicht der Fall sein, und man wird möglicherweise nicht extra eine neue Funktion definieren wollen, nur um mit map eine Liste zu erzeugen. 
map (\x -> x+1) [1,2,3] ⇒ [2,3,4]

<-zurück ^Inhalt ->weiter