Quicksort in C
Zunächst zeigen wir, was für ein Bohei eine Sortierung in einer beliebigen imperativen Sprache ist. So haben diejenigen die eine solche beherrschen, einen direkten Vergleich; alle anderen sehen den Unterschied in Länge und Lesbarkeit.
/**
* quick-sort (part of) an array of integers
* @param a the array
* @param lo beginning of the range to sort
* @param hi end of the range to sort
*/
void qsort(int a[],int lo,int hi) {
if (lo<hi) { /* Gibt es etwas zu tun? (leere Liste -> fertig) */
/* lo..hi ist der Bereich den zu sortieren wir gebeten wurden.
l..h wird spaeter den Teilbereich davon bezeichnen, der tatsaechlich unsortiert ist.
zunaechst sind beide Bereiche gleich.
x ist das Pivotelement, die Wasserscheide. */
int l=lo;
int h=hi;
int x=a[hi];
do {
while((l<h)&&(a[l]<=x)) /* bereits sortierte Element am Bereichsanfang ueberspringen */
l=l+1;
while((h>l)&&(a[h]>=x)) /* bereits sortierte Elemente am Bereichsende ueberspringen */
h=h-1;
/* Wenn noch zu sortierende Elemente im Teilbereich uebrig sind, tauschen das
erste und das letzte der Elemente die der Sortierung beduerfen die Plaetze. */
if (l<h) { /* Gibt es etwas zu sortieren? */
int t=a[l]; /* temporaeres Element für Dreieckstausch */
a[l]=a[h];
a[h]=t; }
} while(l<h); /* Wiederholen, bis Bereich sortiert */
t =a[l];
a[l] =a[hi];
a[hi]=t;
qsort(a,lo,l-1); /* Elemente "links" (kleiner als x) sortieren */
qsort(a,l+1,hi); }} /* Elemente "rechts" (groesser oder gleich x) sortieren */
Haskell
Nun die Haskell-Variante. Man beachte die Kürze und Ausdruckskraft der Sprache. Wer auch nur in einer einzigen Mathevorlesung wach war, versteht Ausdrücke wie elemente_kleiner_als_x = [y | y <- xe, y < x]: alle y
für die gilt y ist Element aus xe und y ist kleiner als x
. Schwieriger wird's nicht mehr.
qsort [] = [] -- qsort auf einer leeren Menge gibt... eine leere Menge. ("this part is simple")
qsort (x:rest) = qsort elemente_kleiner_als_x ++ [x] ++ qsort elemente_groesser_oder_gleich_x
where
-- alle Werte y aus "rest" für die gilt "y ist kleiner als x"
elemente_kleiner_als_x = [y | y <- rest, y < x]
-- alle Werte y aus "rest" für die gilt "y ist größer oder gleich x"
elemente_groesser_oder_gleich_x = [y | y <- rest, y >= x]
Die sortierte Liste ergibt sich also, in dem man aus der erhaltenen Liste ein Element x
entnimmt, und dann alle kleineren Werte sortiert und links anklebt, und alle größeren Werte sortiert und rechts anklebt.
Zur Erinnerung: kleinere Werte als der Erste, x
, mag es in der Ausgangsliste durchaus geben; x
ist ja zunächst nur der erste, nicht aber der geringste Wert — diesen Zustand wollen wir ja erst herstellen.
Noch kürzer:
qsort [] = []
qsort (x:a) = qsort [ y | y <- a, y <= x ] -- alle Elemente "links von x" sortieren
++ [x] -- x (als Liste) anhängen
++ qsort [ y | y <- a, y > x ] -- alle Elemente "rechts von x" sortieren und anhängen
Grau ist alle Theorie! Wir prüfen!
> qsort [1,9,23423,3,5]
[1,3,5,9,23423]
Das war beinahe zu einfach. Versuchen wir doch mal, unsere Funktion zu erschrecken...
> qsort ["katze","hund","giraffe","maus"]
["giraffe","hund","katze","maus"]
Wir stellen fest: das funktioniert auch noch für mehrere Datentypen! Offensichtlich ist es einerlei was in einer Liste steht, solange die Elemente untereinander vergleichbar sind! Wir prüfen auch diese Theorie:
> qsort [5,4,3.14]
[3.14,4.0,5.0]
Läuft. Gegenprobe:
> qsort ["giraffe", "arsch", 15, "käsefondue", 3.14]
Isnichdrin, Hoschi!
Ocaml
Und noch einmal, dieses Mal in Objective caML. So sehen wir, daß die Syntax von Haskell selbst für eine funktionale Sprache (die ocaml ja auch sein kann) elegant ist.
let rec qsort = function (* sei qsort eine rekursive Funktion... *)
| [] -> [] (* leer bleibt leer, da helfen keine Pillen *)
| x :: rest -> (* andere Listen zerfallen in den Kopf x und einen Rest *)
let rec split = function (* sei split eine rekursive Funktion *)
| [] -> [], [] (* eine leere Liste kann in zwei leere Listen geteilt werden *)
| y :: m -> let a, b = split m in (* fuer andere Listen eine Liste aller y kleiner als x
und eine Liste aller y groesser gleich zurueckgeben *)
if y < x then y :: a, b else a, y :: b
(* gerade definierte Funktion split auf "rest" anwenden *)
in let kleiner_x, groesser_gleich_x = split rest
(* gerade definierte Funktion qsort anwenden: sortierte Liste bildet sich aus alle
Elemente kleiner als x sortiert, x, alle Elemente groesser als x sortiert *)
in (qsort kleiner_x) @ [x] @ (qsort groesser_gleich_x);;
Offensichtlich fehlt hier die Mengenbeschreibung (alle y aus m, für die gilt...
); wir müssen sie selbst (als Funktion split) nachbauen.
Von Äpfeln und Birnen
Während Haskell eine rein funktionale Sprache ist, läßt sich in Ocaml auch objekt-orientiert oder imperativ arbeiten. Im schlimmsten Fall erschwert dies die Lesbarkeit von in Ocaml verfassten Quelltexten; im besten begünstigt es eine "sanfte Migration" von einem Paradigma zum anderen bzw. stellt unterstützt für jedes Problem das geeignete Paradigma.
Rein funktionale Sprachen haben keine Nebenwirkungen; es gibt keine Zustandsvariablen, die während einer Berechnung verändert werden. Die Auswertung eines Ausdrucks ergibt stets den gleichen Wert (referential transparency
); die Reihenfolge der Berechnungsschritte ist nicht festgelegt. (Dies zu verstehen fällt leichter, wenn man ein funktionales Programm als eine mathematische Funktion und nicht wie ein imperatives Programm ("Kochrezept") betrachtet.)
Ein übliches Merkmal funktionaler Sprachen ist lazy evaluation — Werte werden erst berechnet, wenn sie tatsächlich benötigt werden, so daß man auf unendlich grossen Datenmengen ("alle Primzahlen"
) operieren kann. Lässt man in einer funktionalen Sprache Nebenwirkungen (Variablen, Ein-/Ausgabe, ...) zu, kann die Reihenfolge der Auswertung einzelner Ausdrücke plötzlich wichtig werden; dies betrifft auch die "Bedarfsauswertung." Während Haskell üblicherweise lazy
auswertet, muß dies in Ocaml speziell angefordert werden (Design-Begründung); andersherum muß dafür in Haskell speziell sequentielle Verarbeitung angefordert werden (Monaden
für die Abarbeitung von Ausdrücken ohne referential transparency
, z.B. IO).
Typen
Ein beliebter Streitpunkt ist die Typisierung von Variablen.
In schwach typisierten Sprachen
können Variablen spontan in Kontexten verwendet werden, die nicht ihrem Typ entsprechen (Zahlen als Zeichenketten etc., <?php $a="12"; $b="34"; $c="$a$b"; $d=$c+1; print "$d\n"; ?>). In stark typisierten Sprachen
ist eine explizite Umwandlung in den gewünschen Typ notwendig. stark vs. schwach
definiert was geschieht, wenn eine geforderte Operation für einen Variablentyp nicht definiert ist — wird die Variable stillschweigend in einen geeigneten Typ überführt, oder ein Fehler geworfen?
In statisch typisierten Sprachen
wird beim Schreiben bzw. Übersetzen des Programms festgelegt, welchen Typ die Inhalte einer Variablen haben kann (int x — x kann nur integers
, ganze Zahlen also, aufnehmen).
In dynamisch typisierten Sprachen
klebt die Typinformation gleichsam am Wert der Variablen statt am Namen; die Variable kann nacheinander Werte verschiedenen Typs annehmen. Ob eine Operation für eine Variable definiert ist, kann also bei dynamisch typisierten Sprachen erst zur Laufzeit abschließend beantwortet werden.
Dynamische Typen
sind u.a. für container
interessant.
Wenn ein Bus einen Vektor Passagiere
hat, möchte ich da einen Flötisten und eine Ingenieurin hinterlegen können und nachher einen Flötisten und eine Ingenieurin wieder herausbekommen — und nicht zwei anonyme Passagiere, denen ich erst die Flötentöne wieder beicasten muß.
Statisch typisierte Sprachen zerfallen in
explizit typisierte Sprachen
und
implizit typisierte Sprachen
. Im ersten Fall muß ich aufschreiben, welchen Typ die Inhalte einer Variable haben können, im zweiten findet es der Übersetzer selbst heraus. (Einfaches Beispiel: Wenn meine Funktion zwei Werte annimmt und als Ergebnis die Summe beider zurückliefert, wird es sich wohl um Zahlen handeln. Dieses Ausknobeln heisst man
type inference
.)
Das worst case scenario
ist hier Java; die Typinformation klebt am Namen statt am Inhalt der Variablen, und ich muß mir überdies die Finger blutig schreiben: Foo foo=new Foo(); — links wird festgelegt, dass foo nur Objekte vom Typ Foo aufnehmen kann; rechts wird ein solches hergestellt. Die Information, daß es um Objekte vom Typ Foo geht, wirkt redundant; der Konstruktur Foo() liefert definitionsgemäß ein Foo-Objekt; damit sollte der Typ der Variablen foo (wenn man schon statisch typisieren will) unmittelbar ableitbar sein.
Dass das Java-Typenmodell die Basistypen zudem sowohl als Skalare als auch als Objekte kennt (und man oft zwischen beiden hin- und her-konventieren muß), läßt das Modell nicht wirklich gelungener erscheinen.
Man vergleiche
public Vector aList = new Vector; /* sei aList eine Liste */
public int aNumber = 5; /* sei aNumber ein Ganzzahl-Skalar mit dem Wert 5 */
public int anotherNumber; /* hier soll unser Ergebnis wohnen */
/* aus dem Skalar ein Objekt, denn nur solche dürfen in die Liste */
aList.addElement(new Integer(aNumber));
/* Da Java statisch typt, ist in der Liste jetzt ein generisches Object-Objekt und kein
Integer-Objekt; Java "vergisst" also umgehend, was genau wir in die Liste getan haben.
Mit getElement() holen wir das Object-Objekt aus der Liste, und typecasten das zurück
in ein Integer-Objekt, denn nur auf ein Integer-Objekt dürfen wir intValue() anwenden,
um unsere 5 nach langer Reise als Skalar wieder zu sehen. Diesen Wert dürfen wir
dann der anderen Skalar-Variable "anotherNumber" zuweisen und sind in jeder
Beziehung fertig. */
anotherNumber = ((Integer)aList.getElement(0)).intValue();
Wie kompakt hingegen die Python-Lösung:
aList = []
aNumber = 5
aList.append(aNumber)
anotherNumber = aList[0]
Taaadaaa!
Fazit
Ocaml und Haskell bieten starke implizite Typen an. Damit kann man "arbyten." Sie bieten außerdem ein Programmierpragma weit jenseit von "prozedural" und "wieso das denn?" an, das auf jeden Fall einen Blick wert ist, selbst wenn man sich dann entscheidet, nicht damit arbeiten zu wollen: Sprachen lernen macht schlau, und das gilt nicht nur für Natursprachen. Selbst, wenn die Schlauheit im konkreten Fall im Wissen darüber besteht, wie schlecht Java wirklich ist.
Ressourcen
