Meine Damen und Herren,
wir waren stehen geblieben bei dieser Folie über Häufigkeitszählung,
bei der ich Ihnen vorführte, wie man ein Histogramm berechnet und auf
welche Art und Weise man hierbei Listenbeschreibungen einsetzt.
Die nächsten Folien sind zunächst einmal nur Wiederholung von Dingen,
die wir eigentlich schon alle kennen, mit dem Ziel, anschließend eine
Einsicht zu gewinnen.
Wir wissen also bereits, was ein Funktional ist, nämlich eine
Funktion, die andere Funktionen als Parameter haben kann, was wir hier
am Beispiel von Map und von Filter nochmal aufgeführt haben.
Und die Frage lautet also, wie kann man solche Funktionen aufrufen,
wenn man die Argumente vorher eigentlich definieren muss und wie
bekommt man Funktionen als Resultat einer solchen Funktion.
Und zum Beantworten der zweiten Frage wussten wir also bereits, dass
wir mit dem Rückstrich,
den wir hier benutzen, anstelle des Lambdas in
der Lache sind, Werte hinzuschreiben, die ihrerseits Funktionen sind.
Und der Unterschied ist also eigentlich nur der, dass wir da eine
Funktionsdefinition angeben, die aber namenlos ist, die also keinen
Bezeichner trägt und die Notation und der Gebrauch entspricht dem, was
wir im Lambda-Kalkül gelernt haben.
Und auf die Art und Weise sind wir also beispielsweise in der Lache,
die Map-Funktion auch anzuwenden, selbst wenn die Funktion, die wir
auf die Liste anwenden wollen, im Augenblick doch gar nicht mit Namen
bekannt ist.
Dann schreiben wir sie einfach in der Form hin, wie hier Lambda X mit
dem Rumpf X plus 2 und wenn ich das auf diese Liste anwende, dann
wird, wie von Map erwartet, die Funktion auf jedes Listenelement
angewandt, also überall wird 2 addiert.
Und wenn ich hier eine solche Lambda-Definition angebe mit einer Liste
als Parameter und als Rumpf dann hinschreibe, nimmt den Rest der Liste
und konkateniere ihn mit sich selbst und das auf alle Elemente
anwende, dann sehe ich also im ersten Argument habe ich hier nur eine
Liste aus einem Element, das ist das X, die XS-Liste ist leer, die
wird mit sich selbst konkateniert, also kommt hier im Ergebnis die
leere Liste heraus.
Hier habe ich 2 Elemente, 2 ist das X, die Liste, die nur aus 3
besteht, ist das XS, die wird mit sich selbst konkateniert, also kommt
die 3 zweimal und hier kommt also die 5, 6 nach dem gleichen Schema
ebenfalls zweimal.
Das nochmal als Wiederholung und Illustration anonymer Funktionen.
Wenn wir uns jetzt fragen, was ist eigentlich der Zusammenhang
zwischen Funktionen und Relationen, dann wissen wir zweierlei.
Erstens, jede Abbildung, also jede Funktion ist zugleich eine
Relation, bei der ich aber weiß, dass für die N-1 ersten Argumente
immer nur ein einziger Funktionswert existiert.
Das eben ist die Auszeichnung Funktion, eine Relation, die aber nicht
mehr deutlich ist.
Ich kann aber eine Funktion auch noch in anderer Art und Weise
gebrauchen und das kommt in der Informatik öfters vor, um eine
Relation zu definieren.
Wenn ich zum Beispiel eine N-stellige Relation habe mit Argumenten X1
bis Xn und einem Ergebnisbereich X, dann definiert mir das insgesamt
eine N-plus-1-stellige Relation der Argumente der Funktion mit ihrem
jeweiligen Funktionswert.
Das kann ich so interpretieren, dass ich also zum Beispiel sage, die
Konjunktion bei Bool'schen Größen definiert eine 3-stellige Relation,
die ich hier angegeben habe.
Wenn die beiden ersten Argumente true sind, ist das Gesamtergebnis
auch true und so geht es weiter, die Wahrheitstabelle ist Ihnen
bekannt.
Und das kann ich jetzt spezialisieren.
Ich kann zum Beispiel also fragen, gegeben sei diese Tabelle, jetzt
halte ich ein Argument fest, zum Beispiel das erste und nehme an, dass
das immer true sei.
Dann scheiden diese beiden unteren Fälle aus und was bleibt dann
übrig?
Dann bleibt dieser Teil der Tabelle übrig und
da ich das erste true jetzt festgehalten habe, interessiert es mich
sozusagen nicht mehr weiter, dass was eigentlich übrig bleibt, ist
dieser Teil.
Und was ist das?
Das ist nicht mehr eine 2-stellige Funktion, sondern eine 1-stellige
Funktion samt ihrem Ergebnis.
Und diese 1-stellige Funktion bildet also true auf true ab und false
auf false.
Nun das ist trivial, aber für das Vorführen des Prinzips reicht es
vollkommen aus.
Ich bekomme also diese Relation hier unten und auch die definiert eine
Funktion und die Funktion, die können wir auch direkt hinschreiben.
Die Frage lautet, wie können wir die hinschreiben?
Mit unseren bisherigen Hilfsmitteln.
Also ich führe nochmal vor, was wir bisher haben.
Wir haben bisher gesehen gehabt, dass die Konjunktion, ich schreibe es
jetzt in Präfixform, für zwei Werte p und q definiert ist.
Und wenn Sie zurückblättern, dann finden Sie also eine Folie, auf der
genau drauf steht, was hier auf der rechten Seite steht.
Es sind mehrere Fälle zu unterscheiden.
Das schreibe ich jetzt nicht hin.
Und jetzt ist die Frage, kann ich irgendeine Funktion, Konjunktion,
Querstrich definieren, die nur noch ein Argument nimmt und zwar das q
und mir dann, wie hier definiert, das Ergebnis liefert.
Wie würde ich die definieren?
q gleich q, sagt er.
Richtig.
Das ist eine Möglichkeit.
Können Sie es machen, ohne den Rumpf anzugeben?
Das ist die interessante Frage.
Ich behaupte, ich kann das Ding hinschreiben, ohne die rechte Seite
anzugeben.
Ich kann doch einfach hinschreiben, eine neue Funktion f, also dieses
quer, mit einem Argument und das definiere ich jetzt als und, und,
true, true.
Ich brauche mich also nicht einmal mehr darum kümmern, wie die
Konjunktion definiert ist.
Ich gebe einfach als Rumpf an, das ist dasselbe, was du bekommst, wenn
du das erste Argument der Konjunktion festsetzt auf true.
Genauso könnte ich so ein einstelliges oder definieren, käme etwas
anderes raus.
Ich brauche mich nicht darum zu kümmern.
Also das eine Argument kann ich einfach weglassen, in dieser Hinsicht.
Wo haben wir das schon gehabt?
In welchem Zusammenhang haben wir sowas schon gesehen, ist die Frage.
Nun, ich habe Ihnen mehrfach Beispiele angegeben, wo ich zum Beispiel
hinschrieb, Map und jetzt glaube ich als Funktion an, plus zwei und
dann irgendeine Liste.
Das ist exakt dasselbe Beispiel.
Ich habe eine Funktion angegeben, die ist einstellig.
Es fehlt nämlich bei der Addition der erste Operand.
Das ist das eine Argument, was mir noch fehlt.
Das andere Argument habe ich angegeben.
Was habe ich hier gemacht?
Ich habe eine Funktion angegeben, die ist einstellig.
Das andere Argument habe ich festgesetzt.
In diesem Fall auf true.
Also wir haben diese ganze Konstruktion schon öfters gesehen und in
der Tat, das ist carrying, so wie wir das bisher schon mehrfach
benutzt haben.
Was also, ich wiederhole die Notation erklärt, warum wir sagen, eine
Funktion mit N Argumenten ist eigentlich eine Abbildung des ersten
Arguments auf eine Funktion mit N-1 Argumenten.
Nämlich von T2 bis TN.
Und so weiter.
Und zum Schluss ist es eine Abbildung einer nullstelligen Funktion,
die nur noch das T ergibt, als Ergebnis, wenn ich sämtliche Argumente
festgelegt habe.
Und das ist also eine Technik, die wir jetzt schon mehrfach benutzt
haben.
Und für die es auch noch Grundfunktionen gibt in Haskell, die im
Predictor definiert sind.
Da gibt es die Operation Carry, die sagt, nimm zunächst einmal ein
paar von Argumenten, gegeben als Tuble.
Und das als Abbildung nach irgendeinem anderen Typ G.
Und fabriziere daraus eine Abbildung, die zwei Argumente hat, vom Typ
A, vom Typ B und dann ein Ergebnis vom Typ G funktioniert.
Und die umgekehrte Operation Uncarry macht genau das Gegenteil.
Sie nimmt also eine Funktion mit zwei Argumenten und macht daraus eine
Funktion, die ein paar von Argumenten nimmt.
Also am Beispiel, das plus zwei, was ich gerade zitiert habe, wenn ich
diese Funktion nehme und auf drei anwende, kommen fünf heraus.
Und was ist das also eigentlich?
Das ist genau die Anwendung auf die einstellige Funktion.
Und Sie können das also auch mit dem Carry noch in anderer Form
hinschreiben.
Sie können also definieren Carry A 2,3 als Paar und dazu brauchen Sie
aber eine Funktion.
Und wenn ich da jetzt davor schreibe, als Funktion plus, dann bekomme
ich hinterher als Ergebnis heraus, das ist genau die Funktion, die 2
plus 3 addiert.
Das führt also als Ergebnis zu der Funktion 2 plus 3.
Wir brauchen es aber meistens nicht in dieser Form, sondern in der
Form, dass wir also einfach Funktionen hinschreiben, bei denen
zunächst mal noch Argumente fehlen und zwar regelmäßig ist es das
erste oder das erste und zweite oder das erste und zweite und dritte
Argument, was uns fehlt.
Und der ganze Sinn dieser Folien war jetzt zunächst mal, dieses
nochmal in Erinnerung zu rufen, dass wir also Funktionen hinschreiben
können, bei denen die Anfangsargumente noch offen sind und die
Endargumente gegeben sind.
Solche Funktionale werden also häufig verwendet, wenn das gleiche
Definitionsschema vorkommt.
Haben wir schon bei der Faltung gesehen.
Sie haben dann in der Literatur auch einen Namen, sie heißen
Programmgeneratoren.
Und mit Currying genügt es also nur einen Teil der Argumente beim
Aufruf anzugeben.
Und das, was man rausbekommt, ist eine neue Funktion, bei der die
ursprünglich aufgerufene Funktion mit den gegebenen Argumenten
partiell ausgewertet wird.
Die restlichen Argumente fehlen noch.
Diese Tätigkeit des partiellen Auswertens ist im Übrigen eine der
wesentlichen Operationen, die wir in vielen praktischen Anwendungen
antreffen.
Nämlich immer dann, wenn irgendeine Tätigkeit erforderlich ist, die
sich in Einzeltätigkeiten zerlegt.
Und die Einzeltätigkeiten werden von verschiedenen Rechnern oder von
verschiedenen Personen ausgeführt.
Dann nimmt der Erste die Daten, die Argumente und sagt, ja, ich kann
ein Stück von dem Ding berechnen.
Und diese teilweise ausgewertete Rechnung, die gibt er an den Nächsten
weiter und der sagt, ja, jetzt kann ich ein Stück weiter rechnen.
Und das ist eine Methode, die im verteilten System, in den
Multiagentensystemen sehr häufig angewandt wird.
Soviel zu Funktionalen und zum Teil als Anwendung, zum Teil als neuer
Punkt, nun zum Thema unendliche Listen.
Eine unendliche Liste ist eine Liste mit abzählbar unendlich vielen
Elementen.
Und die kann ich in Haskell hinschreiben.
Nämlich mit meinem enum from, was wir schon kennengelernt haben.
Enum from n, oder wir hatten es auch in dieser Form geschrieben, n
Punkt Punkt,
ist eine Liste, die bei n anfängt.
Dann kommt n plus 1, n plus 2 und so weiter.
Ich habe aber keinen Endwert angegeben.
Also geht sie ad infinitum.
Ja, was kann ich im Rechnen auf dem Rechner, der ja nur einen
endlichen Speicher hat und endlich viel Zeit hat, mit solch einer
Sache eigentlich anfangen?
Und die erste Antwort dazu lautet, wenn Sie das nur einfach so
hinschreiben, enum from 1, dann jagen Sie Ihren Rechner in eine
Endlosschleife, der produziert nämlich die Liste 1, 2, 3, 4, 5, 6, 7
und so weiter.
Und das macht er bis morgen früh immer noch und im neuen Jahr macht er
das auch noch.
Es sei denn, Sie unterbrechen das.
Das ist also das Beispiel einer Endlosschleife zunächst einmal.
Für den Fall aber, dass Sie sagen, nimm eine solche Liste und jetzt
schau doch mal irgendein Element nach.
Sie erinnern sich, der doppelte Ausruf in Zeiten war der
Indexieroperator in der Liste.
Wir schauen also hier das Element mit Index 2350 nach, gezählt ab 0,
also ist es das 2351.
Element der Liste insgesamt.
Und jetzt bringt er uns ein Ergebnis, jetzt bringt er uns keine
Endlosschleife.
Wie kommt das?
Das erste war also offensichtlich etwas, was man nicht hinschreiben
darf.
Und das zweite unterscheidet sich von der ersten Anwendung doch nur
dadurch, dass ich das Resultat, von dem ich gerade festgestellt habe,
es gibt es gar nicht, weil der endlos rechnet, noch indiziert habe und
jetzt funktioniert es plötzlich.
Wie kommt das?
Was haben wir da für Ideen?
Sie können beides ausprobieren.
Dass das erste nicht geht und dass das zweite funktioniert.
Nun die Antwort ist sehr leicht und wir erinnern uns daran, dass es da
etwas gab wie faule Auswertung.
Der Rechner sagt im zweiten Fall, ja in NUMFROM 1, das ist das erste
Argument des Indizieroperators und dann soll ich wohl also diese Liste
berechnen, aber ich bin faul, ich mag nicht.
Also werde ich nur unter großem Stöhnen und wütendem Geschrei dir ein
Element nach dem anderen liefern, solange bist du zufrieden bist.
Ja und er fängt also an und liefert uns die Elemente 1,2,3,4,5 und so
weiter.
Wir sind immer noch nicht zufrieden und nach 2350 sagt der
Indizieroperator, Hurra, jetzt bin ich zufrieden, jetzt kann ich das
Resultat ausrechnen.
Ja und dann sagt das NUMFROM, prima und jetzt kann ich mich schlafen
legen.
Mehr brauchst du also offensichtlich nicht.
Also der Unterschied zwischen dem ersten Beispiel und dem zweiten
Beispiel besteht offenbar darin, dass wir im ersten Beispiel gesagt
haben, du musst mir nacheinander die Listenelemente liefern und wir
haben keine Bedingungen gegeben, unter welchen Umständen wir
zufriedengestellt sind.
Im zweiten Fall haben wir eine Bedingung angegeben, wann wir zufrieden
sind und soviel hat er uns geliefert und mehr brauchen wir auch nicht.
Das ist also die Feststellung, was hier passiert.
Nur die Argumente werden berechnet, die benötigt werden.
Wir haben faule Auswertung benutzt.
Und was da tatsächlich passiert, habe ich Ihnen hier jetzt auch im
Detail aufgeschrieben, natürlich nicht für 2350, das ist auch
uninteressant, sondern für den Index 2.
Und ich habe hier oben nochmal hingeschrieben, wie die
Indizieroperation definiert ist.
Sie liefert also das erste Element bei einer Liste mit mindestens
einem Element und andernfalls kann ich mit N plus 1 indizieren und
bekomme dann auf die Restliste angewandt das Ergebnis mit Index N.
Und wenn ich jetzt diese Konstruktion ansehe, dann sagt er ja, enum
from 1 indiziert mit 2.
Das ist nach diesem Schema offensichtlich also 1, zusammengesetzt mit
der Restliste, die Restliste fängt bei 2 an, also enum from 2.
Und dieses ganze Ding wird indiziert mit 2.
Und nach dieser Gleichung kannst du jetzt die 1 weglassen, dann bleibt
die Restliste mit 2 übrig.
Und die wird indiziert mit 1.
Und jetzt geht das ganze Ding noch einen Schritt weiter.
Dann sind wir bei enum from 3, indiziert mit 0.
Ja, und das ist die Liste, die mit 3 beginnt, dann enum from 4 umfasst
und mit 0 indiziert wird.
Und jetzt brauche ich für das Gesamtergebnis das Ergebnis von enum
from 4 nicht mehr.
Weil nach dieser oberen Definition das XS nicht notwendig ist.
Ich brauche bloß das X.
Und in Folge dessen kann ich an dieser Stelle das Ergebnis 3 liefern.
Und den ganzen Rest habe ich nicht berechnet.
Also faule Auswertung führt in einem solchen Fall dazu, dass von einer
Liste immer nur die Elemente berechnet werden, die tatsächlich
notwendig sind.
Und die restlichen Elemente werden gar nicht berechnet.
Das können wir praktisch anwenden in verschiedenen Zusammenhängen.
Zum Beispiel kann ich also eine Liste hinschreiben, und das ist ein
Standardoperator Repeat, der immer denselben Wert beliebig oft
wiederholt.
Das Ganze ist also definiert als Repeat X.
Und das ist die Liste, die mit X anfängt und dann Repeat X hintendran
hat.
Und wenn Sie fragen, wann hört das auf?
Die Antwort lautet, es hört nie auf.
Sie bekommen beliebig viele Xen.
Und wozu kann das gut sein?
Die Antwort ist, es ist genauso gut und schlecht, wie das Enum From 1,
was wir gerade gesehen haben.
Sie können auf eine solche Liste jetzt irgendwelche weiteren
Operationen abliefern und anwenden und das liefert Ihnen als Argumente
so viele As, wie Sie brauchen.
Und wenn Sie keine mehr brauchen, dann hört auch das Repeat auf.
Tolle Auswertung.
Noch häufiger ist die Konstruktion des Iterates, bei der wir ein
Funktional definieren.
Es nimmt als erstes eine Funktion F als Parameter, dann ein Argument X
und liefert uns als Ergebnis das Argument X, konkaliniert mit Iterate
F, aber diesmal jetzt angewandt auf Fx.
Das heißt, das nächste Element ist Fx und die Liste, die wir insgesamt
herausbekommen, lautet X, Doppelpunkt, Fx, Doppelpunkt, F von F von X,
Doppelpunkt und so weiter.
Also F wird beliebig oft angewandt.
Diese Iterate-Funktion ist das Grundmuster der Schleifen in
imperativen Programmiersprachen.
Die machen nämlich genau das.
Die Schleife kann nullmal ausgeführt werden.
Wenn da ein Argument reingegangen ist, dann bleibt dieses Argument
unverändert, weil Sie den Schleifenrumpf nicht ausgeführt haben.
Sie kann einmal ausgeführt werden, dann wird der Schleifenrumpf
angewandt.
Der Schleifenrumpf ist die Funktion F.
Und Sie bekommen als Ergebnis Fx.
Es kann zweimal angewandt werden, dann bekommen Sie Ffx.
Und so geht das weiter.
Und diese Elemente bekommen Sie hier alle in eine Liste aufgeführt
durch das Iterate.
Und jetzt können Sie sich also irgendein Element daraus holen.
Wenn ich also anfange mit der Zahl 5 und darauf meine Funktion plus 2
anwende, iterativ, dann liefert mir das eine Endlosliste, 5, 7, 9 und
so weiter.
Beliebe ich.
Und wenn ich da jetzt sage, und was ist denn nach 100 mal passiert,
dann kommt da heraus und sagt, ja nach 100 mal habe ich 100 mal 2
addiert.
Also bekommst du raus, 100 mal 2 plus 5 macht 205.
Und damit bricht die ganze Geschichte auch ab.
Aber selbe Geschichte wie bei dem Enum und wie bei dem Repeat.
Das Iterate läuft endlos, es sei denn Sie haben an irgendeiner Stelle
eine Abbruchbedingung, mit der Sie signalisieren und weitere
Ergebnisse brauche ich nicht.
Dann hört es auf.
Ja, damit kehre ich zurück zu einem Beispiel, was wir vorher schon
hatten und führe jetzt vor, wie man Primzahlen tatsächlich in Praxis
berechnet.
Wir haben also bisher gesagt, das können wir definieren, indem wir
zunächst unsere Teilerfunktion definieren, die uns eine Liste liefert
der sämtlichen Teiler.
Und dann wissen wir, dass eine Zahl n' ist, wenn die Teilerliste aus 1
und n besteht.
Und das gilt für positive ganze Zahlen.
Ja, damit sind wir dann auch in der Lage, jetzt zu fragen, was ist die
n -te Primzahl?
Wenn ich da also das n vorgebe, dann ist die einfachste Methode nach
dem, was wir bisher kennengelernt haben, fang doch einfach mal an und
zähle die sämtlichen potenziellen Zahlen auf, die als Kandidaten für
die Primzahl in Betracht kommen.
Nun 1 ist keine, also kann ich die Liste gleich mal bei 2 anfangen
lassen.
Da ich nicht weiß, wie groß die n-te Primzahl ist, schreibe ich hier
als Generator hin, das ist eine Liste, die bei 2 anfängt und dann
endlos läuft.
Sie hört nicht auf.
Damit generiere ich die Einzelelemente P für meine Liste und die
Forderung, die ich jetzt habe, ist, dass dieses P, was ich darauf
reingebe, Prim sein muss mit dieser Definition.
Die Qualifikation Prim P bricht den Generator noch nicht ab, sondern
sie selektiert nur und sagt, wenn du mir einen Kandidaten lieferst,
wie zum Beispiel 15, dann prüfe ich nach, ob 15 Primzahl ist und siehe
da, es ist es nicht, also wird es nicht in meine Liste aufgenommen.
Wohingegen 17 aufgenommen wurde.
Aber das mache ich endlos.
Bis Sie auf den Knopf drücken.
Wenn ich aber jetzt diese ganze Liste indiziere und sage, aus dieser
Liste will ich das n-te Element haben,
dann wird mir, wie ich vorhin sagte, mit Stöhnen und Heulen
nacheinander jedes Listenelement geliefert.
Und nachdem er das n-te Listenelement gesehen hat, sagt er, ja, jetzt
habe ich das, was ich wollte, mehr wollte ich nicht.
Und dann hört die ganze Geschichte auf.
Und infolgedessen können wir jetzt n-te Primzahl aufrufen mit
irgendeiner auch großen Zahl wie 302 und bekommen dann heraus, dass
das die Jahreszahl 1997 ist.
Die sich also als Primzahl entpuppt.
Nur, wenn Sie das jetzt praktisch machen, dann dauert es endlos.
Ich empfehle also, dieses Programm zu nehmen, auf Ihrem Rechner zu
starten und dann auf die Uhr zu schauen, wie lange das ganze Ding
dauert.
Warum ist das so langsam, ist die Frage daher.
Nun, das Dumme ist, dass dieses Programm sämtliche ganzen Zahlen
durchprüft, ob sie Primzahlen sind.
Und erst wenn es zu dem Schluss gekommen ist, es ist keine Primzahl,
dann schmeißt es die Zahl weg.
Und die Feststellung, es ist keine Primzahl, wird hier getroffen,
indem ich sämtliche Teile berechne.
Das ist natürlich eine ziemlich aufwendige Geschichte.
Stellen Sie sich also vor, Sie sollen eine Primzahl dadurch bestimmen,
dass Sie für sämtliche Zahlen, die kleiner gleich dieser Zahl sind,
sämtliche Teile ausrechnen.
Ziemlich unsinnig.
Das Nächste, was einem weiterhelfen könnte, wäre zum Beispiel
festzustellen, wenn wir schon wissen, dass 2 eine Primzahl ist, dann
reicht es uns für alle geraten Zahlen aus, zu wissen, die haben 2 als
Teile, also können wir sie wegwerfen.
Und welche anderen Teile diese Zahlen haben, interessiert uns für
diesen Zweck gar nicht.
Es sind keine Primzahlen, weil wir einen Teil gesehen haben.
Also alle Teile zu bestimmen, ist offensichtlich zu viel.
Und jetzt ist die Frage, können wir aus dieser Idee, wir schmeißen
eine Zahl weg, in dem Augenblick, wo wir einen Teil von ihr kennen.
Können wir daraus ein Prinzip machen, was uns zur Berechnung der
Primzahlen führt.
Nun die Frage wurde schon sehr früh geklärt und führt zu einem
Verfahren, was in der Literatur als Sieb des Eratosthenes bekannt ist.
Das Verfahren ist über 2000 Jahre alt.
Und die Grundidee lautet, wir beginnen, wie in unserem vorherigen
Programm, mit der Liste ab 2 und stellen fest, die erste Zahl dieser
Liste ist auf jeden Fall eine Primzahl.
Das ist unsere Anfangsfeststellung.
Also Vorkenntnis, wir wissen, dass 2 eine Primzahl ist.
Mit der Kenntnis gehen wir rein.
Wenn wir das gewusst haben, dann streichen wir aus der Liste, die wir
hier haben, sämtliche Vielfachen der uns bereits als Primzahl
bekannten Zahlen raus.
Das machen wir zuerst mit 2.
Also alle Vielfachen von 2 werden rausgestrichen.
Wenn wir jetzt in eine Situation kommen, dass diese Liste z.B.
sämtliche Vielfachen von Primzahlen, die kleiner als K sind,
gestrichen bekam, aber K übrig bleibt.
Dann ist der nächste Schluss, dann muss K ebenfalls eine Primzahl
sein.
Begründung, sämtliche Teile, die K hat, müssten kleiner als K sein.
Für alle Primzahlen, die kleiner als K sind, haben wir die Vielfachen
rausgestrichen.
K haben wir nicht rausgestrichen, also kann K kein Vielfaches
irgendeiner kleineren Primzahl sein.
Also keine Primzahl, die kleiner ist als K teilt K, also ist K prim.
Wir wissen sogar noch mehr.
Wenn K prim ist, dann kann ich sogar feststellen, dass sämtliche X,
die kleiner als K² sind, ebenfalls Primzahlen sind.
Denn alle echten Teile von einem solchen X, also mit R mal S gleich X,
die müssten beide kleiner gleich K sein.
Wenn aber das X nicht rausgestrichen worden ist, gibt es keine solchen
Teile.
Also ist X ebenfalls Primzahl.
Ein Beispiel vorgeführt.
Ich fange also an mit dieser Liste von 2 bis irgendwo hin und streiche
zunächst einmal heraus die sämtlichen Vielfachen von 2.
Wenn ich das getan habe, dann weiß ich nach dieser Feststellung, dann
sind sämtliche Zahlen, die übrig geblieben sind und die zwischen 2 und
4 liegen, 4 ausgeschlossen, ebenfalls Prim.
Also wissen wir, dass 3 eine Primzahl ist.
Jetzt streichen wir sämtliche Vielfachen von 3.
2 mal 3 brauchen wir gar nicht mehr streichen, das haben wir vorhin
schon raus.
Es fängt also mit 3 mal 3 an zu streichen.
Wir fangen immer bei der Quadratzahl an.
Das ist das erste Vielfache, was zu streichen ist.
Dann bleiben nur noch die Zahlen übrig, die ich hier hingeschrieben
habe.
Das ist also dieselbe Liste wie oben, nur habe ich jetzt alles
rausgestrichen, was da rauszustreichen ist.
Die Vielfachen von 3, die drinnen stehen, habe ich rot angestrichen.
Also 9, 15, 21, 27 stehen da noch drinnen.
Und jetzt weiß ich, alles was übrig bleibt und was zwischen 3 und 3²
liegt, ist ebenfalls Primzahl.
Also weiß ich jetzt, dass 2, 3, 5 und 7, das sind nämlich die Zahlen,
die übrig geblieben sind, kleiner als k², kleiner als 9, dass das auch
Primzahlen sind.
Und streiche auch deren Vielfache raus, dann bleibt also das übrig,
was jetzt in dieser Zeile steht.
Und ja, dann wissen wir aber auch, dass alles, was jetzt noch stehen
geblieben ist, kleiner als 25, dass das ebenfalls Primzahlen sind.
Das heißt, wir haben mit einem Schlag herausgekriegt, dass 11, 13, 17,
19, 23 Primzahlen sind.
Und wenn Sie das weitermachen, dann statt 5 jetzt zu 7 übergehen und
alles wegstreichen, beginnend mit 49, mit 7².
Dann ist alles, was da noch übrig geblieben ist, kleiner als 49 Prim
und das ist die Liste der Zahlen, die ich hier unten angegeben habe.
Und dann sind Sie schon in der Lage festzustellen, jetzt kenne ich
sämtliche Primzahlen kleiner als 47².
Wer weiß zufällig auswendig, was 47² ist?
Also ich weiß es nicht auswendig, es ist über 2000.
Das heißt also, alleine mit den 5 Schritten, die ich hier auf der
Folie aufgeführt habe, können wir bereits sämtliche Primzahlen
bestimmen, bis zur Größenordnung 2000.
Und das ist offensichtlich ein wesentlich effizienteres Verfahren, als
das, was wir bisher gehabt haben.
Fragt sich, wie wir das programmieren können.
Und das führe ich Ihnen hier vor.
Das ganze Ding heißt Sieb des Eratosthenes, weil wir also, wenn wir
eine Primzahl ermittelt haben, die Zahlliste schütteln und da fallen
sämtliche Vielfachen unserer Primzahlen durch.
Im Korb bleiben immer nur Primzahlen zurück.
Oder Zahlen, die größer sind, die wir noch nicht untersucht haben.
Infolgedessen ist Eratosthenes eine Funktion, die uns eine
Integerliste liefert.
Die Liste aller Primzahlen.
Und definiert wird das dadurch, dass wir auf die Liste der ganzen
Zahlen ab 2, haben wir ja gerade gesehen, eine Funktion Sieb anwenden.
Und Sieb hat die Aufgabe, alle Vielfachen auszusieben der Zahl, die
wir vorne dran geschrieben haben.
Also das erste Argument ist die Zahl, die wir aussieben wollen.
Und das wird rausgestrichen.
Also ist Sieb eine Funktion, die nimmt eine Integer und eine
Integerliste und liefert uns zurück diese Integerliste.
Aber bitte schön, ohne die Vielfachen dieser Integer, die wir als
erstes Argument angegeben haben.
Ja, von dem ersten Argument wissen wir, dass es Prim ist.
Und infolgedessen können wir Sieb, K, X, S jetzt definieren.
Nimm erstmal sämtliche Primzahlen heraus, die in der ganzen Geschichte
drin sind.
Und dann füge ich dazu das Sieb, aber diesmal angewandt auf K plus 1,
mit der Restliste X, S, wobei wir alle nicht Prim in Zahlen
rausgestrichen haben.
Das macht das Diff, wie wir gleich noch sehen werden.
Schauen wir uns an, was da für Funktionen vorkommen.
Hier drinnen, da ist Prim zunächst mal die Funktion.
Nimm sämtliche Elemente aus X, S heraus, die kleiner als K² sind.
Take while, hier definiert, ist eine Standardfunktion aus dem Prelude.
Macht dasselbe, was wir bei dem Take kennengelernt haben.
Nur fängt es an und nimmt die Elemente vom Anfang an, so lange, wie
eine bestimmte Bedingung erfüllt ist.
Und sobald die Bedingung nicht mehr erfüllt ist, hört es auf.
Wir geben also nicht an, nimm die ersten 5 oder die ersten 7, sondern
wir geben an, nimm die Anfangselemente bis, solange eine bestimmte
Bedingung erfüllt ist.
Und die Bedingung ist also hier, die Elemente müssen kleiner als K²
sein, von denen haben wir gerade vorhin argumentiert, das sind
Primzahlen.
Ja, und dann möchte ich also hier noch die nicht Primzahlen haben.
Und nicht Primzahlen nach meinem bisherigen Kenntnisstand, sind dann
Vielfache der Zahlen, die ich als Prim erkannt habe.
Also definiere ich mir zunächst einmal eine Liste der Vielfachen.
Das ist gegeben dadurch, dass ich die Liste der Primzahlen nehme und
darauf eine Funktion Vielfache bilden anwende.
Die habe ich hier definiert.
Und wenn ich diese Vielfachen habe, dann kann ich jetzt die nicht
Primzahlen feststellen, eigentlich als alle diese Vielfachen.
Nur die Vielfachen, die erscheinen in irgendeiner ungeordneten
Reihenfolge.
Und da müsste ich also sagen, ich streiche erstmal alle Vielfachen von
2 raus, bis ganz ans Ende, das Ende gibt es aber nicht.
Und dann streiche ich alle Vielfachen von 3 heraus, wieder bis ans
Ende, gibt es aber nicht.
Und das ist also unangenehm, dass da zwischendrin immer eine Art
Infinitum gelaufen wird.
Und in Folge dessen mache ich etwas ganz anderes, ich sortiere diese
Liste erstmal.
Und dieses Sortieren, das mache ich hier mit einem jetzt dritten
Sortierverfahren, nämlich dem sogenannten Mischsortieren.
Grundfunktion ist Merge, gegeben sind 2 Integerlisten, von denen
erwarte ich, dass sie ihrerseits bereits sortiert sind.
Und jetzt produziere ich eine gemeinsame Integerliste, die diese
beiden Listen verzahnt liefert in sortierter Reihenfolge.
Was mache ich dazu?
Nun, wenn eine der beiden Listen leer ist, dann liefere ich die
andere, die ist ja schon sortiert.
Wenn aber beide Listen nicht leer sind, also jeweils ein erstes
Element x bzw.
y besitzen, dann frage ich nach, welches Element sollst du denn jetzt
als erstes nehmen, wenn x kleiner als gleich y ist, nehme ich als
erstes das x und mische die Restliste xs mit der anderen Liste.
Wenn das erste Element y ist, weil y kleiner als x ist, das ist der
Außerweisfall, nehme ich das y raus und mische die x-Liste mit dem
Rest der y-Liste.
Vollständige Induktion.
Wenn ich annehmen darf, dass die Listen xs bzw.
die Listen x.xs und y.ys bereits sortiert sind, dann habe ich
offensichtlich in diesem Fall x als das kleinste Element beider
Listen, im anderen Fall habe ich y als kleinstes Element beider
Listen.
Ja, und wenn ich jetzt dieselbe Operation anwende auf die Restlisten,
dann heißt das bei vollständiger Induktion, hier hast du insgesamt n
plus m Elemente gehabt, jetzt hast du das Merge auf n plus m minus 1
Elemente angewandt, also 1 weniger.
Und das führt dich zum Schluss in die Situation, wo die ersten beiden
Definitionen von Merge zuschlagen, die also nur einfach die Liste
herausnehmen.
Mischsortieren ist eines der verbreitetsten Verfahren zum Sortieren
und wird insbesondere angewandt, wenn Sie Datenbestände haben, die so
umfangreich sind, dass Sie sie nicht mehr in den Hauptspeicher Ihres
Rechners kriegen.
Dann sind diese beiden Listen, von denen ich hier rede, Dateien auf
dem Hintergrundspeicher und das Mischsortieren macht das alles ganz
einfach.
Ich nehme jeweils die ersten Elemente beider Dateien, vergleiche die,
dann weiß ich, was das erste Element meiner Ergebnisdatei ist und dann
mache ich weiter.
Das heißt, ich lese beide Dateien vom Anfang weg, ein Element nach dem
anderen und erstelle dabei jedes Mal durch Auswahl ein neues Element
des Ergebnisses.
Voraussetzung dafür ist, dass die beiden Einzeldateien bereits
sortiert sind, aber die kann ich jetzt, das eine n, das andere m
Elemente und insgesamt haben wir n plus m und wenn wir das richtig
machen, dann können wir unterstellen, dass die beiden Einzeldateien n
halbe Elemente haben, wenn n die Gesamtzahl ist, die wir im Ergebnis
brauchen.
Und darauf kann man dasselbe Verfahren rekursiv anwenden und das ist
also, wie gesagt, das häufigste Verfahren.
Wir werden das noch ausführlich zu besprechen haben, wie das
funktioniert.
Und dann kriegen Sie auch ein schönes Bild dazu, wie solche Dinge
funktionieren.
Also Merge ist nichts anderes als das Zusammenmischen von zwei Listen
und das wird hier angewandt auf die leere Liste und die Liste aller
Vielfachen und das mit Linksfaltung.
Und jetzt müssen wir uns bloß noch anschauen, was Vielfache sind.
Vielfache von x ist die Liste aller x mal j, wobei j beliebig ist.
1, 2, 3.
Also auch wieder eine unendliche Liste, die sämtliche Vielfache
generiert.
Und damit habe ich also definiert, was diese drei Funktionen sind.
Jetzt fehlt mir noch die Funktion diff.
Die Funktion diff tut nichts anderes, als zwei Listen vergleichen, um
festzustellen, welches Element sie rausschmeißen kann.
Welche Elemente sie rausschmeißen kann.
Wenn die ersten beiden Elemente gleich sind, dann schmeiße ich die
raus und wende diff auf den Rest der ganzen Geschichte an.
Wenn x größer als y ist, dann schmeiße ich offensichtlich das y
heraus.
Also schmeiße ich insgesamt jeweils in einem Schritt das kleinste
Element heraus.
Und der Sinn der Sache ist an dieser Stelle, diese Diff-Funktion
anzuwenden auf xs und die Liste der nichtprämen Zahlen, sprich auf die
Weise schmeißen wir die nichtprämen Zahlen in der ganzen Geschichte
heraus.
Und die Erklärungen, die ich jetzt abgegeben habe, die stehen alle auf
dieser Folie.
Das brauche ich Ihnen also jetzt nicht mehr vorlesen, weil ich es
schon gesagt habe.
Und wenn Sie mit diesem Sieb des Eratosthenes jetzt die 301.
Primzahl berechnen, dann bekommen Sie auch wieder die 1997 heraus.
Aber vergleichen Sie also die Rechenzeit, falls Sie das zu Hause
durchrechnen, mit der Rechenzeit, die Sie vorhin gebraucht haben.
Und dann werden Sie sehen, dass Sie hier Ihre Kaste kaum losgelassen
haben, da hat er sein Ergebnis schon.
Während Sie im anderen Fall mehrmals scannen mussten, bevor das
Ergebnis da war.
Weil, wo waren wir denn?
Ja, weil wir an dieser Stelle, wie Sie hier sehen, angefangen haben
mit, wie war denn das?
Da haben wir auch mit zwei angefangen, das ist jetzt verwunderlich.
Eigentlich haben wir da mit eins angefangen.
Ich vermute also mal, dass das ein Fehler ist.
Ja, das tut sie hier auch.
Das tut sie hier auch.
Also ich vermute mal, dass da noch ein Fehler drin ist, das aus einem
früheren Probelauf, dieses Beispiel hier lief, mit einer Eins an
dieser Stelle, statt einer Zwei.
Liefert dasselbe Ergebnis, bloß dann ist der Index ein anderer.
Tut mir leid, werden wir nochmal nachrechnen.
Nochmal, hier oder wo?
An der Stelle?
Da war die Definition,
wiedergegeben aus dem Prelude.
Also wie gesagt, ich vermute, dass wir da einen Rechenfehler gemacht
haben, indem wir im Nachhinein das Programm korrigierten, aber nicht
den Aufruf.
Soviel also als Illustration an einem praktisch interessanten Thema,
wie man mit unendlichen Listen arbeitet.
Und ich wiederhole das in der Theorie, grundlegend zu lernen, die ist
hier, man kann in einer Programmiersprache mit fauler Auswertung, wie
Haskell, mit unendlichen Datenstrukturen arbeiten, hier mit
unendlichen Listen.
Und dann wird automatisch dafür gesorgt, dass von diesen unendlichen
Datenstrukturen immer nur der Teil berechnet wird, den man absolut
braucht für das Endergebnis.
Und alle weiteren Teile werden nicht berechnet.
Wir werden im Februar noch weitere Beispiele dieser Bauart sehen, bei
denen wir das Ganze dann nicht mehr auf eine einzelne Liste anwenden,
aber immer noch dasselbe Prinzip haben.
Programm funktioniert im Wesentlichen deshalb, weil es die eigentlich
unendliche Datenstruktur nicht komplett ausrechnet.
Andere Anwendungen, bei denen wir indirekt auch wieder von unendlichen
Listen Gebrauch machen, diesmal aber ganz gezielt sagen, wir wollen
gar nicht alles sehen, sondern immer nur das nächste Element, ist die
Frage nach Zufallszahl.
Zufall ist bekanntlich etwas nicht vorher planbares.
Und wenn Sie also mit einem Würfel in die Hand nehmen und mit dem
Würfel würfeln, dann können einige Taschenspieler das so machen, dass
das Ergebnis planbar wird.
Der normale Mensch kann das nicht.
Und deswegen liefert uns der Würfel Zufallszahlen zwischen 1 und 6.
Wir brauchen in der praktischen Anwendung sehr häufig nicht nur Zahlen
zwischen 1 und 6, sondern sehr viel mehr.
Zum Beispiel ist eine in der Physik weit verbreitete Methode, um
Integrale zu berechnen, wie folgt.
Wir berechnen unsere Funktion an zufälligen Stellen innerhalb des
Integrationsbereichs, zählen alle diese Werte zusammen, ummitteln
durch die Anzahl der Stellen und multiplizieren das Ganze mit der
Länge des Integrationsintervalls.
Wenn wir wirklich zufällig die Stellen ermitteln, an denen wir die
Funktion berechnen, ist das ein Verfahren, was in der Tat gegen das
Integral konvergiert, wie man sich leicht überlegen kann nach
Definition des Riemannschen Integrals.
Und wenn Sie jetzt mehrdimensionale, sehr unangenehm geformte
Integrationsbereiche haben, also Sie sollen integrieren über den
gesamten Raum dieses Hörsaals, wo Luft zu finden ist.
Das heißt, Sie müssen genau abgrenzen, Bänke sind keine Luft, Ihre
Köpfe sind keine Luft, der Rechner hier vorne ist keine Luft und so
weiter.
Und dafür dann versuchen, mit mathematischen Methoden nachzurechnen,
wie berechne ich dieses Integral, bei dieser kompliziert geformten
Umrandung des Raums, in den ich integriere.
Dann funktioniert das nicht richtig.
Wenn ich aber jetzt einen Zufallszahlengenerator hätte, der
gleichverteilt Zufallszahlen generiert, die ich benutzen kann als
Koordinaten x, y, z in diesem Raum.
Sobald ich mit irgendeiner solchen Koordinate in meinen Kopf
reinkomme, sage ich wegwerfen, das war keine Luft.
Bei Ihnen mache ich es genauso.
Und sobald ich tatsächlich in der Luft bin, sage ich prima, an der
Stelle haben wir jetzt den Integralwert zu berechnen, den
Funktionswert zu berechnen.
Dann ist das ein relativ einfaches Verfahren.
Das als Elementaridee, wo man Zufallszahlen gebrauchen kann.
Wir werden sehen, dass wir auch in der Informatik in vielen
Algorithmen auf solche Zufallszahlen angewiesen sind.
Problem ist nur, der Rechner ist, wie wir wissen, ein Vollidiot mit
Spezialbegabung.
Und zu seiner Spezialbegabung gehört, dass er alles ganz präzise
ausrechnet.
Würfeln kann er nicht.
Dazu ist er zu dumm.
Da haben also viele Leute alle möglichen Versuche unternommen, wie man
das verbessern könnte.
Sind aber nicht zu einer vernünftigen Lösung gekommen, sondern haben
gesagt, wir helfen dem Zufall etwas nach.
Wir fabrizieren Zahlen, die zwar einer gewissen Gesetzmäßigkeit
genügen, aber die Gesetzmäßigkeit wählen wir so, dass es keiner merkt.
Sowas nennt man Pseudo-Zufallszahlen.
Und das sind also Listen von Zahlen, die nach irgendwelchen
statistischen Tests als zufällig erscheinen.
Zum Beispiel als gleich verteilt.
Obwohl sie in Wahrheit nach einem strengen Rechengesetz aufgebaut
sind.
Es gibt viele solche Funktionen, die solche Pseudo-Zufallszahlen
berechnen.
Zum Beispiel die einfachste wäre, ich berechne nacheinander Zahlen,
x1, x2 und so weiter.
Indem ich jeweils die vorangehende Zahl mit irgendeinem festen Faktor
A multipliziere und das Ergebnis Modulo einer sehr großen Primzahl
nehme.
Also beispielsweise, wenn ich den Würfel nachahmen wollte, dann könnte
ich das machen, indem ich sage, ich nehme 1.
Und addiere dazu das Divisionsergebnis von x mal 6, dividiert durch m,
nach unten gerundet.
m kann ich noch frei wählen.
Dafür gibt es eigentlich Normen, die weit verbreitet sind.
Also eines der Verfahren sagt beispielsweise, wir nehmen die Primzahl
2.147.483.647 und wählen A gleich 16.807.
Und dann rechnen wir diese Formel aus.
Das ist ein Standardverfahren mit exakt diesen Zahlen, was sich in der
Praxis bewährt hat.
Und das ist eine der Standardmethoden, die Sie einsetzen,
beispielsweise auf einem 32-Bit-Rechner.
Wenn Sie einen 64-Bit-Rechner haben, dürfen Sie das Verfahren nicht
einsetzen.
Dann ist m zu klein.
Dann sollten Sie m gleich in der Größenordnung 2 hoch 63 gewählt haben
und nicht in der Größenordnung 2 hoch 31.
Wir kennen zahllose Beispiele, dass bei der Generierung von
Zufallszahlen Betriebssysteme und Übersetzer und alle möglichen
Bibliotheken großen Ärger verursachen.
Sie finden nämlich solche Zufallszahlengeneratoren oft standardmäßig
eingebaut.
Und das Ergebnis soll ja wirklich willkürlich sein.
Wenn aber das Ergebnis beispielsweise nach 15 Zufallszahlen plötzlich
eine Periode bekommt, dann kann ich das keineswegs als zufällig
bezeichnen.
Wenn es nach 95 Elementen eine Periode bekommt, ist es auch nicht
zufällig.
Die Zahlwerte, die ich hier angebe, sind so geartet, dass Sie in der
Tat sämtliche 2 hoch 31 minus 1 ganzen Zahlen als Ergebnis bekommen,
ohne eine Periode vorzufinden.
Und die Bemerkung, dass man also nach 15 natürlich nicht aufhören
darf, stimmt zwar, aber so lächerlich es klingt, ich habe
Sprachimplementierungen gesehen, bei denen nach 15 die Periode kam.
Fehler der Implementierung einer Programmiersprache und deren
Bibliotheken.
Ich erzähle das im Wesentlichen, um Sie misstrauisch zu machen.
Wenn Sie Zufallszahlengeneratoren haben, dann ist es gar nicht so
verfehlt zu sagen, ich mache mal erst einen Test, ob das Zeug wirklich
gleich verteilt ist, wie es behauptet, oder ob es nicht womöglich
Perioden hat.
Es sei denn, Sie sind Spezialist und wissen so viel über
Zufallszahlen, dass Sie nachvollziehen können, warum bei diesem
Rechenverfahren nichts rauskommt.
Das Problem selbstverständlich, wenn Sie xn plus 1 gleich a mal xn
modulo m berechnen wollen, mit diesem m und diesem a, ist, dass die
Zahlen, die Sie als Produkt bekommen, größer werden als 32 Stellen.
Die Frage, die also hinzukommt, ist, wenn ich Wert darauf lege, dass
ich alle 2 hoch 31 minus 1 ganzen Zahlen erwische mit meiner
Zufallszahl, dann muss ich offensichtlich Arithmetik anwenden, die ich
eigentlich nur mit 64 bit machen kann.
Im Buch steht ein Verfahren, wie man dieses spezielle Produkt trotzdem
mit 32 bit berechnen kann.
Wie beimplementieren wir sowas in Haskell?
Nun, ich implementiere zu diesem Zweck zunächst eine Funktion, nächste
Zufallszahl, die nimmt eine Zufallszahl und liefert mir die nächste.
Und nach dem, was wir gesehen haben, ist also das, was zu tun ist,
dass wir den Rest nehmen des Multiplikationsergebnisses von 16.000
multipliziert mit x und der Nenner ist 2 hoch 31 minus 1.
Und die Zufallszahlengenerierung ist jetzt eine, die uns zunächst
einmal eine Liste solcher Zufallszahlen liefert, wozu wir
zusammenschließen, ausgehend von irgendeiner Zahl x, das nächste von
x, das ist also dieser Generator, und dann wenden wir Zufall an, auf
das nächste von x.
Wiederum eine unendliche Liste.
Und wenn wir jetzt würfeln wollen, also Zahlen rausbekommen wollen
zwischen 1 und 6, dann heißt das, du definierst hier zunächst einmal
eine entsprechende Funktion, die das Ganze zurückführt auf die Zahlen
zwischen 1 und 6.
Das wendest du auf eine Zufallsliste an und die Zufallsliste
generierst du mit dieser Funktion Zufall.
Und wenn wir also von dem Würfel jetzt, das ist eine unendliche Liste,
die ersten 20 Elemente nehmen, dann bekommen Sie beispielsweise diese
Würfel heraus.
Beachten Sie, das Experiment können Sie wiederholen.
Und insofern ist es schon mal nicht zufällig.
Sie bekommen immer dieselben Zahlen.
Nichts von Zufall.
Das schadet in diesem Fall aber wahrscheinlich wenig.
Es ist sogar erwünscht in vielen Fällen, dass wir sagen können, wir
haben ein zufälliges Experiment gemacht und dieses zufällige
Experiment kannst du 1 zu 1 wiederholen.
In anderen Fällen stört mich das dann doch sehr.
Da möchte ich wirklich Zufall haben.
Und wenn der zweite Fall vorliegt, dann ist ein probates Mittel, um
tatsächlich Zufall zu erreichen, der, dass Sie den Rechner auf die Uhr
schauen lassen.
Und sagen, wir nehmen entweder die Uhrzeit, alle Bits hintereinander
zusammen als eine Integerzahl oder wir nehmen daraus die Sekundenzahl
oder die Uhrzeit in Millisekunden oder Mikrosekunden gerechnet.
Und das ist der Anfangswert unserer Zufallsgenerierung.
Dann ist sichergestellt, wenn Sie zwei Experimente machen, fangen die
zu einer unterschiedlichen Uhrzeit an und damit liefern Sie auch
unterschiedliche Ergebnisse.
Also zwei verschiedene Arten der Verwendung.
Entweder wiederholbar oder nicht wiederholbar.
Je nach Bedarf.
Und das Ganze ist, wie Sie sehen, ebenfalls wieder eine Anwendung
endlicher Listen.
Damit sind wir im Grunde jetzt mit den Grundelementen einfacherer
Bauart funktionaler Sprachen durch.
Und wir können also zusammenfassen, wir haben gesehen, wie man
Funktionsdefinitionen hinschreibt, wie man Ausdrücke hinschreibt.
Wir haben gesehen, dass Ausdrücke Funktionsaufrufe sind oder
Fallunterscheidungen.
Und dass sich alle anderen Fälle darauf zurückführen lassen.
Wir haben kennengelernt, wie Funktionale aussehen.
Das sind nämlich Funktionen, die andere Funktionen als Argument haben,
beziehungsweise als Resultat.
Wir haben am Beispiel der Fold-Operation, der Map-Operation, der
Filter -Operation Beispiele gesehen, wie wir kompliziertere
Konstruktionen mit Hilfe von Funktionalen einheitlich zusammenfassen
können.
Und insbesondere solche Sätze, wie wir sie als Dualitätssätze
kennengelernt haben bei den Fold-Operationen, vereinfachen erheblich
die Einsicht in die Korrektheit irgendwelcher Programme.
Wir haben dann gesehen, wie Listenbeschreibungen funktionieren.
Und dass wir spezifisch in Sprachen mit fauler Auswertung, also zum
Beispiel in Haskell, aber nicht in ML, sogar unendliche Listen
definieren können und sinnvoll gebrauchen können, weil immer nur die
Listen -Elemente vom Anfang weg berechnet werden, die tatsächlich
benötigt werden.
Wir haben noch nicht gesehen, was hier auf der letzten Seile steht,
dass auch andere Typen unendlich sein können.
Das haben wir erst im Kapitel 6 bekommen, Beispiele hierfür.
Das ist die Zusammenfassung zunächst über die Grundelemente.
Ich erinnere nochmal dran, Programmieren lernt man nicht durch
Zuhören, sondern durch Üben.
Das heißt also, ich habe Ihnen bisher eine relativ trockene Vorlesung
gehalten zu der ganzen Geschichte und ich kann nicht anders, weil jede
Vorlesung dazu trocken ist, denn sie kann nur Gesetze verkünden und
einige Beispiele durchrechnen, aber die praktische Handhabung und das
Auswendiglernen der ganzen Mechanismen, das muss ich Ihnen überlassen
als Einzelne zu Hause.
Soviel zu dem Kapitel und damit kommen wir nun zu einem Kapitel, was
am Ende die Brücke schlägt zum objektorientierten Programmieren, was
uns aber hier jetzt einige Einblicke verschafft, zunächst in die
Mechanismen, wie funktionale Sprachen implementiert sind und dann
auch, wie Typen insgesamt klassifiziert werden können.
Überschrift ist also Typisierung in Programmen und ich habe bereits
eingangs erläutert gehabt, eigentlich brauche ich Typen nicht.
Sondern ich könnte rechnen in einer Sprache wie Haskell, in dem ich
sage, alle Werte sind Terme, alle Ausdrücke sind Terme und damit gibt
es einen einheitlichen Datentyp, der heißt Term.
Ja, und wenn es keine zwei verschiedenen Datentypen gibt, dann übrigt
es sich über Typen zu reden.
Das gibt es dann einfach nicht.
Dann haben wir festgestellt, es ist aber sinnvoll, diese große
Wertemenge zu positionieren, um auf diese Art und Weise
sicherzustellen, dass immer auch die richtigen Operanten zur Verfügung
stehen für irgendeine Operation.
Wobei nebenbei dann für bestimmte Operationen wie Plus und Minus auch
noch festgestellt wird, was ist denn durch den Operator eigentlich
gemeint.
Und insgesamt dient das also zu zwei Zwecken.
Der erste Zweck steht nicht auf der Folie, der heißt, wir wollen
Studenten ärgern, damit die also über möglichst viele Typfehler
stolpern und damit was zu kauen haben.
Der zweite Zweck ist, auf die Art und Weise wollen wir sie dazu
erziehen, dass sie Laufzeitfehler möglichst bereits zur
Übersetzungszeit erkennen und nicht erst durch umfänglichen Tests zur
Laufzeit feststellen.
Wobei umfänglicher Test in vielen Fällen heißt, sie sind gar nicht in
der Lage, so viele Tests durchzuführen, um alle Fehler zu finden, die
möglicherweise in ihrem Programm sind.
Also ist der erste Teil der Rede, wir wollen Studenten ärgern,
offensichtlich falsch.
Sondern wir wollen ihnen eigentlich mit Typisierung helfen und uns
allen helfen, Fehler möglichst frühzeitig zu erkennen.
Ja, und hier stehen die Dinge, die ich bereits gesagt hatte.
Im Rechner sind alle Daten zunächst Bitfolgen.
Das heißt, die Operationen haben eigentlich nur Bitfolgen als
Argumente.
Bit sind weder grün noch rot.
Ich kann also zwei verschiedene Bitfolgen bestenfalls nach ihrer Länge
unterscheiden.
Und die Operation entscheidet, wie die Bitfolgen interpretiert werden.
Und die Fehlerquelle, die wir jetzt vermeiden wollen, ist, wir wollen
sicherstellen, dass dann, wenn sie sagen, ich will eine bestimmte
Operation F anwenden, dann sollen sie garantiert bekommen, aber die
bekommen bloß grüne Bitfolgen als Argumente.
Und das kann die Hardware nicht unterscheiden, also machen wir es mit
der Programmiersprache auf eine andere Art und Weise.
Das haben wir zusammengefasst in dieser Folie, die wir Sie schon
kennen.
Wir haben also festgestellt, die Wertemenge ist partitioniert.
Wir kennen starke Typbindung, wir kennen schwache Typbindung und
Typfreiheit.
Und auch diese Folie kennen wir schon.
In funktionalen Sprachen haben wir starke Typbindung mit dem
zusätzlichen Erweiterung, dass wir Typen kennzeichnen können durch
Typvariable, die dann jeweils konsistent eingesetzt werden.
Oder dass wir Typen kennzeichnen können als Mitglied einer Typklasse.
Und der Unterschied zwischen Polymorphie und Zugehörigkeit zu einer
Typklasse ist der, dass bei einem Polymorphentyp eine Funktion
angegeben wird, die muss so, wie sie dasteht, funktionieren für
sämtliche Typen, die sie einsetzen können.
Da kann keine Operation ausgetauscht werden.
Wenn Sie einen Operator definieren für die sämtlichen Typen einer
Typklasse, dann sind Sie befugt, für jeden einzelnen Typ eine neue
Definition anzugeben.
Das heißt, da haben Sie unterschiedliche Definitionen, bei Polymorphie
haben Sie keine unterschiedlichen Definitionen, sondern nur eine
einzige.
Soviel zur Wiederholung.
Und ja, erstens stark typisiert.
Den Typ können Sie auch hinschreiben.
Die Notation, die Sie auch schon gesehen haben, führe ich jetzt
offiziell ein.
Wenn Sie einen Ausdruck haben, dann können Sie hinterher den Typ
angeben.
Das heißt, wenn Sie hinschreiben wollen, 1 plus 2, dann können Sie
dahinter schreiben, und ich meine in diesem Fall Integer, ich meine
nicht Int.
Sollten Sie dahinter geschrieben haben, Doppelpunkt, Doppelpunkt,
Pool, dann kriegen Sie einen Typfehler, weil er sagt, der Ausdruck ist
doch niemals vom Typ Pool.
Das kann nicht stimmen.
Waren Sie sich mit der Funktion Info vertraut, die in Haskell
definiert ist, dann sind Sie in der Lage, beliebige Ausdrücke
hinzuschreiben und zu verlangen, dass er Ihnen den Typ angibt.
Also das, was nach dem Doppelpunkt, Doppelpunkt folgt, das erspuckt
Ihnen das Haskell-System im Zweifelsfall auch aus, wenn Sie es nicht
vorgegeben haben.
Wie ergibt sich der Typ?
Nun, wenn Sie hier eine Operation haben, ich habe sie hier F genannt,
nicht Plus, die ein oder mehrere Typen als Parameter nimmt, hier
einen, T1, und angeblich ein Ergebnis vom Typ T2 liefert, und E hat
den Typ T1, dann hat F von E den Typ T2.
So wird der Typ festgestellt.
Also umgekehrt, wenn F von E den Typ T2 haben soll, dann muss E den
Typ T1 haben, nach dieser Definition.
Ich kann es also auch rückwärts rechnen.
Und wegen dieser Eigenschaft haben wir dann die Redewendung, der
Kontext von E, also die Stelle an der E auftritt, nämlich als Argument
von F, die erwartet von E, dass es den Typ T1 hat.
Wenn dieser Typ nicht vorliegt, dann liegt ein Typfehler vor.
Diese Art von Regeln, was erwartet der Kontext, die kann man als ein
Kalkül darstellen, den ich Ihnen hier nicht vorführe, den aber das
Haskell -System implementiert hat.
Und zwar unter der Überschrift Typ-Inferenz.
Das hat nicht nur das Haskell-System implementiert, sondern das haben
alle funktionalen Sprachen implementiert.
Die gehen her, lesen ihr Programm durch, vor Programmausführung, also
bevor irgendetwas startet, und bestimmen für jede Funktion und jeden
Ausdruck den Typ.
Der Typ ist entweder endgültig festgelegt,
oder Sie sagen, ja, ich kann mich noch nicht einigen, das ist eine
Typvariable.
Da könnten noch verschiedene Möglichkeiten vorkommen.
Und genauso, wenn wir da Operationen drin haben, die zu einer
Typklasse gehören, dann wissen wir unter Umständen, da können noch
verschiedene Typen vorkommen, aber die müssen alle zu dieser Typklasse
gehören.
Und wenn Sie also Ihr Programm in den Interpretierer laden und jetzt
eine Fehlermeldung bekommen, dann ist das genau eine Typfehlermeldung,
die Sie hier vor der Programmausführung bekommen.
Und die Gründe könnten sein,
das Haskell-System hat versucht, den Typ irgendwelcher Funktionen zu
ermitteln, hat das aber nicht zustande gebracht.
Dann beschwert es sich und sagt, Du hättest die Signatur angeben
sollen.
Dann hätte ich es nämlich gewusst.
Die zweite Möglichkeit ist, dass es an irgendwelchen Stellen findet,
dass von einem Ausdruck erwartet wird, dass er den Typ T hat, wenn ich
ihn im Kontext sehe und er hat leider gar nicht den Typ.
Also zwei Ursachen, entweder Funktion nicht vereinbart oder Typ eines
Ausdrucks nicht konsistent mit dem erwarteten Typ im Kontext.
Das sind die möglichen Ursachen und Typ-Inferenz ermittelt das.
Auf die Einzelheiten gehe ich, wie gesagt, hier nicht ein, auf welche
Art und Weise das ermittelt wird, aber ich kann vielleicht einige
Beispiele elementarer Bauart angeben.
Wenn Sie eine Funktion f definieren, mit Parameter I und im
Funktionsschrumpf kommt unter anderem vor I plus 1.
Was wissen wir dann über den Typ von I?
Also wir schauen einfach ganz elementar nach und stellen fest, I muss
einen Typ haben, der erlaubt, Plus anzuwenden und I kann dabei die
erste Operand sein.
Also schauen wir, wenn wir keine weiteren Definitionen von Plus haben,
in unserem Prelude nach, wo ist denn Plus definiert für welche Typen
und dann haben wir schon eine Liste von Typen, die für I in Betracht
kommen.
Das ist eine Einschränkung.
Dann schauen wir uns als nächstes an und stellen fest, aha, und der
zweite Operand zu dem Plus ist eine 1.
1 ist vom Typ Int oder vom Typ Integer.
Also die Addition, nach der wir suchen, muss als erstes Argument den
Typ von I haben und als zweites Argument entweder Int oder Integer.
Weitere Einschränkung.
Dann schauen Sie genau nach und stellen fest, da bleibt mir nur noch
die Addition übrig für Integers oder für Ints und in Vorhinein habe
ich bereits aus dieser Programmstelle geschlossen, dass das I vom Typ
Int oder Integer sein sollte.
Kriege ich jetzt an einer anderen Stelle eine Funktionsdefinition, g
von x ist gleich und da drinnen steht plötzlich f von x dividiert
durch 2 mit dieser Funktion f.
Was weiß ich jetzt?
Was fällt mir dazu ein?
Also ich behaupte, dass jetzt nichts mehr geht.
Es ist alles falsch.
Was ist falsch?
I kann nicht mehr vom Typ Integer sein.
Begründung.
Aha, also x durch 2 ist vom Typ Double oder Float, also nicht Integer
und in Vorhinein kann eine Definition von f, die nur für Int oder
Integer -Argumente definiert ist, die kann nicht anwendbar sein.
Typfehler beim Aufruf.
Gibt es noch mehr Fehler?
Dürfen Sie überhaupt x dividiert durch 2 schreiben?
Für was ist denn das Schrägstrich definiert?
x muss auch Float oder Double sein.
Das ist richtig, aber 2 ist Integer.
Darf ich eine Integer-Zahl dividieren?
Ah, das 2 muss 2 Punkt werden.
Also Sie sehen, aus solchen Einzelheiten kann man Kenntnisse über
Typen zusammensetzen und kann im Vorhinein schon sagen, das Ding wird
nicht funktionieren.
Der Haskell-Übersetzer tut das für Sie.
Ein C oder C++ oder Java-Übersetzer tut das entweder gar nicht oder
nur in eingeschränktem Maße.
Und das heißt also, da kriegen Sie dann an solchen Stellen plötzlich
Laufzeitfehler, weil irgendeine Operation auf ein Bitmuster angewandt
wird, für die es gar nicht definiert ist.
Das ist der Nachteil.
Ja?
Nein?
Sie müssen ihn explizit hinschreiben.
Haben wir gehabt als Konvertierungsoperation.
Können Sie explizit hinschreiben.
Ja, und die Klassifikation der Typen kennen wir auch bereits.
Wir kennen die vordefinierten Typen, wir kennen Typvariable, eventuell
beschränkt in einer Typklasse, wir kennen Funktionstypen, wir kennen
benutzerdefinierten Typen und aufgeführt habe ich hier jetzt also nur
unter den benutzerdefinierten Typen die mit Data definierten Typen und
die mit Newtype definierten Typen, wobei in dem zweiten Fall D ein
neuer Typ ist für einen Typ, den wir schon kennen, A, bei dem aber die
Funktionen nicht übernommen werden.
Und die benutzerdefinierten Typen, genauso wie Newtype, können
parametrisiert sein.
Da können also noch weitere Typenangaben hinter dem D stehen, wie wir
das beim Kellerkennen gelernt haben, wo wir den Elementtyp noch
dahinter geschrieben haben.
Und hier sind jetzt also die Grundregeln für die Typinferenz.
Den Konstanten ist ein vordefinierter Typ zugeordnet.
Bezeichner haben zunächst einen beliebigen Typ.
Wenn ich eine Funktionsangabe habe, mit einem Argument, dann muss ich
den Argumenttyp mit dem Typ, den die Parameter in der
Funktionsdefinition hat, unifizieren.
Und er weiß, das Ergebnis erhält den Typ B.
Bedingungen sind in allen Fällen bulsch.
Sonst gibt es einen Typfehler.
Und in Funktionsdefinitionen muss ich also den Typ des Musters
unifizieren mit dem Typ des Arguments in der Signatur, falls die
Signatur angegeben ist.
Insgesamt führt die ausführliche Darstellung dieser Methoden der
Typinferenz zu dem nach zwei Herrn so genannten Hindley-Milner
-Typsystem, was in der theoretischen Informatik und in allen
funktionalen Sprachen eingesetzt wird.
Was hat die Typinferenz insgesamt für Vorteile?
Wenn Sie die Situation vergleichen, soweit Sie andere
Programmiersprachen kennen, mit einer Situation, wie Sie sie
beispielsweise in einer Skriptsprache haben.
Egal, ob Sie jetzt PHP oder irgendeine Schall nehmen.
Dann ordnen Sie dort auch den Variablen keine Typen zu.
Genauso wie wir hier nichts sagen und in der Funktionsdefinition FAB
hat A den Typ T und B den Typ T'.
Das machen wir nicht.
Genauso wenig machen wir das in diesen Skriptsprachen.
Aber die Skriptsprachen beschränken dann die Möglichkeiten zum Schluss
und sagen, ja, wenn ich gar nichts weiß, dann weiß ich immer, dass das
Argument ein Text ist.
Als solchen nehme ich ihn an und bei Bedarf bin ich noch bereit, den
in eine Zahl zu konvertieren und das war's.
Und mehr Arten von Typen kenne ich nicht.
Mit so reichhaltigen Typsystemen, wie wir sie hier vorfinden,
funktioniert das nicht.
In keiner Sprache, die keine Typ-Deklarationen kennt, funktionieren
kompliziertere Dinge als Strings oder Zahlen.
Es sei denn, in funktionalen Sprachen.
Nehmen Sie aber dann dafür Java oder C, dann müssen Sie Deklarationen
schreiben für alle diese Parameter von Funktionen und für Variable.
Und jetzt müssen Sie den Typ explizit angeben.
Wir haben festgestellt, das können wir hier zwar auch, denn
Signaturangaben sind eigentlich Angaben von solchen Typen, aber wir
müssen nicht immer.
Und wir haben hinreichend viele Beispiele gesehen, in denen wir es
nicht angegeben haben und sie haben funktioniert.
Das heißt, der große Vorteil der Typ-Inferenz ist, dass sie A, uns die
Typen nachliefert in den meisten Fällen und B, dort wo sie die Typen
nicht nachliefern kann, sondern darauf vertraut, dass wir sie vorher
angegeben haben, prüft sie mindestens Konsistenz und garantiert, dass
nicht zur Laufzeit plötzlich Typfehler auftreten könnten, die in Java
und in C niemals vollständig vermieden werden können.
Soviel zum Grundsätzlichen an Typ-Inferenz.
Und hier sehen Sie also jetzt noch Beispiele, bei denen wir mit
Absicht Fehler eingebaut haben.
Hier habe ich also True geschrieben.
Bis dahin ist das Programm bereits falsch.
Also bis an diese Stelle.
Warum?
Nun, ich habe ja da oben verlangt, dass ein Integer rauskommt.
Und Boolean ist kein Integer.
Jetzt streiche ich diese Zeile durch.
Dann wäre diese Zeile noch okay.
Aber wenn ich jetzt beide Zeilen zusammennehme, dann habe ich
ebenfalls wieder einen Typfehler.
Wie kommt der zustande?
Dann stellt sich nämlich heraus, dass er aus dieser Zeile schließt.
Aha, die rechte Seite muss ein Ausdruck sein des Typ-Boolsch.
Und jetzt sucht er in dieser Zeile verzweifelt.
Habe ich eine Definition von Plus, die ein Ergebnis liefert vom Typ
-Boolsch?
Das hat er nicht.
Infolgedessen stellt er an dieser Stelle dann einen Fehler fest.
Und wenn ich alle drei Zeilen nehme, dann sehen Sie also, was ihr für
Fehlermeldungen unten bekommt.
Nun, ich habe noch mehr solche Beispiele und gehe auf weitere solche
Beispiele am nächsten Montag ein.