Einführung

... [ Seminar "Einführung in die funktionale Programmiersprache Haskell" ] ... [ Inhaltsverzeichnis ] ... [ Zurück ] ... [ Weiter ] ...

Übersicht: Einführung

Vorbemerkungen

 Diese Arbeit ist der neunte Beitrag zu der insgesamt fünfzehnteiligen Seminarreihe „Einführung in die funktionale Programmiersprache Haskell“ im Wintersemester 2003/04 an der Fachhochschule Wedel. Im Mittelpunkt steht das Konzept der unendlichen Listen und deren Darstellung in Haskell. Die Grundlagen für diese Seminararbeit, insbesondere das Thema "Endlichen Listen", wurden in den Arbeiten 1-8 dargestellt, so dass auf diese nur kurz zu Beginn und im Verlauf nur am Rande in Form von Rückblicken auf bereits bekannte Definitionen noch einmal eingegangen wird.

Rückblick

 Bei der Betrachtung von endlichen Listen wurden die Eigenschaften von unendlichen Listen bereits teilweise angesprochen. Im Folgenden sollen diese nocheinmal aufgegriffen und anschliessend weiter vertieft werden. In diesem Zusamenhang wird schliesslich auch auf Anwendungen eingegangen, die unendliche Listen nutzen sowie deren Bedeutung im Allgemeinen.

Die Definition einer endlichen Liste von Integer-Werten in einem Intervall von m bis n läßt sich durch die Notation [m..n] ausdrücken. Bei der Darstellung einer unendlichen Liste ändert sich die Notation im Prinzip nur in der Hinsicht, dass bei der Darstellung die obere Intervallgrenze n weggelassen wird.
Während einer Session kann eine uendliche Liste z.B. durch Ausdruck ?[1..] auf dem Bildschirm ausgegeben werden. Jedoch würde die Ausgabe theoretisch uendlich lange dauern und wird deshalb vorzeitig unterbrochen. 
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,{Interrupted}
Unendliche Listen können genauso wie endliche Listen in Programmen verwendet werden. Eine Funktion kann beispielsweise einer unendliche Liste als Argument erhalten und eine endliche Liste als Resultat zurückliefern. Im Folgenden sollen kurz einige Beispiele für Anweisungen gezeigt werden, die sowohl für endliche als auch unendliche Listen gültig sind: 
head [n..] = n 
take n [1..] = [1..n]
[m..]!!n = m + n
Weiterhin ist es möglich uenendliche Listen im Zusammenhang mit List Comprehensions zu verwenden. Der Ausdruck 
[square x | x <- [1..], odd x]
liefert als Resultat eine Liste der Quadrate aller ungeraden Zahlen. Wichtig ist jedoch die Unterscheidung von unendlichen Listen in Haskell und unendlichen Mengen in der Mathematik. Der Ausdruck für die Menge der Quadratzahlen <10 wird in der Mengentheorie durch die Notation 
{x² x ∈ {0,1,2,3,...}; x² <10}
dargestellt. Die entsprechende Darstellung einer List Comprehension würde folgendermaßen ausgedrückt werden: 
?[square x | x<-[0..], square x<10] 
[0,1,2,4,9
Was ist passiert?
Der Rechner wertet die ersten drei Elemente aus und gerät dann in eine Endlosschleife, da er die Quadrate der einzelnen Elemente der uenendlichen Liste ab 4 aufwärts gegen 10 prüft. Ab dem Quadrat der Zahl 4 ist die Resultatliste also undefiniert und es ergibt sich folgende Teilliste: 
0,1,4,9,⊥
Allerdings ist es nicht schwer den Ausdruck so umzuformen, dass er als Ergebnis eine endliche Liste aller Quadrate <10 liefert. Die List Comprehension ist Äquivalent zum Ausdruck 
filter (<10) (map square [0..])
Wird hier die Funktion filter durch die Funktion takeWhile ersetzt, erhält man bei der Auswertung innerhalb einer Session das erwartete Ergebnis. 
? takeWhile (<10) (map square [0..])
[0,1,4,9]

Beispiel: Generieren von Primzahlen

 Eine natüliche Zahl ist prim, falls sie nur durch sich selbst und durch eins teilbar ist. Ein bekannter Algorithmus zu Erzeugung von Primzahlen ist das "Sieb des Eratosthenes" (Nach Eratosthenes von Kyrene, hellenistischer Gelehrter, um 276-195 v. Chr.) , welcher auf folgendem Denkansatz beruht:
Streicht man aus der Menge natürlicher Zahlen von 2 bis n, beginnend mit 2, nacheinander alle Vielfachen der jeweils noch verbleibenden Zahlen heraus, enthält die Restmenge nur noch Primzahlen.

Das "Sieb des Eratosthenes" funktioniert im klassischen Sinne folgendermaßen:
1. Schreibe alle natürlichen Zahlen von 2 bis zu einer beliebigen Zahl n auf.
2. Streiche alle Vielfachen von 2 heraus.
3. Gehe zur nächstgrößeren nichtgestrichenen Zahl und streiche deren Vielfache heraus.
3. Wiederhole 3. sooft es geht.
4. Die übriggebliebenen Zahlen sind Primzahlen.

Für diesen Algorithmus soll nun eine Funktion entwickelt werden, die als Ergebnis eine unendliche Liste mit allen Primzahlen zurückliefert. Wir definieren uns also die Funktion primes mit folgender Signatur: 
primes :: [Int]

primes     = sieve [2..]
sieve      = x : sieve [y |y <- xs , y mod x > 0]
Die Funktion primes delegiert das Herausfiltern der nicht-primen natürlichen Zahlen an die Funktion sieve weiter, welche welche mit Hilfe der bekannten List Comprehensions jedes Element y der Liste auf ganzahlige Teilbarkeit mit x testet und als Ergebnis eine Liste mit allen Primzahlen zurückgeliefert.

Bemerkungen

 Warum werden unendliche Listen genutzt?
Durch die Verwendung von unendichen Listen werden Programme abstrakter und sind damit zunächst einfacher zu entwickeln. Als konkretes Beispiel kann das eben genannte zur Erzeugung von Primzahlen dienen. Wäre dieses Beispiel mit Hilfe einer endlichen Liste realisiert worden, dann hätte im Vorraus festgelegt werden müssen, wie lang die Liste sein soll. Bei der in unserem Beispiel verwendeten unendlichen Liste ist das nicht nötig, da einfach nur der jeweils benötigte Listenteil ausgewertet wird.
... [ Seminar "Einführung in die funktionale Programmiersprache Haskell" ] ... [ Inhaltsverzeichnis ] ... [ Zurück ] ... [ Weiter ]