Einführung in F#

Funktionale Programmierung  

Was macht F# nun so besonders?

Die Antwort lautet: Es ist besonders, weil die "Denkweise", das Prinzip hinter F# eine völlig andere ist, als bei den meisten anderen Sprachen. Visual Basic oder C# zählt man zu den sogenannten imperativen Programmiersprachen. Imperativ heißt: Ich gebe dem Computer Befehle und sage ihm Schritt für Schritt, wie er ein Problem zu lösen hat.

F# ist hier anders - Es ist eine funktionale Programmiersprache.

Historisch gesehen geht die funktionale Programmierung nicht auf Maschinensprachen wie dem heutigen Assembler zurück, sondern basiert auf dem mathematischen Konzept des sog. Lambda-Kalküls, einer formalen Sprache zum Untersuchen und Bearbeiten von Funktionen. Man hatte daraufhin festgestellt, dass dieses System den herkömmlichen Berechnungssystemen (Programmiersprachen) in Mächtigkeit um Nichts nach stand und bald entstand mit LISP die erste funktionale Sprache. Mit ML (Meta-Language) keimte im Weiteren eine ganze Familie von solchen Sprachen auf (Standard ML, OCaml), deren neuster Vertreter nun F# ist. Der Einfluss dieses Programmierparadigmas ist seit dem immer mehr gewachsen und hat bei nahezu allen modernen Sprachen seine Spuren hinterlassen.

Funktionale Programmierung orientiert sich am Begriff der mathematischen Funktion - Ein Programm ist letztendlich eine einzige, komplexe Funktion. Man konzentriert sich hauptsächlich darauf, was ein Programm tun soll und überlässt das Wie dem Compiler. Der Vorteil, der sich hieraus ergibt, ist, dass oft viel knapper und näher an einem Problem formuliert werden kann. Funktionale Programme sind dadurch oft viel kürzer, verständlicher und fehlerunanfälliger als vergleichbare imperative Programme.

Was genau aber funktionale Programmierung bedeutet werden wir im weiteren Verlauf klären.

Wozu F# lernen?  

F# hat Zukunft - Als neues Mitglied in der .NET-Familie eignet es sich sehr gut, in bereits vorhandene Projekte integriert zu werden und ist damit, im Gegensatz zu mach anderen funktionalen Sprachen, in Projekten der "wirklichen Welt" tatsächlich einsetzbar.

Als vollwertige .NET-Sprache lässt sich mit F# zwar alles anstellen wie mit VB oder C# auch, allerdings hat es wie alle anderen Sprachen seine Stärken und Schwächen. Die folgende Liste soll einen kleinen Ausblick geben, wo und weshalb F# so eine mächtige Ergänzung in unserer Programmierlandschaft ist:

1. F# produziert hochgradig fehlerunanfälligen, präzisen und wartbaren Code.
2. F# hat ein außerordentlich weit entwickeltes, striktes Typsystem, das dem Programmierer viel Arbeit abnimmt anstatt abverlangt. Eine große Zahl von Fehlern kann bereits beim Kompilieren abgefangen werden.
3. F#-Code ist sehr leicht parallelisierbar - Programme skalierbar und effizient auf Mehrkernprozessoren auszuführen ist kein Problem.
4. F# selbst ist syntaktisch sehr anpassungsfähig an spezielle Bedürfnisse eines Problemfeldes.
5. F# verändert und bereichert durch seinen unkonventionellen Ansatz die Denkweise, mit der wie an Programmierung herangehen .
6. F# kann uneingeschränkt mit allen .NET-Sprachen und Bibliotheken interagieren und nahtlos in deren Programme integriert werden.

Das prädestiniert es für folgende Aufgabenfelder:

1. Wissenschaftliches Arbeiten (Mathematik, Physik, Finanzen)
2. Problemlösung
3. Parallele Programmierung (Mehrkernprozessoren) / Netzwerke
4. Sicherheitskritische Aufgaben
5. Text/Datenverarbeitung
6. Entwicklung eigener Programmiersprachen (Domain-specific languages)

Wer hingegen benutzeroberflächen-intensive Programme zu schreiben gedenkt, wird schnell feststellen, dass dies, obgleich natürlich möglich, einer funktionalen Sprache nicht sehr liegt. Statt dessen kann eine F#-Bibliothek im Hintergrund sinnvoller sein.

Aber letztendlich ist vor Allem auch für "normale Hobbyprogrammierer" F# unbedingt einen Blick wert, denn immerhin ermöglicht es, Aufgaben auf eine neue Art sehr schnell und präzise zu formulieren und zu lösen.

Erste Schritte  

F#-Programme sehen auf den ersten Blick zunächst sehr viel anders aus, als man es gewohnt ist. Umso wichtiger ist es, direkt loszulegen und sich gleich mit der funktionalen Denkweise auseinanderzusetzen.

Installation:
Es gibt leider zur Zeit keine F#-ExpressEdition wie für VB. In den Standard-Editionen des Visual Studio ist es integriert und kann wie jede andere Sprache auch verwendet werden (Screenshot aus der kostenlosen Beta des VS2010 Professional):

Für alle, die keine der regulären VisualStudio-Editionen haben, müssen wir F# von Hand installieren. Es kann bei Microsoft kostenlos unter diesem Link heruntergeladen werden. Als kostenlose Entwicklungsumgebung mit (leider nicht sehr ausgereifter) F#-Unterstüztung kann #Develop oder die bessere Visual Studio Shell (isolated mode) von Microsoft verwendet werden. Nach der Installation von F# stehen uns zwei Programme zur Verfügung. Ein Kommandozeilen-Compiler, der aus unseren Quellcodes normale .NET-EXE-Dateien macht, und ein Konsolen-Interpreter namens FS harp I nteractive ( FSI ). Im FSI werden wir unsere ersten Schritte mit F# machen. Wir können Anweisungen in das Konsolenfenster tippen und direkt das ausgeführte Ergebnis sehen:

Das Erste, was wir eingeben, ist folgende Zeile:

#light;;

Listing 1: Erste Anweisung

#light ist ein Kommando, das den Compiler veranlasst, bestimmte Vereinfachungen an der Syntax zu aktivieren und das in jedem Programm als erste Zeile stehen sollte. Die ;; terminieren im FSI eine Eingabe und werden in normalem F#-Code weggelassen. Man könnte jetzt theoretisch die Interaktivkonsole als eine Art Taschenrechner missbrauchen, oder aber wir beginnen mit unserem ersten F#-Programm:

let x = "Hallo, Welt"

Listing 2: Erstes F#-Programm

Wie man sieht, erhalten wir prompt die Ausgabe:

val x : string

Man ahnt, es wurde eine Art Variable angelegt. Wir können x jetzt anzeigen lassen:

> x;;

val it : string = "Hallo, Welt"

Listing 3: Ausgabe von x

Das Typsystem  

Let, das erste Schlüsselwort, das wir kennengelernt haben, ist eines der wichtigsten in F#. Und wie wir gesehen haben, dient es dazu, einen Wert unter einem Namen zu speichern.

Wieso Wert und nicht Variable? Das x aus unserem Beispiel ist doch eine Variable?

Nein! Das ist es nicht - und zwar, weil es in funktionalen Programmiersprachen keine Variablen gibt. Schockierend? Hier ist es sinnvoll sich vorzustellen, dass bei Berechnungen aus Werten neue Werte entstehen, ohne dass sich der eine dafür ändern muss.

Betrachten wir eine Anweisung, die in fast allen Programmiersprachen permanent auftritt, einmal mathematisch.

X = X + 1

Listing 4: Paradoxon vieler Programmiersprachen

X, z.B. eine Zählvariable, wird hier um eins erhöht. Was logisch aussieht ist mathematisch bedenklich, denn wenn man auf beiden Seiten X abzieht, kommt man zur hochsinnvollen Aussage:

Es gibt kein X, dass gleich seinem Nachfolger ist, auch wenn das von obiger Aussage vermittelt wird. Das ist ein Sachverhalt, an dem sich funktionale Programmierung stört.

In bestimmten "Hardcore"-funktionalen (rein funktionalen) Sprachen wie Haskell ist dieser Gedanke so stark durchgezogen, dass schon für eine einfache Bildschirmausgabe tief in die mathematische Trickkiste gegriffen werden muss.

So extrem stehen die Dinge in F# nicht, immerhin muss die Sprache ja auch noch mit dem nicht funktionalen .NET-Framework interagieren können. Man kann konventionelle Variablen erzeugen (über einen speziellen mutable-Modifizierer), allerdings sind diese sehr selten und nicht unbedingt als schön oder F#-mäßig empfunden, weshalb man sich angewöhnen sollte, wo es geht nur mit Let zu arbeiten und seine Werte nicht zu ändern. Man kann so Fehlern vorbeugen und verschiedene funktionale Features besser nutzen. Die Aufforderung

x = "Foo"

Listing 5: Vergleich, nicht Zuweisung

ist keine Zuweisung, sondern nur ein Vergleich, der false ergibt.

Noch ein zweiter Aspekt ergibt sich aus unserer ersten F#-Zeile:

Die FSI-Ausgabe

val x : string

Listing 6: Explizite Typangabe

bedeutet: x ist ein Wert vom Typ string ( Zeichenkette ).

Wenn wir die Eingabe betrachten steht da aber gar nichts von string, wir haben x doch nur "Hallo, Welt" zugewiesen und doch weiß der Compiler, dass x ein string sein muss.

Diese Fähigkeit, die schon VB und C# an bestimmten Stellen boten, nennt sich Typableitung oder Type inference und wurde von F# perfektioniert. Sie ist sogar derart mächtig, dass nicht selten in kompletten F#-Programmen kein einziger Datentyp angegeben werden muss. Zum Eingewöhnen in die Typschreibweise werde ich hier dennoch immer wieder die Typsignaturen angeben.

let a = 1
let b = 15
let c = a * a + b

Listing 7: Einige Werte

Auch hier ist der Compiler direkt in der Lage, a, b und c als Ganzzahlen (int) zu bestimmen.

Wichtig : Alles in F# hat einen Wert, er ist nur manchmal "Nichts" (unit).

Ein normales Hallo-Welt-Programm lautet in F# unter Verwendung der .NET-Funktionen folgendermaßen:

System.Console.WriteLine("Hallo, Welt")

Listing 8: Hallo, Welt in F# mit .NET

F# hat allerdings die eingebaute Funktion printf(n):

printfn "Hallo, Welt"

Listing 9: Hallo, Welt in F# mit printf(n)

Beide geben "Hallo, Welt" in der Konsole aus und geben sinnigerweise nichts (also ()) zurück.

printfn ist selbst hochflexibel, wie folgendes Beispiel zeigt:

let name = "Max Mustermann"
let alter = 42

printfn "%s ist %i Jahre alt" name alter

Listing 10: Spielereien mit printfn

Die %-Werte sind (wie im printf() der Sprache C) Platzhalter für die hinten angeführten Argumente.

Interessant ist es, dass die Typsicherheit der Argumente zur Kompilierzeit geprüft wird:

printfn "%s" 42.23

Listing 11: Typsicherheit bei printfn

ist somit ungültig, da ein string (%s) mit einer Gleitkommazahl (float) belegt werden sollte.

%A passt auf alles.

Ein komplettes, kompilierbares F#-Programm sieht z.B. so aus:

#light

// System-Namespace einbinden
open System

// Ausgabe machen
printfn "Hallo, Welt"

(* Verhindern, dass die Konsole geschlossen wird *)
ignore Console.ReadKey()

Listing 12: Ein erstes Programm mit mehreren Zeilen

Anders als in VB muss hier keine Programm-Klasse angegeben werden.

Hier noch eine Übersicht der gängisten Typen.

Tabelle 1 : Gängige Datentypen

Für Typumwandlungen existieren gleichnamige Konverterfunktionen:

let x = int 42.3

Listing 13: Typkonvertierung

Funktionen  

F# ist eine funktionale Programmiersprache! Wie dieser Name vermuten lässt, sind Funktionen folglich für die Sprache von großer Bedeutung. Die Deklaration von Funktionen ist denkbar einfach: Man verwendet Let.

Let? Wird das nicht für Werte (nicht Variablen!) verwendet? Ja und nein. In einer funktionalen Sprache ist ein Wert selbst prinzipiell nichts anderes als eine Funktion, die keine Werte übergeben bekommt und einen zurückgibt. Weil sich Werte, von denen sie abhängt, ja nicht ändern dürfen und das Ergebnis einer Funktion nur von ihren Eingabewerten abhängen darf, ergibt diese Definition keine Probleme. F# sieht das zwar etwas lockerer (als z.B. Haskell) und Funktionen dürfen sich auch ein wenig unfunktional verhalten (sonst wäre wie gesagt eine Konsolenausgabe oder ein Zufallsgenerator schon etwas schwierig), aber so lässt sich zumindest das Let erklären.

Erste Funktionen

Hier kommt unsere erste Funktion:

let plus1 x = x + 1

Listing 14: Unsere erste Funktion

Und der Aufruf:

let a = 41
let b = plus1 a
let c = plus1 22

Listing 15: Aufruf unserer ersten Funktion

Wichtig: Das Gleichheitszeichen ist keine Zuweisung, sondern eine Definition. Mathematisch steht hier:
(Lies: Plus1 von x)

Eine ganze Funktion in nur einer Zeile und wieder ohne irgendeine Typangabe. Man denke an VB:

Function Plus1(ByVal a As Integer) As Integer
   Return a + 1
End Function

Listing 16: Plus1() in VB

F#: Keine Klammern, keine Kommata, keine Typangaben und kein Return. Die letzte Berechnung einer F#-Funktion ist automatisch ihr Rückgabewert .

val plus1 : int -> int

Listing 17: Typangabe einer Funktion

Der Typ dieser Funktion wird in F#, ähnlich der mathematischen Definition, so notiert, was aber wie gesagt zumeist überflüssig ist, da der Compiler den Typen ermittelt. Mit Typangabe:

let plus1 (x : int) : int = x + 1

Listing 18: Funktionsdeklaration mit Typangabe

So - Jetzt wollen wir uns an eine etwas größere Funktion wagen:

let leseString text =
    printf "%s: " text
    System.Console.ReadLine()

let name = leseString "Gib deinen Namen ein"
printfn "Hallo, %s" name

Listing 19: Eine etwas größere Funktion

leseString (Funktionen sollten üblicherweise mit Kleinbuchstaben beginnen) gibt eine Aufforderung aus und gibt den eingegebenen Text zurück. Der Compiler weiß wiederum, dass es sich bei text um einen String handeln muss, denn er muss im printf auf das Typkennzeichen %s passen.

Mehrzeilige Funktionen, generell alle Blöcke, haben keine schließenden Klammern oder Ends, sondern werden, wie in Python, über ihre Einrücktiefe identifiziert (Tabs sind in F# ungültig, man nehme Leerzeichen). Die letzte Berechnung wird zurückgegeben.

Weiter geht's:

let pythagoras a b = 
    let quadrat a = a ** 2.0
    sqrt ((quadrat a) + (quadrat b))

let res = pythagoras 3.0 4.0 

Listing 20: Pythagorasfunktion

Diese (gewiss auch sinnvoller implementierbare) Funktion verdeutlicht zwei Dinge:

• Man braucht keine Klammern, um eine Funktion aufzurufen, die Argumente kommen ohne Kommata einfach hintereinander.
• Man kann zwei Funktionen / Let's problemlos verschachteln.

val pythagoras : float -> float -> float

Listing 21: Typsignatur von pythagoras

Die Aussage float entstammt der Verwendung des Hochoperators **, der nur für floats funktioniert - Das eigentlich verwunderliche sind die Pfeile. Wieso jetzt zwei? Müsste es nicht vielmehr irgendwie so lauten?

val pythagoras : (float, float) -> float

Listing 22: Vermeintliche Typsignatur von pythagoras

Die Antwort auf diese syntaktische Besonderheit entstammt einem so genialen wie verwirrenden Konzept namens Currying. Wer nur einen groben Überblick über F# gewinnen will, für den genügt es, diesen Teil zu überfliegen.

Currying (von einem Herrn namens Curry erfunden), bedeutet, dass eine Funktion immer nur einen Parameter zur Zeit aufnimmt und gebenenfalls eine weitere Funktion zurückgibt. Die Definition lautet geklammert so:

val pythagoras : float -> (float -> float)

Listing 23: Typsignatur von pythagoras mit Klammern

Wenn ich

pythagoras 3 4

Listing 24: Aufruf von pythagoras

aufrufe, entspricht das dem Aufruf

(pythagoras 3) 4

Listing 25: Aufruf von pythagoras mit Klammern

pythagoras 3 ist selbst eine Funktion, die noch einen Parameter aufnimmt und dieser ist hier 4.

Per Currying kann man Funktionen teilweise belegen:

let plus a b = a + b
let plus1 = plus 1

Listing 26: Currying

Man sieht:

val plus : int -> int -> int
val plus1 : int -> int

Listing 27: Typsignaturen von plus und plus1

Generell gilt: Der letzte Typ ist der Rückgabetyp, die ersten sind Parametertypen.

Currying beschränkt sich nicht nur auf Funktionen, Operatoren selbst sind nichts anderes.

let plus = (+)
let durch2 = (/) 2

Listing 28: Operatoren als Funktionen

mit

val plus : int -> int -> int
val durch2 : int -> int

Listing 29: Typsignaturen von plus und durch2

Wichtig: Nur F# und ähnliche Sprachen unterstützen Currying - Eine solche Funktion ist .NET-weit einzigartig. Eine "normale" .NET-Funktion Pythagoras ließe sich in F# so nachbilden:

let pythagoras (a, b) = ...

Listing 30: .NET-Ähnliche Pythagorasfunktion

Sie hat die Signatur

val pythagoras : (float * float) -> float

Listing 31: Typsignatur der .NET-Funktion Pythagoras

und würde folgendermaßen aufgerufen:

let res = pythagoras (3, 4)

Listing 32: .NET-mässiger Aufruf von pythagoras

Mathematisch gesehen:

Die Funktion bekommt hier ein sogenanntes Tupel aus zwei Floats übergeben.

Die Tupelschreibweise für Parameter ist F#-untypisch und dient vor Allem dazu, die Standard-.NET-Funktionen aufzurufen, während sie an anderer Stelle sehr nützlich ist:

Per Tupel können Funktionen auch "mehrere" Rückgabewerte besitzen:

let divMod a b = (a / b, a % b)

let (div, mod) = divMod 10 8

Listing 33: Funktionen mit mehreren Rückgabewerten

mit

val divMod : int -> int -> (int * int)

Listing 34: Typsignatur bei mehreren Rückgabewerten

Hier werden im zweiten let beide Werte gleichzeitig zugewiesen.

Generische Funktionen

Ich komme nun zu einem weiteren Highlight im F#-Typsystem, der ebenfalls in den Standard-.NET-Sprachen schon teilweise vorhanden ist. Dieses ist der Grund, weshalb man in F# so prägnant formulieren kann - Generizität.

Als Einführungsbeispiel betrachten wir folgende Funktion:

let getFive x = 5

Listing 35: getFive

Sie nimmt einen Parameter x auf und gibt einfach immer 5 zurück. Die Frage ist: Welchen Typen hat x?

Die Antwort ist hier: Es ist egal, welchen Typen x hat, die Funktion funktioniert immer, d.h. vom Typen unabhängig, wie folgendes Beispiel beweist:

getFive 1
getFive "Hello, World"
getFive (1, "xy", 4.0)

Listing 36: Anwendung von getFive

Wir brauchen nicht zu sagen, x hat den Typen int oder string. Wir sagen lediglich, x kann jeden beliebigen Typen haben. FSI notiert das wie folgt:

val getFive : 'a -> int

Listing 37: Typsignatur von getFive

Der Buchstabe für die sog. Typvariable ist dann einfach alphabetisch fortlaufend. Generische Typen sind extrem wichtig in der funktionalen Programmierung und treten unbewusst fast überall auf, wenngleich man sie fast nie explizit notiert, sondern der Compiler sie bequem ableitet.

Higher-Order functions

Da in funktionalen Sprachen alles als Funktion gehandhabt wird, ist es ohne Weiteres möglich, mit Funktionen genau so zu rechnen, wie mit normalen Werten. Funktionen können andere Funktionen als Parameter haben oder welche zurückgeben - Man spricht von sog. Funktionen höherer Ordnung (Higher-Order functions).

Betrachten wir folgende Definition:

let zahlVerdoppeln    x = 2 * x
let stringVerdoppeln  x = x ^ x // ^-Operator verknüpft Strings

let zweimalAnwenden f x = f (f x)

Listing 38: Higher-Order functions

ZweimalAnwenden ist eine Funktion, die eine andere Funktion f auf einen Wert x zwei mal anwendet.

Logischerweise ergibt folgener Ausdruck den Wert 4:

zweimalAnwenden zahlVerdoppeln 1

Listing 39: Funktionen als Parameter

Genauso ergibt Folgendes den Wert "XXXX":

zweimalAnwenden stringVerdoppeln "X"

Listing 40: Funktionen als Parameter mit strings

Die Funktionen zum Verdoppeln sind als ganz normale Parameter übergeben worden.

Interessant sind hier die Typsignaturen:

val zahlVerdoppeln   : int -> int
val stringVerdoppeln : string -> string
val zweimalAnwenden  : ('a -> 'a) -> 'a -> 'a

Listing 41: Typsignaturen von Funktionen höherer Ordnung

Hier sieht man, der erste Parameter von zweimalAnwenden hat den Typen ('a -> 'a), d.h. eine Funktion, die einen beliebigen Typen aufnimmt und den selben Typen wieder ausgibt. Deshalb funktioniert auch die Funktion sowohl mit dem Verdoppeln von Zahlen als auch von Strings, sie funktioniert sogar mit jeder beliebigen Funktion, die obiger Typangabe folgt. Beispiel:

let zahlVervierfachen x = zweimalAnwenden zahlVerdoppeln x

Listing 42: Weitere higher-order function

Durch Currying ermöglicht sich sogar folgende Definition:

let zahlVervierfachen = zweimalAnwenden zahlVerdoppeln

Listing 43: Higher-order function mit Currying

Anonyme Funktionen

Bis jetzt hatten unsere Funktionen immer einen Namen. Das muss aber nicht sein, mit dem fun-Schlüsselwort kann man direkt anonyme Funktionen einführen, die komplett gleichwertig mit "richtigen" sind. Diese Funktion (int -> int) verdoppelt wiederum den Wert x:

fun x -> 2 * x

Listing 44: Verdoppeln als anonyme Funktion

Folgende Definition

let verdoppeln x = 2 * x

Listing 45: verdoppeln in erster Variante

ist komplett identisch mit dieser:

let verdoppeln = fun x -> 2 * x

Listing 46: verdoppeln in zweiter Variante

Anonyme Funktionen können problemlos mehrzeilig sein - Einrücktiefe und letzte Anweisung entscheiden wiederum wie bei normalen Funktionen. Betrachten wir nun einmal ein sinnvolles Beispiel: Wir möchten eine Funktion compose schreiben, die zwei Funktionen f und g miteinander kombiniert (verkettet):

let compose f g = fun x -> f (g x)

let mal2  x = 2 * x
let plus1 x = x + 1

let mal2Plus1 = compose plus1 mal2

Listing 47: compose als verkettete Funktion

compose nimmt zwei Funktionen und gibt eine anonyme zurück. Mal2Plus1 ist eine Funktion, die von einem Wert x den Wert berechnet.

An dieser Stelle möchte ich auf die VB-Version desselben Codes hinweisen:

Sub Main()
    Dim Mal2Plus1 = Compose(New Func(Of Integer, Integer)(AddressOf Plus1), _
                            New Func(Of Integer, Integer)(AddressOf Mal2))
End Sub

Function Plus1(ByVal x As Integer) As Integer
    Return x + 1
End Function

Function Mal2(ByVal x As Integer) As Integer
    Return 2 * x
End Function

Function Compose(Of A, B, C)(ByVal f As Func(Of B, C), _
                             ByVal g As Func(Of A, B)) As Func(Of A, C)
    Return Function(x) f(g(x))
End Function

Listing 48: compose in VB.NET

Die Typsignatur von compose ist schon etwas trickreich. Wiederum müssen wir die in F# zum Glück nicht angeben, dass tut ja der Compiler für uns!

val compose : ('b -> 'c) -> ('a -> 'b) -> ('a -> 'c)

Listing 49: Typsignatur von compose

Hier wird eindrucksvoll deutlich, wie nah man in funktionalen Sprachen an Problem / Aufgabenstellung arbeiten kann, ohne sich mit Typisierungen oder Deklarationen aufzuhalten.

Pipelines  

F# hat eine syntaktische Besonderheit, den Pipeline-Operator. Von manchen wird er zwar als nicht schön empfunden, aber er hat durchaus seine Vorzüge und wird in F# oft ausgiebig eingesetzt. Wie der Name schon sagt dient er dem Zwecke, eine Reihe von Transformationen hintereinander durchzuführen.

Nehmen wir an, wir wollten eine Kommazahl x quadrieren, zu einer Ganzzahl umwandeln und auf dem Bildschirm ausgeben.

Klar - Das können wir:

printfn "%i" (int (quadriere x))

Listing 50: Quadrieren und in eine ganze Zahl umwandeln

Resultat: Mengen an Klammern (ein Punkt, bei dem immer über LISP gelästert wird) und die Operationen in falscher Reihenfolge. Durch den magischen Pipeline-Operator |> lässt sich das merklich entzerren:

x |> quadriere |> int |> printfn "%i"

Listing 51: Quadrieren und in eine ganze Zahl umwandeln mit dem Pipeline-Operator

Durch die Pipeline wird also immer der zuletzt berechnete Wert als letztes Argument der folgenden Funktion verwendet. Das war's schon zu diesem Thema.

Verzweigungen  

If

Die einfachste Programmverzweigung ist das aus VB hinreichend bekannte If. If prüft eine bestimmte Bedingung und führt, je nachdem, ob sie erfüllt ist, eine von zwei Alternativen aus. Ein Beispiel sagt mehr als tausend Worte:

let passwort = System.Console.ReadLine()
if passwort = "xyz" then
    printfn "Juhu, du hast das richtige Passwort eingegeben"
else
    printfn "Nein!"          

Listing 52: If in F#

Der Unterschied zu VB ist, dass das If in F# stehts einen Wert zurückgibt, auch wenn er in diesem Beispiel wieder nichts (()) ist. If-Blöcke werden wiederum durch Einrücktiefe bestimmt und die letzte Anweisung pro Zweig bestimmt das Ergebnis.

Deshalb funktioniert auch Folgendes.

let abs x = if x >= 0 then x else -x

Listing 53: abs-Funktion in F#

Es existiert auch eine If-Variante ohne else, diese muss vom Typ unit (()) sein:

if irgendwas then
    // Tu was

Listing 54: If ohne else

Pattern-Matching

Pattern-Matching, zu Deutsch Mustervergleich, ist eine "funktionalere" und viel mächtigere Alternative zu Ifs. Es kann als eine Weiterentwicklung zu Select...Case gesehen werden und wird benutzt, um Vergleiche zu tätigen und Daten (benutzerdefiniert) auseinanderzunehmen. Pattern-Matchings geben wie Ifs einen Wert zurück.

Die einfachste Variante:

match System.Console.ReadLine() with
| "xyz" -> printfn "Juhu, du hast das richtige Passwort eingegeben"
| "xYz" -> printfn "Fast"
|    _  -> printfn "Nein!"

Listing 55: Pattern-Matching im Stil von Select-Case

Der Tiefstrich (_) passt auf jeden Eingabewert und ist quasi das Case...Else.

Der Clou am Pattern-Matching ist allerdings, dass weniger gegen Werte als gegen Datenmuster geprüft wird:

let parse x =
    match System.Int32.TryParse x with
    | true, res  -> res
    | false,   _ -> 0

parse "42"
parse "xyz"

Listing 56: Pattern-Matching für Datenmuster statt Werte

Möchte man z.B. einen Eingabe-String, der eine Zahl enthält, in diese Zahl umwandeln, verwendet man dazu meist die Funktion TryParse. Das Ergebnis von TryParse ist ein Tupel (Typ bool * int) der Form (Umwandlung erfolgreich?, Ergebnis).

Es wird nun geprüft, ob die Rückgabe auf das Muster "true und ein Ergebnis" passt - In diesem Falle war das Umwandeln der Zahl erfolgreich und das Ergebnis steht in res, andernfalls erfüllt es das Muster "false und irgendwas", was bedeutet, dass die Eingabe keine gültige Zahl war und es wird 0 zurückgegeben.

In den Mustern können auch sog. Guards, d.h. kleine Prüfungsbedingungen, verwendet werden:

let sign x = 
    match x with
    | 0            -> 0
    | _ when x > 0 -> 1
    | _            -> -1

Listing 57: Pattern-Matching mit Guards

Durch die verkürzte Notation mit function kann dieses Beispiel noch weiter gekürzt werden - ein Parameter kommt hinzu und es wird ein Matching eröffnet.

Merke : function erschafft einen zusätzlichen anonymen Parameter, der nur in den Matching-Alternativen auftritt.

let sign = function
    | 0            -> 0
    | x when x > 0 -> 1
    | _            -> -1

Listing 58: sign-Funktion mittels Pattern-Matching

Pattern-Matchings können beliebig viele Bedingungen enthalten, verschachtelt werden und die Ausdrücke können auch mehrzeilig sein.

match ... with
| x -> 
    printfn "..."
    42
| 0 -> 
    printfn "..."
    23

Listing 59: Noch mehr Pattern-Matching

Spätestens hier erkennt man, dass es in F# oft viele Techniken gibt, das Selbe zu erreichen bzw. auszudrücken.

Rekursive Funktionen  

Einfache Rekursion

Bis jetzt können wir in F# Werte anlegen, Funktionen definieren und mit ihnen rechnen. Wir konnten alles aber höchstens einmal ausführen lassen, sog. Schleifen und ähnliches fehlt. Das wird sich jetzt mit rekursiven Funktionen ändern.

Eine Funktion heißt rekursiv, wenn sie sich selbst aufruft. Folgendes Beispiel: Wie berechne ich die Summe aller Zahlen von 1 bis 100? Antwort in VB:

Function Summe(ByVal n As Integer) As Integer
    Dim Sum = 0
    For i = 1 To n
        Sum += i
    Next
    Return i
End Function

Console.WriteLine(Summe(100))

Listing 60: Listensumme in VB

Dieser Code ist denkbar "unfunktional", es werden ständig Lauf- und Summenvariable geändert.

Stellen wir statt dessen folgende Überlegung an: Die Summe von 1 bis 100 ist doch 100 plus die Summe von 1 bis 99. Die Summe von 1 bis 99 ist 99 plus die Summe von 1 bis 98. Und so weiter.

Wir können also sagen:

1. Die Summe von 1 bis n ist n plus die Summe von 1 bis n-1.
2. Weiterhin ist die Summe von 1 bis 1 gleich 1.

Über Rekursionen können wir das direkt als Programm formulieren:

let rec summe = function
    | 1 -> 1
    | n -> n + (summe (n - 1))

printfn "%i" (summe 100)

Listing 61: Listensumme in F#

Hinzugekommen ist hier lediglich das Schlüsselwort rec, das angibt, dass eine bestimmte Funktion rekursiv ist. Und siehe da: Keine Mehrfachzuweisungen, keine Schleifen, sondern eine perfekt funktionale Summenfunktion. Viele Zusammenhänge, Baumstrukturen, Listen etc. sind rekursiv strukturiert und daher mit diesen funktionalen Mechanismen gut zu beschreiben.

Endrekursion

Ein Problem besteht noch bei obiger Summenfunktion: Für große Werte bekommt man Fehlermeldungen. Das liegt daran, dass sich das Programm bei jedem Funktionsaufruf, auch bei einem rekursiven, merken muss, wo es vor dem Aufruf war, damit es danach dorthin zurückkehren kann. Das geschieht auf dem sog. Stapel (Stack) und dieser läuft bei großen Datenmengen schlichtweg über.

Die Lösung für dieses Problem nennt sich Endrekursion. Eine Funktion ist endrekursiv, wenn ihr Selbstaufruf der letzte ausgeführte Befehl ist, denn dann muss sich keine Addresse gemerkt werden! Um die berechnete Summe zwischenzuspeichern verwendet man einen sog. Akkumulator-Parameter. Das eigentliche Funktionsargument ist hier durch function anonym gehalten und quasi im Pattern-Matching versteckt:

let rec summe acc = function
    | 1 -> acc
    | n -> summe (n + acc) (n - 1)

Listing 62: Summenfunktion mit Endrekursion

Der Aufruf müsste nun

summe 1 100

Listing 63: Aufruf der endrekursiven Summe

lauten. Der Compilier kann diese Art der Rekursion komplett wegoptimieren.

Um das noch einmal zu verdeutlichen, zeige ich für die erste, nicht endrekursive Variante der Summenfunktion einen sog. Auswertungsbaum, also die Schritte, die das Programm zur Auswertung der Summenfunktion geht:

              summe 6
            = 6 + (summe 5)
            = 6 + (5 + (summe 4))
            = 6 + (5 + (4 + (summe 3)))
            = 6 + (5 + (4 + (3 + (summe 2))))
            = 6 + (5 + (4 + (3 + (2 + (summe 1)))))
            = 6 + (5 + (4 + (3 + (2 + 1))))
            = 6 + (5 + (4 + (3 + 3)))
            = 6 + (5 + (4 + 6))
            = 6 + (5 + 10)
            = 6 + 15
            = 21
          

Listing 64: Auswertungsbaum der einfach rekursiven Summenfunktion

Selbst für diese relativ kleine Eingabe sieht man, dass der Baum zwischenzeitig sehr stark wächst.

Hier nun die Auswertung einer Endrekursion:

              summe 1         6 

            = summe  (6 + 1)  5
            = summe       7   5

            = summe  (5 + 7)  4
            = summe      12   4

            = summe (4 + 12) 3
            = summe      16  3

            = summe (3 + 16) 2
            = summe      19  2

            = summe (2 + 19) 1
            = summe      21  1

            = 21
          

Listing 65: Auswertungsbaum der endrekursiven Summenfunktion

Die Größe des Baumes ist hier beschränkt, kein Stapel läuft über.

Anschaulich kann man sich den Akkumulator als den Beginn oder Ausgangspunkt einer Berechnung vorstellen. Weil wir von diesem Akkumulatorparameter eigentlich nichts wissen wollen, können wir ihn sogar in einer nichtrekursiven Hauptfunktion verstecken:

let summe n =
    let rec summeRec acc = function
        | 1 -> acc
        | n -> summe (n + acc) (n - 1)
    
    summeRec 1 n

// Aufruf:
printfn "%i" (summe 100)

Listing 66: Akkumulator versteckt

Ein weiteres Beispiel für die Fakultätsfunktion:

let factorial n =
    let rec factorialRec acc n =
        if n = 1 then acc
                 else factorialRec (n * acc) (n - 1)
    
    factorialRec 1 n

// Aufruf:
let n = 6
printfn "%i! = %i" n (factorial n)

Listing 67: Fakultätsfunktion

Wechselseitige Rekursion

Hier werde ich kurz auf einen Spezialfall von Rekursionen hinweisen: Wechselseitige Rekursion.

Zwei Funktionen heißen wechselseitig rekursiv, wenn beide die jeweils andere aufrufen. Dies ist auch auch mehrere Funktionen übertragbar. Hier ein Beispiel in Visual Basic, über dessen Sinnhaftigkeit man sich streiten kann ;-)

Sub Main()
    ZahlenZeigen(1, 10)
End Sub

Sub ZahlenZeigen(ByVal Zahl As Integer, ByVal Maximum As Integer)
    If Zahl Mod 2 = 0 Then GeradeZahlZeigen(Zahl, Maximum) Else UngeradeZahlZeigen(Zahl, Maximum)
End Sub

Sub GeradeZahlZeigen(ByVal Zahl As Integer, ByVal Maximum As Integer)
    If Zahl > Maximum Then Return
    Console.WriteLine("Gerade Zahl: {0}", Zahl)
    UngeradeZahlZeigen(Zahl + 1, Maximum)
End Sub

Sub UngeradeZahlZeigen(ByVal Zahl As Integer, ByVal Maximum As Integer)
    If Zahl > Maximum Then Return
    Console.WriteLine("Ungerade Zahl: {0}", Zahl)
    GeradeZahlZeigen(Zahl + 1, Maximum)
End Sub

Listing 68: Wechselseitige Rekursion in VB

Was nicht weiter spektakulär zu sein scheint stellt uns in F# vor ein Problem - Funktionen werden strikt von oben nach unten deklariert und verarbeitet!

Dieser eigentlich korrekt anmutende Code kann deshalb nicht funktionieren, weil die Funktion ungeradeZahlZeigen zum Zeitpunkt, da geradeZahlZeigen diese aufruft, "noch gar nicht existiert".

let geradeZahlZeigen zahl maximum =
    if zahl <= maximum then
        printfn "Gerade Zahl: %i" zahl
        ungeradeZahlZeigen (zahl + 1) maximum
        
let ungeradeZahlZeigen zahl maximum =
    if zahl <= maximum then
        printfn "Ungerade Zahl: %i" zahl
        geradeZahlZeigen (zahl + 1) maximum

Listing 69: Vermeintlich richtige wechselseitige Rekursion in F#

Streng genommen ist dieses Problem sogar zunächst in keiner Sprache elegant lösbar, da wir hier, anders als im obigen VB-Code nicht nur Funktionen, sondern auch Werte ("Variablen") deklarieren, die sich gegenseitig referenzieren, was auch VB nur durch mehrfache Zuweisung umgehen kann. Da wir in F# aber gerne funktional schreiben und ohne jene auskommen möchten, existiert glücklicherweise ein Konstrukt, um wechselseitige Rekursionen doch auszudrücken:

let rec geradeZahlZeigen zahl maximum =
    if zahl <= maximum then
        printfn "Gerade Zahl: %i" zahl
        ungeradeZahlZeigen (zahl + 1) maximum
        
and ungeradeZahlZeigen zahl maximum =
    if zahl <= maximum then
        printfn "Ungerade Zahl: %i" zahl
        geradeZahlZeigen (zahl + 1) maximum

let zahlenZeigen n = if n % 2 = 0 then geradeZahlZeigen n else ungeradeZahlZeigen n

zahlenZeigen 2 11

Listing 70: Korrekte wechselseitige Rekursion in F#

Erste grundlegende Datentypen  

F# hat, wie jede funktionale Sprache, verschiedene grundlegende Datentypen zusätzlich zu den "normalen" .NET-Typen. Diese eingebauten Typen sind speziell auf die Sprache zugeschnitten und können sehr intuitiv verwendet werden.

Tupel

Den ersten dieser Typen haben wir bereits kennen gelernt: Tupel

Sie können beliebig viele Werte aufnehmen und werden mit * notiert (bspw. int * string * float - Ähnlich der mathematischen Schreibweise des kartesischen Produktes). Durch Zuweisungen können sie wieder in ihre Bestandteile zerlegt werden:

let meinTupel = (1, "Hallo", 3.141)
let a, b, c = meinTupel

Listing 71: Verwendung von Tupel

Eine weitere Möglichkeit Tupel zu zerlegen ist das Pattern-Matching.

Typenaliase

Typenaliase sind keine Datentypen, sondern "Ersatznamen" für andere. Man kann so Typangaben einen gesonderten Sinn geben:

type Alter = int

let alterAusgeben (jahre : Alter) = printfn "%A" jahre

Listing 72: Verwendung von Typenaliasen

Records

Records sind Tupeln ähnlich, nur dass hier Werte explizit benannt werden können. Sie entsprechen im weitesten Sinne den Structures aus VB.

type Name = { Vorname : string; Nachname : string }

Listing 73: Aufbau von Records

Die einzelnen Felder können durch "normale" Punkt-Schreibweise abgefragt werden. Ein Record ist, genau wie jeder andere Typ, unveränderbar. Eine Instanz wird durch einfache Angabe der Felder oder aus einem Prototypen erstellt. Der Typ wird automatisch abgeleitet.

let max   = { Vorname = "Max"; Nachname = "Mustermann" }
let erika = { max with Vorname = "Erika" }

Listing 74: Verwendung von Records

In Funktionen kann der Record-Typ manchmal über die Felder identifiziert werden, da es aber auch uneindeutige Fälle gibt, sollte man den Record-Typen explizit angeben.

let grüssen (name : Name) = printfn "Hallo, %s, %s" name.Vorname name.Nachname

Listing 75: Record mit impliziter Typangabe

Records können, wie andere benutzerdefinierte Datenstrukturen auch, mit generischen Typen belegt werden.

type 'a Eintrag = { Position : int; Wert : 'a }

let foo = { Position = 42; Wert = "Hallo, Welt" }

Listing 76: Record mit generischen Typen

Die Typschreibweise für foo lautet:

val foo : string Eintrag

Listing 77: Typsignatur von foo

.NET-Typen

F# kann alle .NET-Typen normal instantiieren und verwenden:

let zufallsgenerator = new System.Random()

let zufallszahl = zufallsgenerator.Next(1, 10)

Listing 78: .NET-Typen in F#

Für IDisposable-Typen existiert eine Using-Schreibweise, die diese automatisch am Ende des Blocks entsorgt:

use foo = new Objekt()
// Objekt verwenden

Listing 79: IDisposable-Typen mit use

Listen  

Listen sind die funktionalen Datenstrukturen schlechthin. Eine Liste enthält eine bestimmte Anzahl von Objekten eines bestimmten Typs. Auf Elemente kann nur nacheinander zugegriffen werden, nicht über einen Index. Listen sind unveränderbar, man erstellt aus Listen immer neue Listen, was aber extrem effizient möglich ist. Allem voran sind Listen aber keine Arrays!

Listen erstellen

Ein paar Listen:

let liste1 = [1; 2; 3; 4]
let liste2 = [1..4]
let liste3 = [1, 2; 3, 4]

let liste4 = ["Hallo"; ", "; "Welt"]

Listing 80: Listen in F#

Wie man sieht ist das Erstellen von Listen denkbar einfach: Eckige Klammern und dazwischen mit Semikolon getrennte Einträge. Kommata erstellen Listen von Tupeln! Eine weitere Möglichkeit ist die Bereichsnotation mit zwei Punkten. Die Beispiellisten haben folgendermaßen notierte Typen (Siehe generische Records):

val liste1 :         int list
val liste2 :         int list
val liste3 : (int * int) list
val liste4 :      string list

Listing 81: Typsignaturen der Listen

Der Hintergrund für Listen ist folgender: Eine Liste ist aufgebaut aus Knoten - Jeder Knoten enthält einen Wert und einen nächsten Knoten. Die Liste wird durch einen sog. Nil-Knoten beendet, der keine weitere Liste enthält:

Eine gleichwertige Listenkonstruktion in der Sprache LISP sieht folgendermaßen aus:

(cons 1 (cons 2 (cons 3 '())))

Listing 82: Listen in LISP

Auch unter F# können wir den Cons-Operator :: verwenden. Die leere Liste ist [].

let liste = 1::2::3::[]

Listing 83: Cons-Operator (::) in F#

Das steckt letztendlich hinter der Schreibweise [1; 2; 3].

Mithilfe des ::-Operators können wir leicht und unglaublich effizient eine Liste nach vorne verlängern:

let liste1 = [1..4]     //    1, 2, 3, 4
let liste2 = 0::liste1  // 0, 1, 2, 3, 4

Listing 84: Listenverlängerung mittels ::

Da sich die Listen wie alle Werte nicht ändern können, muss hier nicht einmal Speicher kopiert werden. Es werden einfach Zeiger "umgehängt".

Das Anfügen an das Ende einer Liste ist währenddessen vergleichsweise ineffizent. Die Prozedur muss sich durch alle Knoten "durchhangeln":

let liste1 = [1..4]    // 1, 2, 3, 4
let liste2 = [6..8]    // 6, 7, 8

let liste3 = liste1 @ [5] @ liste2 // 1, 2, 3, 4, 5, 6, 7, 8

Listing 85: Listenverlängerung mittels @

Wegen dieser Ineffizienz bauen F#-Programme Listen oft falschherum auf und drehen sie am Ende um, was sich wiederum schnell bewerkstelligen lässt.

Manuelle Listenverarbeitung

Listenverarbeitung ist in F# sehr wichtig.

Es gibt hier zahlreiche Techniken, die grundlegende manuelle Listenverarbeitung ist trotzdem oft unumgänglich. Als klassische, rekursive Datenstruktur lässt sich funktional gut mit Listen arbeiten. Exemplarisch suchen wir eine Funktion, die die Summe einer Liste berechnet.

Hier hilft wieder der rekursive Denkansatz von vorher. Wir wissen: Eine Liste ist aus Kopfelement und der Restliste aufgebaut.

1. Die Summe einer Liste ist um das Kopfelement größer als die Summe des Rests.
2. Die Summe von einer leeren Liste ist 0

Mit ein wenig Pattern-Matching lässt sich das fast 1:1 übernehmen:

let rec summe liste =
    match liste with
    | []    -> 0
    | x::xs -> x + (summe xs)

Listing 86: Listensumme in F#

Das Matching ist hier folgenermaßen zu sehen: Passt die Liste auf das Muster [], also leere Liste, so gib 0 zurück. Passt die Liste auf das Muster Kopf::Rest, dann addiere Kopf und Summe des Rests. Die Benennung der einzelnen Teile ist beliebig, es haben sich aber verschiedene Konventionen eingebürgert:

• x::xs (das s ist als Plural-s zu verstehen - Beispiel: apple::apples)
• x::x'
• h::t (head/tail)

Unsere Summenfunktion ist leider noch nicht endrekursiv - Wir bemühen also wieder einen Akkumulatorparameter (und schreiben aus optischen Gründen das Match...With durch function um):

let summe liste =
    let rec summeRec acc = function
        | []    -> acc
        | x::xs -> summeRec (x + acc) xs

    summeRec 0 liste

Listing 87: Bessere Listensummenfunktion mit Endrekursion

Schön an Listen ist auch, dass der Compiler den Umgang mit ihnen so durchschaut, dass er automatisch auf ihre Verwendung schließt und wir (wie im Beispiel) wieder keinen einzigen Typen angeben müssen. Die Pattern-Matchings sind sehr variabel - Man kann sich fast beliebige Kombinationen aus Listenschreibweise ([]), Konstruktorschreibweise (::) und Platzhaltern (_) zusammenbauen.

| [] ->
| x::xs ->
| x::[] -> 
| _::xs ->
| _::x::_ ->
| a::b::rest ->
| _::[a, b; c, d] -> 

Listing 88: Einige Patterns für Listen

Die Syntax lässt sich sogar in Funktionsdeklarationen übertragen:

let erstesElement (x::_) = x // val erstesElement :: 'a list -> 'a

Listing 89: Listen in Funktionsdeklarationen

Zurück zur Summenfunktion: Es wäre doch sinnvoll, die Funktion so zu verallgemeinern, dass sie nicht nur die Summe, sondern jede beliebige Operation über die Listen akkumulieren kann. Eine Summenbildung wäre dann lediglich ein Spezialfall, bei dem diese Operation Plus lautet. Eine derartige Funktion nennt sich fold. Dank Higher-Order-Functions hat man hier kaum Mehraufwand. Man kann sich sogar sparen, den Akkumulatorparameter zu verstecken.

let rec fold func acc = function
    | []    -> acc
    | x::xs -> fold func (func acc x) xs 

Listing 90: fold-Funktion

Mit dieser Funktion lassen sich jetzt Summen, Produkte und Vieles mehr auf einen Schlag abdecken.

let sum  = fold (+) 0 // Summe:   Eine Liste von 0 beginnend mit + zusammenrechnen
let prod = fold (*) 1 // Produkt: Eine Liste von 1 beginnend mit * zusammenrechnen

let factorial n = prod [1..n]

Listing 91: Anwendung der fold-Funktion

List-Comprehensions

List-Comprehensions sind extrem mächtige Konstruktionen, um Listen in andere zu überführen und ihre Benutzung ist denkbar intuitiv:

let zahlen        = [1..10]
let quadratZahlen = [ for x in zahlen -> x * x ]
let geradeZahlen  = [ for x in zahlen do if x % 2 = 0 then yield x ]

Listing 92: List-Comprehensions

Hier sieht man zwei List-Comprehensions in Aktion. Die obere Syntax ist stark vereinfacht, die untere ist die Langform, wobei yield letztendlich einen Wert in die neue Liste schreibt (die Pfeilschreibweise gilt als veraltet und sollte nur in sehr einfachen Fällen wie dem obigen verwendet werden).

List-Comprehensions sind letztendlich nur ein möglicher Fall von Computation Expressions, einer Möglichkeit für F#-Programmierer, den Kontrollfluss von Programmen extrem flexibel verändern zu können, auf die ich später noch einmal zu sprechen kommen werden. Ihre imperativ anmutende Syntax ändert nichts daran, dass ihre Funktionsweise rein funktional ist. Sie können ganz normalen F#-Code enthalten und sich über viele Zeilen erstrecken - wie man es aus normalen Programmen kennt. Auch die for-Syntax ist nichts Spezielles, sie wird auch in normalem F# verwendet. Mögliche Formen sind

1. for x in Aufzählung do
2. for x in Anfang..Ende do
3. for x = Anfang to Ende do

Weiterhin unterstützt F# auch while-Schleifen (Siehe Schleifen).

Komplett-Beispiel:

for (i, x) in [for x in 1..10 -> x, x * x] do
    printfn "#%i -> %i" i x

Listing 93: Beispiel zur Verwendung einer for-Schleife mit Listen

Mit yield! kann jedes Element einer Liste in eine neue geschrieben werden. Beispiel:

let copy list = [ yield! list ]

Listing 94: Verwendung von yield!

Listenfunktionen

Der Dreh- und Angelpunkt jeder F#-Listenverarbeitung sind und bleiben die integrierten Listenfunktionen. Viele lassen sich durch for, Pattern-Matching oder List-Comprehensions besser ausdrücken, manche hingegen sind wichtig. Für die Verwendung muss jeweils ein List. ergänzt werden.

Tabelle 2 : Listenfunktionen

Ein paar Beispiele

Jetzt, da wir einiges über Listenverarbeitung gelernt haben, ist es Zeit für ein paar komplexere Beispiele.

Mittelwert, Varianz und Standardabweichung

let summeDerQuadrate = [1..10] |> List.fold_left (fun sum i -> sum + i * i) 0

Listing 95: Summe der Quadrate (Statistik)

Quicksort

Quicksort ist der Klassiker unter den Sortieralgorithmen.

Man wählt aus einer Liste ein sog. Pivotelement (Trennelement) und teilt sie dann so auf, dass man zwei Listen erhält: Eine, die alle kleineren Elemente verglichen zum Pivotelement enthält und eine für die Größeren. Dann werden beide Teillisten abermals mit Quicksort weitersortiert und die Ergebnisse in richtiger Reihenfolge zusammengehängt.

Wer möchte, kann sich vor dem Weiterlesen an dieser Stelle zunächst selbst am Algorithmus versuchen ... Ein Tipp: Eine leere Liste ist sortiert immer noch leer!

Geschafft? Hier ist ein fertiges Programm:

              
#light 

let rec quickSort = function
    | [] -> []
    | pivot::rest ->
        let linkeHälfte  = [for x in rest do if x <  pivot then yield x]
        let rechteHälfte = [for x in rest do if x >= pivot then yield x]
        
        (quickSort linkeHälfte) @ [pivot] @ (quickSort rechteHälfte)

let zahlen   = [4; 1; 7; 6; 6; 1; 0; 3; 4]
let sortiert = quickSort zahlen

printfn "Zahlen : %A\nSortiert: %A" zahlen sortiert

System.Console.ReadKey() |> ignore
              

Listing 96: Quicksort in F#

Als weitere Übung könnte man probieren, quickSort so umzuschreiben, dass es nicht < zum Vergleichen verwendet, sondern eine benutzerdefinierte Funktion.

Notiz: Die obige Implementierung ist natürlich nicht optimal, da die Liste zum Aufteilen zwei mal durchlaufen wird, in einer zeitkritischen Version verwendete man List.partition zum Aufteilen (oder ohnehin das eingebaute List.sort!)

Merge

Unser zweites Beispiel soll eine Funktion bieten, die zwei sortierte Listen miteinander zu einer großen, sortierten Liste verschmilzt.

Beispiel: [1, 2, 7, 8] + [0, 3, 3, 4, 9] -> [0, 1, 2, 3, 3, 4, 7, 8, 9]

In imperativen Programmiersprachen ist das relativ umständlich und nur mit temporärem Speicher durchzuführen, während wir das relativ intuitiv formulieren können. Gehen wir schrittweise vor:

1. Zwei leere Listen ergeben eine leere Liste.
2. Wenn beide Listen mindestens ein Element beinhalten, kommt das Kleinere von beiden in die Zielliste und die Reste werden verschmolzen.

              
#light 

let merge list1 list2 = 
    let rec mergeRec acc list1 list2 = 
        match list1, list2 with
        | [],    []               -> acc
        | x::xs, []               -> mergeRec (x::acc) xs []
        | []   , y::ys            -> mergeRec (y::acc) [] ys
        | x::xs, y::ys when x < y -> mergeRec (x::acc) xs (y::ys)
        | x::xs, y::ys            -> mergeRec (y::acc) (x::xs) ys
    
    mergeRec [] list1 list2 |> List.rev

let list1 = [1; 2; 7; 8]
let list2 = [0; 3; 3; 4; 9]

printfn "%A + %A -> %A" list1 list2 (merge list1 list2)

System.Console.ReadKey() |> ignore
              

Listing 97: Verschmelzen zweier sortierter Listen (merge)

Arrays  

Arrays kennen wir aus VB, sie sind dort quasi die Standard-Listenstruktur.

Ein Array ist eine durchnummerierte Aufzählung fester Größe. Es ist deshalb auch nur in den Fällen sinnvoll, bei denen sich die Aufzählung in ihrer Größe nicht ändert und man zwingend über einen Index auf die Werte zugreifen muss. Sonst sind die flexibleren Lists die bessere Wahl.

Der gesamte Umgang mit Arrays ist dem mit Listen sonst sehr ähnlich.

let meinArray  = [| 1; 2; 3 |]
let meineWörter = "Hallo Welt".Split [| ' ' |] 

Listing 98: Deklaration von Arrays

Arrays können durch for-Schleifen durchlaufen werden, genau so wie durch Zugriff per nullbasiertem Index. Die Elemente in einem Array sind veränderlich , was prinzipiell "unfunktional", aber stellenweise auch sinnvoll ist. Hierfür verwendet man eine Notation mit <- . Für Arrays existiert ein Pendant zu den List-Comprehensions sowie für fast alle List.*-Methoden, die jetzt Array.* lauten. Auf Elemente kann in der Syntax .[] zugegriffen werden. Dieser Indizierungszugriff wird bei vielen .NET-Typen wie den System.Collection.-Listen oder auch Strings verwendet. Auch haben Arrays eine .Length-Eigenschaft, die die Anzahl der enthaltenen Elemente angibt.

Ein paar Beispiele:

          
let ersteBuchstaben = [| for wort in meineWörter -> wort.[0] |] 

let meinArray  = [1; 2; 3] |> List.to_array
let meinArray2 = [| 1..3 |]

printfn "Zweiter Eintrag: %i" meinArray.[1]

meinArray.[0] <- 42

printfn "Zweiter Eintrag: %i" meinArray.[1]
          

Listing 99: Beispiele zur Verwendung von Arrays in F#

Ein klassisches Beispiel für einen imperativen Algorithmus mit veränderlichen, indexbasierten Daten ist das Primzahlsieb des Eratosthenes:

          
let primeEratosthenes n =
 let sieb = [| for i = 0 to n do yield 1 |]  
 for i = 2 to n do
    if sieb.[i] >0 then
       for j in 2*i..i..n do
          sieb.[j] <- 0
 [ for i in 2..n do if sieb.[i] > 0 then yield i ]
          

Listing 100: Sieb des Eratosthenes

Arraytypen werden folgendermaßen notiert:

val sieb : int array

Listing 101: Typsignatur von einem Array

Sequenzen  

Sequenzen sind eine abstraktere Form, eine Aufzählung von Objekten zu repräsentieren. Sowohl Listen als auch Arrays sind Spezialformen der Sequenzen. (Für die eingefleischten .NET-ter: Eine Sequenz ist alles, was IEnumerable<T> implementiert).

Ein paar Stichpunkte zu den Eigenschaften von Sequenzen:

• Typisiert
• Unveränderlich
• Nur schrittweise zugreifbar
• Sequence-Expressions (Spezialfall: List-Comprehensions) als bequeme Syntax
• Iteration erfolgt per for
• Zahlreiche Funktionen in Seq.*

Unterschiede:

• Keine Initialisierungsschreibweise - Nur yield kann Elemente generieren
• Bedarfsauswertung
• Kein Pattern-Matching zur Dekomposition
• Selten manuelle Verarbeitung

          
let zahlen = seq { 1..100 }
let quadratZahlen = seq { for i in zahlen -> i * i }

let alleNatürlicheZahlen = Seq.init_infinite (fun i -> i)
let alleQuadratzahlen    = seq { for i in zahlen -> i * i }

printfn "%A" (quadratZahlen |> Seq.take 20)
printfn "%A" (alleQuadratzahlen |> Seq.take 20) 
          

Listing 102: Verwendung von Sequenzen

Man sieht: Es besteht kein Handhabungs-Unterschied zwischen endlichen und unendlichen Sequenzen, da beide hier nur für 20 Elemente ausgewertet werden. Hinter der Schreibweise seq {} verbirgt sich eine sehr interessante Konstruktion namens Computation-Expression, die im Grunde gar nicht speziell für Sequenzen geschaffen wurde und uns bei asynchronen Berechnungen nocheinmal begegnet.

Notiert werden Sequenzen so:

val zahlen : seq<int>

Listing 103: Typsignatur einer Sequenz

Der Trick an Sequenzen ist, einfach mit allen Möglichkeiten zu rechnen und es dem Programm zu überlassen, dass es die Möglichkeiten, die nie in Frage kommen, gar nicht berechnet.

          
let prim = 
    let rec primRec altePrimzahlen n = seq {
        if altePrimzahlen |> List.forall (fun p -> n % p <> 0) then
            yield n
            yield! (primRec ( altePrimzahlen @ [n]) (n + 2))
        else
            yield! (primRec altePrimzahlen (n + 2))
    }
    seq { yield 2; yield! primRec [2] 3 } 

printfn "Die ersten 20 Primzahlen: "

for p in prim |> Seq.take 20 do printfn "%i" p
          

Listing 104: Unendliche Sequenz von Primzahlen

Berechnen wir einmal als Beispiel die unendliche Sequenz aller Primzahlen. Dabei können die bereits berechneten Primzahlen gespeichert werden, um die Berechnung später zu beschleunigen.

Eine andere Anwendungsform ist z.B. das sehr effiziente Auswerten von Spielbäumen, denn auch hier werden nur die Lösungen generiert, die überhaupt in Betracht kommen.

Hier nocheinmal eine Verdeutlichung des Terms Bedarfsauswertung:

          
let rec numb3rs() = seq {
 
    printf "Gib einen Wert ein: "
    let num = int(System.Console.ReadLine())
        
   
    yield num
    yield! numb3rs()
}

numb3rs() |> Seq.take 10 |> Seq.iter (printfn "Erhalte Wert: %i\n")

System.Console.ReadKey() |> ignore
          

Listing 105: Sequenz zur Verarbeitung einer Zahlenreihe

Hier wird nicht etwa die Eingabe von 10 Werten gefordert und dann eine Ausgabe gemacht, vielmehr wird nach einem Wert gefragt, dieser eingegeben und direkt danach ausgegeben. Die Sequenzfunktion selbst hat dabei keine Abbruchbedingung, wird aber dennoch nur so weit berechnet, wie benötigt.

Option types  

Option-Types werden an vielen Stellen in F# benötigt und zwar überall dort, wo Berechnungen nicht immer ein Ergebnis produzieren. Sie entsprechen den NULL-fähigen Datentypen aus SQL oder VB. Die Signatur

val x : int option

Listing 106: Typsignatur eines Option-Types

kann also verstanden werden als: "x ist das Ergebnis einer Berechnung, die eine Zahl ergeben kann, oder aber fehlschlägt und nichts zurückgibt".

Ein klassisches Beispiel für Nullwerte ist die Division zweier Zahlen - entweder funktioniert die Division oder es wurde durch 0 geteilt, was bekanntlich nicht funktioniert:

let safeDiv a b =
    if b <> 0 then Some(a / b)
    else None

Listing 107: Überprüfte Division

Eigentlich recht simpel - Wenn der Divisor ungleich 0 ist, dann geben wir etwas zurück, nämlich a/b, andernfalls nichts. Hierzu verwenden wir die Datenkonstruktoren (siehe Discriminated unions) Some und None. Die zugehörige Signatur:

val safeDiv : int -> int -> int option

Listing 108: Typsignatur des Option-Types für sichere Division

Über Pattern-Matching kann der Options-Type wieder auseinandergebaut werden. An dieser Stelle folgt das längst überfällige und obligatorische Zahlenraten:

          
let zahlenRaten max zahlVersuche =
    let ziel = (new Random()).Next(1, max)
    
    printfn "Willkommen beim Zahlenraten\nErraten Sie die Zahl zwischen 1 und %i" max
    printfn "Sie haben %i Versuche\n**********************\n\n" zahlVersuche
    
    let rec rateZahl versuch =
        if versuch > zahlVersuche then None
        else
            printf "#%i - Geben sie ihren Tipp ein: " versuch
            match Int32.TryParse(Console.ReadLine()) with
            | false, _              -> printfn "Keine Zahl!\n"; rateZahl  versuch
            | true, n when n < ziel -> printfn "Zu klein\n"   ; rateZahl (versuch + 1)
            | true, n when n > ziel -> printfn "Zu groß\n"    ; rateZahl (versuch + 1)
            | true, n               -> Some(versuch)
    
    match rateZahl 1 with
    | Some(n) -> printfn "Juhu - Sie haben die Zahl in %i Versuchen erraten" n
    | None    -> printfn "Sie haben verloren - Ergebnis: %i" ziel

zahlenRaten 20 5
          

Listing 109: Zahlenraten

Mengen und Wörterbücher  

Oft benötigt man Datenstrukturen für Mengen (Set) und Wörterbücher (Map). Eine Menge ist eine Auflistung von einzigartigen Elementen (ohne doppelte Exemplare), ein Wörterbuch speichert Wert/Schlüssel-Paare. Obschon beides zurecht durch Listen machbar erscheint, bietet uns F# hierfür die Datenstrukturen Set<T> und Map<TKey, TValue> an, die durch ihre interne Repräsentation durch sog. Rot-Schwarz-Bäume immer geordnet vorliegen und gleichzeitig die Effizienz des Zugriffs stark erhöhen. Beide Datenstrukturen sind unveränderlich. Map und Set können hier als Konstruktoren aus Listen fungieren. Ähnlich wie für Listen sind die nötigen Funktionen (union, intersect, size, etc) unter Set.* bzw. Map.* vorhanden. Per Internet oder .NET-Reflector kann man die komplette Liste erhalten. Hier zwei Beispiele:

Sets:

          
let nums = Set [1..10]
let nums2 = nums + Set [5..20]

let quadrate = nums2 |> Set.map (fun i -> i * i)

let diff = squares - Set [1..5]

let schnitt = Set.intersect diff (Set [1..20])

for i in schnitt do printfn "%i" i
          

Listing 110: Verwendung von Sets

Maps:

          
let personen = Map ["Max", 42; "Erika", 41]

let name = 
    printf "Gib deinen Namen ein: "
    System.Console.ReadLine()

let personen2 = personen.Add("John", 23)

match personen2 |> Map.tryfind name with
| Some(alter) -> printfn "Du bist %i Jahre alt" alter
| None        -> printfn "Du bist nicht im System verzeichnet - Glückwunsch"

let foo = "Erika"

printfn "Hallo %s, du bist %i Jahre alt" foo personen.[foo]
          

Listing 111: Verwendung von Maps

Imperative Elemente  

Auch wenn man in F# nach Möglichkeit funktional programmieren sollte - wenn man das nicht will sollte man es gar nicht erst verwenden, sondern bei VB/C# bleiben - unterstützt F# zwecks Interaktion mit dem .NET-Framework und mancher Anwendungsgebiete wie OCaml selbst auch imperative Elemente.

Variablen

In F# gibt es neben den Werten auch "echte" Variablen, die, ganz im Sinne des Wortes, variabel sind. Sie werden sehr selten verwendet - Ein Beispiel sollte hier genügen:

            
let mutable foo = 23
foo <- 42

let mutable summe = 0

for x in 1..10 do
    summe <- summe + x

printfn "%i" summe
            

Listing 112: Verwendung von Variablen in F#

Die Zuweisungssyntax per <- findet auch bei Zuweisungen an Eigenschaften von .NET-Objekten Verwendung.

Verzweigungen

Verzweigungen können natürlich auch intuitiv eingesetzt werden - sowohl mit zwei als auch mit nur einer Alternative.

let passwortAbfragen() = 
    printf "Geben sie ihr Passwort ein: "
    let eingabe = System.Console.ReadLine()
    if eingabe = "Foo" then
        printfn "Gut"
       

passwortAbfragen()

Listing 113: Verwendung von if-Verzweigungen

Der Rückgabetyp ist entsprechend nichts: ().

Schleifen

Der Vollständigkeit wegen hier nocheinmal die verschiedenen (schon in List-Comprehensions angesprochenen) Schleifenkonstrukte auf eine Blick:

            
printf "Programm fortsetzen? [y/n]"
while System.Console.ReadLine() <> "n" do
    printf "Wirklich? "
    
for i =  1 to 10  do printfn "%i" i
for i in 11..20   do printfn "%i" i
for i in [21..30] do printfn "%i" i
            

Listing 114: Verschiedene Schleifentypen in F#

Referenzzellen

Sollten wirklich einmal veränderliche Werte nötig sein - und das kommt wohl oder übel vor - neigt man in F# wegen ihrer geringen Flexibilität dazu, Variablen durch eine Alternative auszudrücken - Referenzzellen. Die Referenzzelle kann selbst nicht verändert werden und speichert einen Wert. Dieser wiederum kann verändert werden. Vorteil der Referenzzellen ist, dass diese normal in Datenstrukturen gespeichert, typabgeleitet und aus Funktionen zurückgegeben werden können - Dinge, die bei mutable-Variablen nicht der Fall sind.

            
let foo = ref 23
foo := 42

let summe = ref 0
for x in 1..10 do
    summe := !summe + x

printfn "%i" !summe
printfn "%A" [summe, foo]
            

Listing 115: Verwendung von Referenzzellen

Notiert werden Referenzzellen so:

val summe : int ref

Listing 116: Typsignatur einer Referenzzelle

Die Verwendung der Operatoren := und ! sind dabei charakteristisch und können von der Typinferenz als Anhaltspunkt verwendet werden.

Eine interessante Technik ist es, veränderliche Werte in anonymen Funktionen wegzukapseln.

Beispiel 1: Die oberste Funktion selbst hat nichts mit veränderlichen Werten zu tun - Die Funktionalität entsteht erst durch die übergebene anonyme Funktion:

  let alleVerarbeiten list op = for x in list do op x

  let summe = ref 0
  alleVerarbeiten [1..10] (fun x -> summe := !summe + x)

  printfn "Summe: %i" !summe

Listing 117: Kapselung von Referenzzellen in anonymen Funktionen

Beispiel 2: Hier wird die Referenzzelle ganz verborgen:

            
let counter =
    fun () ->
        let i = ref 0
    
        fun () ->
            i := !i + 1
            !i

let foo = counter()
let bar = counter()

printfn "%i" (foo())
printfn "%i" (foo())
printfn "%i" (bar())
printfn "%i" (bar())
            

Listing 118: Noch mehr Kapselung einer Referenzzelle

Dieses Programm hat erstaunlicherweise die Ausgabe 1 2 1 2 - Der vom Benutzer komplett abgekapselte Zähler i in foo oder bar erhöht sich bei jedem Aufruf um Eins. Counter könnte dabei als eine Art Konstruktor gesehen werden - foo und bar als Instanzen.

            
val counter : unit -> (unit -> int)

val foo : unit -> int
val bar : unit -> int
            

Listing 119: Typsignatur von counter, foo und bar

Veränderliche .NET-Aufzählungsklassen

Die (unfunktionalen) Aufzählungsklassen des Frameworks können in F# natürlich ebenfalls verwendet werden.

            
open System.Collections.Generic

let zufall = new System.Random()
let meineListe = new ResizeArray<int>() // Aliasname für List<int>

for x in 1..10 do
    meineListe.Add (zufall.Next(1, 100))

meineListe.[0] <- 0
meineListe.Add (42)
meineListe.Sort()

for x in meineListe do
    printfn "%i" x
            

Listing 120: Verwendung von .NET-Aufzählungsklassen

Die Werte der Klassen können verändert werden und da auch sie auf IEnumerable basieren, lassen sie sich mit den Seq.*-Funktionen sowie F#-Schleifen intuitiv verarbeiten. Wird beim generischen Parameter _ angegeben, versucht der Compiler, den Typen selbst abzuleiten.

Vergleich zu imperativen Programmiersprachen

An dieser Stelle möchte ich noch ein kleines Beispiel geben, wie eine funktionale Herangehensweise bestimmte Fehler vermeiden kann. Exemplarisch behandle ich ein Programm, welches die Anzahl der Nullen in einer Liste ermitteln soll. Das funktional zu formulieren ist kein Problem:

• Eine leere Listen enthält keine Nullen
• Eine Liste, die mit 0 beginnt enthält eine Null mehr als die Restliste

Code:

            
let rec nullenZählen = function
    | [] -> 0
    | 0::xs -> nullenZählen xs + 1
    | _::xs -> nullenZählen xs
            

Listing 121: Funktion nullenZählen

Hier ist die Korrektheit des Verfahrens unmittelbar erkenntlich. Zum Vergleich muss nun ein imperativer C-Code herhalten: (Der Operator ++ erhöht eine Variable um Eins, laenge ist die Arraylänge).

            
int nullen;

for (int i = 1; i <= laenge; i++) {
    if (zahlen[i] = 0) {
        nullen++;
    }
}
            

Listing 122: Nullen zählen in C

Das sieht augenscheinlich richtig aus: Wir gehen alle Indizes durch, rufen das Arrayelement ab und wenn dieses 0 ist, dann erhöhen wir einen Zähler. Falsch gedacht, dieser winzige Code enhält gleich vier Fehler. Gefunden? Nein? Sie sind sehr versteckt, und auch wenn man hier auf die C-Syntax schimpfen kann, ist doch die eigentliche Ursache, dass man hier dem Programm Schritt für Schritt sagen muss, wie es zu rechnen hat.

1. zahlen[i] = 0 ist kein Vergleich, sondern eine Zuweisung an das aktuelle Arrayelement. Diese lässt deshalb in einer If-Anweisung verwenden, weil der gesamte Ausdruck den Wert 0 annimmt, der als false gehandhabt wird.
   Richtig: zahlen[i] == 0
2. Die Schleife zählt von 1 bis laenge; Arrays werden von 0 indiziert, deshalb lautet das richtige Intervall [0; laenge)
3. Nullen, unsere Zählvariable, wurde nicht initialisiert und hat deshalb irgendeinen Wert, aber nicht 0, wie am Anfang gewünscht.

Unser korrigierter Code muss also folgenermaßen lauten:

            
int nullen = 0;

for (int i = 0; i < laenge; i++) {
    if (zahlen[i] == 0) {
        nullen++;
    }
}
            

Listing 123: Korrektes Zählen von Nullen in C

All dies sind Fehler, die in funktionalen Sprachen nicht oder nur selten auftreten können.

In C++ bieten die Standardbibliothek und z.B. BOOST Lösungen für solche Probleme und genau an diesen Stellen wird die Sprache ein wenig mehr funktional.

Im Gegenzug muss man wiederum betrachten, dass unsere Computer imperativ arbeiten. Es gibt einen Arbeitsspeicher, Festplatten, Bildschirme uvm. in denen laufend geschrieben, gelesen und verändert wird. Alles, was irgendwie mit Eingaben und Benutzerinteraktion zu tun hat, ist zwangsläufig nicht mehr rein funktional - Nach diesem Prinzip wäre es ja egal, wie oft und wann ein Benutzer einen Button anklickt.

Discriminated unions  

Discriminated unions kann man am einfachsten als eine Menge von alternativen Typen verstehen.

Am besten lässt sich das wie so oft mit einem Beispiel zeigen. Definition: Ein Wahrheitswert (Boolean) ist entweder True (Wahr) oder False (Falsch). Das können wir in F# notieren.

          
type Boolean = True | False
          

Listing 124: Eigener Boolean in F#

Es folgt das Anwendungsbeispiel:

          
let wahr = True
let falsch = False

let zuBool = function
    | True  -> true
    | False -> false

let ist4 n =
    if n = 4 then True else False  

if zuBool (ist4 4) then
    printfn "Wahr"
else
    printfn "Falsch"
          

Listing 125: Unser Boolean zum standard-boolean

True und False sind hier sog. Konstruktoren des Typs Boolean (diese werden konventionell groß geschrieben). Wir können sie wie jeden anderen Wert auch zurückgeben oder an Funktionen übergeben. Interessant ist hierbei v.A. die Funktion zuBool, die unseren Boolean-Typen zu einem Standard-F#-Boolean umwandelt. Hier wird Pattern-Matching eingesetzt, um entsprechend der Alternativen zu verzweigen. Folglich können wir schreiben:

          
let tauschen = function
    | True  -> False
    | False -> True
          

Listing 126: Negation mit unserem Boolean

Die Funktionssignaturen lauten:

          
val wahr     : Boolean
val falsch   : Boolean
val zuBool   : Boolean -> bool
val ist4     : int -> Boolean
val tauschen : Boolean -> Boolean
          

Listing 127: Funktionssignaturen mit eigenem Boolean

Parameterisierte und generische Varianten

Unsere Typen und Konstruktoren können aber nicht nur statische Alternativen ausdrücken, sie können auch Werte aufnehmen. Beispiel wäre ein erweiterter Boolean, der neben Wahr und Falsch auch ein Fehlerergebnis mit Meldung aufnehmen kann.

            
type BoolComputation =
    | True
    | False 
    | ComputationError of string
            

Listing 128: Erweiterter Boolean

Beispiel:

            
let kannTeilen a b =
    if b <> 0 then
        if a % b = 0 then True else False
    else
        ComputationError("Fehler - Teilen durch 0")
            

Listing 129: Anwendung des erweiterten Booleans

Eine Auswertung erfolgt, wie gewohnt, mit Pattern-Matching:

            
match kannTeilen 14 0 with
| True -> printfn "Teilbar"
| False -> printfn "Nicht teilbar"
| ComputationError(message) -> printfn "Fehler: %s" message
            

Listing 130: Auswertung eines erweiterten Booleans

Soll ein Konstruktor mehrere Werte aufnehmen, so werden Tupel-Typen übergeben.

Auch können (wie bei generischen Records) Typargumente übergeben werden. So können wir einen wichtigen F#-Typen selbst nachbauen:

            
type 'a Option = 
    | None
    | Some of 'a
            

Listing 131: Typargumente in discriminated unions

Dieser ist identisch mit den Option-Typen, die wir bereits kennengelernt haben, da sie in eben dieser Weise definiert wurde.

Rekursive Typen

Hier folgt der Hauptgrund, weshalb discriminated unions so wichtig in F# sind: Sie können mit sich selbst (rekursiv) parameterisiert werden. Berechnungen, Bäume und verkettete Listen können alle direkt in ihrer Definition entsprechend definiert werden.

Beispiel 1 - Verkettete Listen:

Eine verkettete Liste ist entweder

• Leer oder
• Ein Kopfelement und eine Restliste

Voilà:

            
type 'a LinkedList =
    | Nil 
    | Cons of 'a * 'a LinkedList

let meineListe = Cons(1, Cons(2, Cons(3, Nil))) // int LinkedList

let rec summe = function
    | Nil -> 0
    | Cons(x, xs) -> x + summe xs
            

Listing 132: Verkettete Liste

Diese Definition der Liste entspricht wiederum genau den in F# integrierten lists, wobei Nil (not in list) als [] und Cons (construct) als :: notiert wird.

Beispiel 2 - Binäre Bäume:

Ein binärer Baum ist entweder

• Leer oder
• Ein Wurzelelement und ein rechter sowie linker Teilbaum

Auch hier kann die Definition direkt in einen Typen gefasst werden.

            
type 'a Tree =
    | Leaf
    | Node of 'a * 'a Tree * 'a Tree

let myTree = Node(5, 
                Node(3,
                    Node(1, Leaf, Leaf),
                    Node(4, Leaf, Leaf)),
                Node(7, 
                    Leaf,
                    Node(10, Leaf, Leaf)))
            

Listing 133: Binärbaum

Bäume so zu erstellen ist wenig sinnvoll, gemeinhin verwendet man sie eher, um z.B. Werte zu sortieren. Dazu benötigen wir Funktionen zum Einfügen und Durchlaufen des Baumes.

Einfügen eines Elementes x in einem Baum:

• Wenn x <= aktueller Knotenwert: Füge x in den linken Teilbaum ein
• Wenn x > aktueller Knotenwert: Füge x in den rechten Teilbaum ein
• Wenn der Baum leer ist, dann besteht der neue Baum aus x

So sei es:

            
let rec einfügen element baum = 
    match baum with 
    | Node(wurzel, links, rechts) when element <= wurzel -> Node(wurzel, einfügen element links, rechts)
    | Node(wurzel, links, rechts) when wurzel <= element -> Node(wurzel, links, einfügen element rechts)
    | _ -> Node(element, Leaf, Leaf)

let berechneBaum liste = List.fold (fun baum element -> einfügen element baum) Leaf liste
            

Listing 134: Binärbaum zum Sortieren von Werten

Jetzt benötigen wir nur noch eine Funktion zum Durchlaufen eines Baumes und fertig ist das Binärbaum-Sortieren. Hier gilt: Erst den linken Baum durchlaufen, dann das Wurzelelement und dann den rechten.

            
let rec durchlaufen baum = 
    match baum with
    | Leaf -> Seq.empty
    | Node(wurzel, links, rechts) -> seq {
          yield! durchlaufen links
          yield wurzel
          yield! durchlaufen rechts
      }
            

Listing 135: Durchlaufen des Binärbaums

Hier nocheinmal die komplette Baum-Bibliothek mit Sortierfunktion:

            
type 'a Tree =
    | Leaf
    | Node of 'a * 'a Tree * 'a Tree

let rec einfügen element = function
    | Node(wurzel, links, rechts) when element <= wurzel -> Node(wurzel, einfügen element links, rechts)
    | Node(wurzel, links, rechts) when wurzel <= element -> Node(wurzel, links, einfügen element rechts)
    | _ -> Node(element, Leaf, Leaf)

let berechneBaum liste = List.fold (fun baum element -> einfügen element baum) Leaf liste

let rec durchlaufen = function
    | Leaf -> Seq.empty
    | Node(wurzel, links, rechts) -> seq {
          yield! durchlaufen links
          yield  wurzel
          yield! durchlaufen rechts
      }

let sortieren daten = (berechneBaum >> durchlaufen) daten

for x in sortieren [1; 4; -1; 0; 3; 1; 2; 1] do
    printf "%i, " x
            

Listing 136: Komplette Implementierung des Binärbaums

Berechnungen mit Discriminated unions

Discriminated unions eignen sich sehr gut, um komplexe Daten im Speicher zu repräsentieren. Ein interessantes Beispiel ist hierbei die Darstellung eines Programms, wie in diesem Fall einer arithmetischen Berechnung, im Speicher.

Beispiel: Ein Term ist hiermit definiert als eine Zahl, eine Variable oder eine Operation, die zwei Terme verknüpft.

            
type Term = 
    | Zahl  of int
    | Var   of string
    | Plus  of Term * Term
    | Minus of Term * Term
    | Mal   of Term * Term
    | Durch of Term * Term
            

Listing 137: Muster für mathematische Terme

Ein Ausdruck wie 2x+1 würde entsprechend so notiert:

            
let beispiel = Plus(Mal(Var("x"), Zahl(2)), Zahl(1))
            

Listing 138: 2x+1 als Term

Das Ausrechnen gestaltet sich dank Mustervergleich und Rekursion extrem einfach:

            
let auswerten variablen =
    let vars = Map.of_list variablen
    let rec eval = function
        | Zahl(n)     -> n // Eine Zahl wir zu sich selbst ausgewertet
        | Var(name)   -> vars.[name] // Variablen werden durch konkrete Werte ersetzt
        | Plus(a, b)  -> (eval a) + (eval b) 
        | Minus(a, b) -> (eval a) - (eval b)
        | Mal(a, b)   -> (eval a) * (eval b)
        | Durch(a, b) -> (eval a) / (eval b)   
    eval    

let ergebnis = auswerten ["x", 10] beispiel

printfn "%i" ergebnis
            

Listing 139: Berechnen eines mathematischen Ausdrucks

Diese Art der Repräsentation von Berechnungen ist extrem hilfreich. Man kann in F# beispielsweise relativ leicht eigene Programmiersprachen schreiben, deren Quelltext in solche Strukturen überführt und dann ausgewertet wird. Später werden wir sehen, dass es sehr praktische Wege gibt, Text-Eingaben zu parsen, d.h. sie vom Programm in eine solche, verwertbare Form umzuwandeln.

Als Minimal-Beispiel werde ich trotzdem einmal zeigen, wie man einen Term in sog. UPN-Notation (umgekehrte polnische Notation) parst.

Bei einem UPN-Term stehen die Operatoren (Rechenzeichen), also z.B. + oder -, nicht zwischen ihren Operanden, sondern hinter ihnen - Man spricht auch von Postfix-Notation, während ein "normaler" Term in Infix-Notation steht.

Beispiel: Der Term

(1 + 2) * 3

entspricht folgendem in UPN.

1 2 + 3 *

Der Vorteil dieser Notation im Bezug auf Computer ist vor Allem, dass sie sich viel leichter auswerten lässt und man keine Operatorprioritäten berücksichtigen muss (Punkt-Vor-Strich).

Tatsächlich ist das Ausrechnen oder auch Umwandeln eines solchen Terms in konventionelle Notation mithilfe eines sog. Stapels nahezu trivial.

1. Eine Zahl wird oben auf den Stapel gelegt.
2. Ein Operator nimmt die beiden obersten Werte vom Stapel, rechnet mit ihnen und schreibt sie wieder oben hinauf

Der folgende Ablauf zeigt, wie man obigen Term schrittweise ausrechnet:

          
Beginn: Leerer Stapel        => []
1     : 1 auf Stapel legen   => [1]
2     : 3 auf Stapel legen   => [2, 1]
+     : Werte addieren       => [1 + 2]
3     : 3 auf Stapel legen   => [3, 1 + 2]
*     : Werte multiplizieren => [(1 + 2) * 3]
Ende  : Oberstes Element enthält das Ergebnis => (1 + 2) * 3
            

Das können wir nun problemlos in funktionalen F#-Code schreiben. Wir betrachten eine rekursive Funktion parse, die eine Liste von Symbolen (Zahlen, Variablen oder Operatoren) sowie einen Stapel von Termen als Argument enthält. Ein Stapel ist dabei nichts als eine konventionelle Liste, an die, wie üblich, von vorne angehängt wird.

            
let rec parse stapel symbole = 
            

Listing 140: Kopf der parse-Funktion

Jetzt gilt es, die einzelnen Vorschriften umzusetzen. Mit Pattern-Matching müssen wir nichteinmal groß umformulieren.

        
match stapel, symbole with
| y::x::stapel', "+"::symbole' -> parse ((Plus(x, y))::stapel') symbole'
| y::x::stapel', "-"::symbole' -> parse ((Minus(x, y))::stapel') symbole'
| y::x::stapel', "*"::symbole' -> parse ((Mal(x, y))::stapel') symbole'
| y::x::stapel', "/"::symbole' -> parse ((Durch(x, y))::stapel') symbole'
        

Listing 141: Körper der parse-Funktion

1. Ist das aktuelle Symbol ein Operator und enthält der Stapel mind. zwei Elemente, dann verrechne beide und setze die Berechnung mit den restlichen Symbolen und dem aktuellen Ergebnis oben auf dem Stapel fort:

               
   | _, sym::symbole' -> match Int32.TryParse(sym) with
                          | (true, i) -> parse ((Zahl(i)::stapel)) symbole'
                          | _         -> parse ((Var(sym))::stapel) symbole'

   Listing 142: Elemente verrechnen

2. Wenn wir keinen Operator vorliegen haben, prüfe, ob es sich um eine Zahl oder eine Variable handelt und schreibe sie entsprechend auf den Stapel.
3. Sind alle Symbole durch, sind wir fertig, geben also das Oberste (und hoffentlich Einzige) Element des Stapels zurück.

   | _, [] -> List.hd stapel

   Listing 143: Element auf den Stapel legen

Die ganze Funktion sieht dann so aus:

            
let rec parse stapel symbole = 
    match stapel, symbole with
    | y::x::stapel', "+"::symbole' -> parse ((Plus(x, y))::stapel') symbole'
    | y::x::stapel', "-"::symbole' -> parse ((Minus(x, y))::stapel') symbole'
    | y::x::stapel', "*"::symbole' -> parse ((Mal(x, y))::stapel') symbole'
    | y::x::stapel', "/"::symbole' -> parse ((Durch(x, y))::stapel') symbole'
    | _, sym::symbole' -> match Int32.TryParse(sym) with
                           | (true, i) -> parse ((Zahl(i)::stapel)) symbole'
                           | _         -> parse ((Var(sym))::stapel) symbole'
    | _, [] -> List.hd stapel
            

Listing 144: Komplette parse-Funktion

Dieser Code ist tatsächlich völlig ausreichend, um einen mathematischen UPN-Ausdruck in eine F#-Struktur zu überführen. Was allerdings auffällt ist noch eine gewisse Redundanz in den einzelnen Matching-Fällen. Es tritt immer dasselbe Muster auf: parse (...::stapel') symbole'

Ein solches Muster haben wir bereits kennen gelernt - Es entspricht einer Fold-Funktion aus dem Kapitel über Listenverarbeitung. Dabei summieren wir quasi die Eingabesymbole zu einem Stapel auf.

Wir können also tatsächlich die gesamte Funktion als einen Aufruf von Fold vereinfachen - Die Vorschrift, die wir dabei geben, heißt lediglich: "Wenn wir einen Stapel und ein Eingabesymbol haben, was kommt raus?" Und zwar das:

            
let stapelKombinieren stapel symbol = 
    match symbol, stapel with
    | "+", y::x::stapel' -> (Plus(x, y))::stapel'
    | "-", y::x::stapel' -> (Minus(x, y))::stapel'
    | "*", y::x::stapel' -> (Mal(x, y))::stapel'
    | "/", y::x::stapel' -> (Durch(x, y))::stapel'
    | sym, _            -> match Int32.TryParse(sym) with
                               | (true, i) -> (Zahl(i))::stapel
                               | _         -> (Var(sym))::stapel
            

Listing 145: Vereinfachung mit Fold

Als arbeitsfähiges Gesamtpaket mit Verarbeitung der Eingabe sieht unsere Parser-Funktion also so aus:

            
let parse2 (input : string) = 
    let stapelKombinieren stapel symbol = 
        match symbol, stapel with
        | "+", y::x::stapel' -> (Plus(x, y))::stapel'
        | "-", y::x::stapel' -> (Minus(x, y))::stapel'
        | "*", y::x::stapel' -> (Mal(x, y))::stapel'
        | "/", y::x::stapel' -> (Durch(x, y))::stapel'
        | sym, _            -> match Int32.TryParse(sym) with
                                   | (true, i) -> (Zahl(i))::stapel
                                   | _         -> (Var(sym))::stapel

    input.Split [| ' ' |] |> Array.fold stapelKombinieren [] |> List.hd
            

Listing 146: Vereinfachte parse-Funktion

Mit den generierten Term-Objekten kann man jetzt vielerlei Berechnungen durchführen, sie z.B. optimieren, vereinfachen, ableiten oder einfach nur schreiben.

Als Beispiel zeige ich hier ein kleines Programm, das einen solchen Ausdruck wieder als Infix-Term schreibt:

            
let rec alsInfix = function
    | Zahl(n) -> sprintf "%i" n
    | Var(sym) -> sprintf "%s" sym
    | Plus(a, b) -> sprintf "%s + %s" (alsInfix a) (alsInfix b)
    | Minus(a, b) -> sprintf "%s - %s" (alsInfix a) (alsInfix b)
    | Mal(a, b) -> sprintf "%s * %s" (klammern a) (klammern b)
    | Durch(a, b) -> sprintf "%s / %s" (klammern a) (klammern b)
and klammern expr =
   match expr with
   | Plus(_) | Minus(_) -> sprintf "(%s)" (alsInfix expr) 
   | _ -> alsInfix expr

printf "Geben sie einen UPN-Ausdruck an: "
let upn = Console.ReadLine()
let term = parse2 upn
printfn "Term in Infix-Notation: %s" (alsInfix term)
            

Listing 147: Rückweg von Postfix- zu Infix-Notation

Objektorientierung  

Bis hierher haben wir viele interessante Konzepte kennengelernt, doch eines, das für einen Großteil der heute populären Programmiersprachen zentral ist, fehlt noch: Die Objektorientierung .

Objektorientiertes Programmieren ist, wie funktionales auch, ein Ansatz, um Programme sinnvoll zu gestalten und dem Programmierer so das Leben leichter zu machen. Die Idee dahinter ist, Klassen von Objekten zu erstellen, die über bestimmte Eigenschaften und Fähigkeiten verfügen und aus denen dann konkrete Objekte (Instanzen) erstellt werden können, die wiederum miteinander wechselwirken. So werden Daten und Quellcode in sinnvolle, wiederverwendbare Einheiten gruppiert.

Beispiel: Ein Auto. Ein Auto hat verschiedene Eigenschaften, wie eine Farbe, einen Hersteller, ein Kennzeichen, seine Fahrtgeschwindigkeit und verschiedene Fähigkeiten, z.B. Anfahren oder Bremsen. Aus dieser Vorschrift heraus kann man nun "konkrete" Autos erstellen und im Programm fahren lassen.

Die Vorteile der Objektorientierung bestehen in der anschaulichen, oft wirklichkeitsnahen Darstellung von Zusammenhängen. Zudem beugt es Fehlern vor, da in einer Klasse Programmcode gekapselt, also vor dem Programmierer verborgen wird. Bildlich gesprochen: Ich kann ein Auto fahren, ohne wissen zu müssen, wie ein Motor exakt funktioniert und ohne dort Schaden anrichten zu können - der Motor ist vor dem Fahrer verborgen.

Die .NET-Umgebung, auf der F# aufbaut, ist stark objektorientiert - letztendlich ist sogar alles, womit gearbeitet wird, Listen, Zahlen oder Funktionen ein Objekt. Dem kann sich auch F# nicht entziehen und stellt zusätzlich zu seinen funktionalen Fähigkeiten auch objektorientierte bereit. Beide Paradigmen haben Vorteile und Nachteile, Gemeinsamkeiten und Differenzen. Allgemein lässt sich sagen, dass es sehr problemabhängig ist, ob nun funktionale oder OO-Ansätze besser geeignet sind.

Bis jetzt und ein bisschen weiter

Daten in sinnvolle Einheiten gruppieren...

Das können wir doch schon:

• Records
• Tupel
• Discriminated unions

Tatsächlich handelt es sich hier um sehr einfache Klassen, gemacht um Daten zu speichern.

Ein Beispiel zur Erinnerung:

            
type Punkt = { x : float; y : float }
type Linie = { von : Punkt; bis : Punkt }

let linie  = { von = { x = 1.0; y = 2.5 }; bis = { x = 4.0; y = 5.5 } }
            

Listing 148: Typdeklarationen als eine Art von Klassen

Und wenn wir nun die Länge einer Linie bestimmen wollen? Kein Problem - Eine Funktion muss her.

            
let länge li = ((li.von.x - li.bis.x)**2.0 + (li.von.y - li.bis.y)**2.0)**0.5
printfn "Länge: %f" (länge linie)
            

Listing 149: Funktion zur Bearbeitung der Daten einer Klasse

Der objektorientierte Ansatz wäre hier allerdings ein anderer. Man würde sagen, die Länge ist eine Eigenschaft des Objekts Linie, ein Element (member) dieses Typs. Das lässt sich in F# ebenfalls notieren.

            
type Linie = { von : Punkt; bis : Punkt }
     with
         member this.Länge = ((this.von.x - this.bis.x)**2.0 + (this.von.y - this.bis.y)**2.0)**0.5
            

Listing 150: member in F#

member fügt dem Typ ein neues Element hinzu - In diesem Fall die Eigenschaft Länge. Man kann sich member als das Pendant zu let auf Klassenebene vorstellen, Funktionen und Werte funktionieren wiederum auf gleiche Art. Einziger Unterschied ist das this, man kann es sich als den Stellvertreter der Instanz vorstellen, für die die Funktion aufgerufen wird. Man kann statt dessen auch andere Namen verwenden.

Anwendung:

            
printfn "Länge: %f" Linie.Länge
            

Listing 151: Datenzugriff im Objekt mittels member-Wert

Voilà - Die neue Eigenschaft/Funktion kann einfach per Punkt angesprochen werden.

Das ganze Verfahren ist bei Discriminated Unions nicht verschieden.

            
type 'a Berechnung = 
    | Ergebnis of 'a
    | Fehler
    with
        member private this.Fehlgeschlagen =
            match this with
            | Fehler -> true
            | _ -> false

        member this.Ausruf fehlermeldung = 
            if this.Fehlgeschlagen
                then printfn "%s!" fehlermeldung
                else printfn "Juhu"  


let geradeZahl n = if n % 2 = 0 then Ergebnis n else Fehler

for zahl in [13; 42] do (geradeZahl zahl).Ausruf "Nein"
            

Listing 152: Objektorientierung bei discriminated unions

In diesem Beispiel wurden dem Typen Berechnung gleich zwei Member hinzugefügt - Der eine ist nun eine Funktion vom Typ string -> unit und Fehlgeschlagen eine Eigenschaft vom Typ bool, die bestimmt, ob die Berechnung fehlgeschlagen ist. Bemerkenswert ist, dass durch member private letztere als privat gekennzeichnet wurde. Das bedeutet, die Eigenschaft ist nur innerhalb des Objekts sichtbar, also in diesem Fall nur für Ausruf. Von außen kann die Eigenschaft nicht abgefragt werden.

Erste Klasse

Bis jetzt haben wir die F#-Strukturen wie Records oder Discriminated Unions um weitere objektorientierte Merkmale bereichert. Was jetzt folgt, setzt noch einen Schritt tiefer an: Wir schreiben unsere erste eigenständige F#-Klasse.

Als Beispiel verwenden wir hier ein Auto. Als Eigenschaften bekommt es eine Maximalgeschwindigkeit und eine Modellbezeichnung.

            
type Auto(bezeichnung : string, vmax : int) = 
    member this.VMax        = vmax
    member this.Bezeichnung = bezeichnung

    member this.InfosAnzeigen() = 
        printfn "Ich bin ein %s und kann %i km/h schnell fahren" bezeichnung vmax
            

Listing 153: Auto-Klasse in F#

So, nehmen wir das Beispiel schrittweise auseinander:

Es wird hier offensichtlich ein neuer Typ (eine Klasse) namens Auto beschrieben. Dieser verfügt über zwei öffentliche Eigenschaften - VMax und Modell - sowie eine Methode (Funktion) namens InfosAnzeigen, die die entsprechenden Daten des Autos auf der Konsole ausgibt.

Aber was bedeutet die Zeile type Auto(bezeichnung : string, vmax : int) nun genau? Modell und vmax sind hier sog. Konstruktorargumente. Wenn später eine Auto-Instanz erzeugt wird, übergeben wir dieser direkt jene beiden Werte. Sie sind nur innerhalb der Klasse sichtbar.

Das geht so:

            
let porsche = new Auto("Porsche", 330)
let truck   = new Auto("Vierzigtonner", 80)
            

Listing 154: Auto-Instanz erzeugen

Diese beiden Objekte können wir nun verwenden.

            
for auto in [ porsche; truck ] do
    auto.InfosAnzeigen()
            

Listing 155: Methodenaufruf der Auto-Objekte

Große Klasse

Die F#-Klassensyntax erlaubt alles, was mit Klassen in VB oder C# auch machbar ist. Von lokalen Variablen über Eigenschaften bis hin zu Methoden und gekapselten Werten.

Language-Oriented Programming  

Herzlichen Glückwunsch - Mit den grundlegenden Kapiteln sind sie an dieser Stelle durch. Womit es im Folgenden weiter geht, sind Konzepte des sog. Language-Oriented Programming (LOP).

Damit bezeichnet man zusammenfassend die Möglichkeiten, in einer Sprache "an dieser Sprache" zu programmieren. Und gerade hier ist man mit F# wegen seiner hohen Flexibilität sehr effizient in der Lage, diese Sprache seinen aktuellen Bedürfnissen anzupassen, um direkter und meist einfacher an einem Problem formulieren zu können. (Anmerkung: Bei den folgenden Kapiteln werde ich mich oft am englischsprachigen F#-Wikibook orientieren)

Operatordefinition

Schon in VB ist es möglich, bestimmte Operatoren wie +, -, * oder / für eigene Klassen zu überladen.

Dim x = -SomeVector * New Vector(-1, 3) * New Vector(0, 2) + Vector2

Listing 156: Operatorüberladung in VB.NET

F# geht hier noch einen Schritt weiter: Es ist möglich, völlig neue, eigene Operatoren aus Sonderzeichen zu erschaffen. Ein Operator unterscheidet sich sonst kaum von einer herkömmlichen Funktion. Betrachten wir die Fakultätsfunktion:

            
let (!) n = seq {1..n} |> Seq.fold ( * ) 1

printfn "6! = %i" !6
            

Listing 157: Fakultätsfunktion in F#

Für Infixoperatoren (Operatoren zwischen 2 Operanden - a + b) ist das Konzept gleich:

            
let (@@) x y = 10 * x + y

let res = 2 @@ 3
printfn "%i" res
            

Listing 158: Eigene Infixoperatoren

Wenngleich sich bei diesem Beispiel über die Sinnhaftigkeit gestritten werden kann, sind solche Operatoren z.T. Doch sehr nützlich! Im Folgenden wird eine neue Syntax für optisch ansprechende Abfragen mit Regulären Ausdrucken eingeführt:

            
open System
open System.Text.RegularExpressions

let (=~) text pattern = (new Regex(pattern)).IsMatch(text)

printf "Geben sie eine dreistellige Zahl ein: "

if Console.ReadLine() =~ "\d{3}" then printfn "Danke"
else printfn "Falsche Eingabe"
            

Listing 159: Perl-mässige Verarbeitung von Regex

Weiterhin sehen wir hier etwas, was auf viele Bereiche von F# zutrifft: F# besteht aus F#! Viele "eingebaute" Sprachelemente sind nichts weiter als normale Funktionen und Typen, wie man sie selbst formulieren kann:

            
let (|>) x f = f x

1 |> printf "i: %i"
            

Listing 160: Pipe-Operator selbstgemacht

Sogar das ganze System der Referenzzellen ist rein durch Benutzertypen- und Operatoren definiert:

            
type 'a ref = { mutable contents : 'a }

let ref  x   = { contents = x }
let (:=) p v = p.contents <- v
let (!)  p   = p.contents
            

Listing 161: Eigene Referenzzellen

Maßeinheiten

In F# kann man, Wissenschaftler wird's freuen, endlich Werten eine Maßeinheit mitgeben. Unmittelbarer Nutzen hiervon ist, dass immer klar ist, was für Werte man vorliegen hat und dass v.A. Fehler (Äpfel mit Birnen vergleichen) vom Compiler als solche erkannt werden.

Wir können Einheiten als leere Typen definieren, die mit dem Measure-Attribut versehen sind:

            
[<Measure>] type m
[<Measure>] type s    
[<Measure>] type kg
            

Listing 162: [<Measure>] für Masseinheiten

Auch können wir Typsynonyme einrichten:

[<Measure>] type N = kg * m / s ^ 2

Listing 163: Typsynonyme für zusammengesetzte Masseinheiten

Wenn wir nun einheitenbehaftete Werte notieren, hängen wir die gewünschte Einheit in spitzen Klammern an - Alle Operationen verhalten sich wie intuitiv zu erwarten.

            
let g     = 9.81<m/s^2>
let masse = 1.0<kg>
let kraft = masse * g

let kraft2 = 10.0<N>
let deltaF = kraft2 - kraft
            

Listing 164: Rechnen mit Masseinheiten

Der Compiler kann dabei die verwendeten Typen automatisch prüfen und ggf. ableiten, so dass für kraft und deltaF korrektermaßen die Einheit Newton angenommen wird.

Der Code

let delta = kraft2 - masse

Listing 165: Ungültige Berechnung mit Masseinheiten

schlägt bereits beim Kompilieren fehl - Einheiten inkompatibel!

Bei Funktionen verhält sich das Ganze nicht anders:

let fallzeit höhe : float<s> = sqrt (höhe / (0.5 * g))

Listing 166: Typinferenz auch mit Einheiten

Mit der Angabe, die Fallzeit solle in Sekunden angegeben sein, kann F# den Parameter höhe automatisch auf Meter inferieren.

            
printfn "%A" (fallzeit 10.0<m>)
printfn "%A" (fallzeit 20.3<kg>) // Fehler! Inkompatible Einheiten
            

Listing 167: Korrekte und inkorrekte Berechnung einer Fallzeit

Um zwischen Einheiten umzurechnen, muss lediglich mit den Umrechnungsfaktoren multipliziert werden.

In der Fsharp.Powerpack.dll werden die gängigen SI-Einheiten und physikalischen Konstanten bereits definiert!

Aktive Muster

Wie der Name schon vermuten lässt, sind Aktive Muster (Active Patterns) eine Möglichkeit, mit der wir benutzerdefiniertes, aktives Verhalten in Mustervergleichen definieren können. Sie sind nichts Fundamentales und doch oft eine große Hilfe, wenn es darum geht, Strukturen von Daten sehr kompakt zu verarbeiten oder zu vergleichen.

Einfache Muster

Zu erkennen definieren sind sie leicht - Aber ein Beispiel sagt mehr als tausend Worte:

            
let (|Gerade|Ungerade|) x = 
    if x % 2 = 0
      then Gerade
      else Ungerade

printf "Geben sie eine Zahl ein: "
match int (Console.ReadLine()) with
| Gerade   -> printfn "Die Zahl ist gerade"
| Ungerade -> printfn "Die Zahl ist ungerade"
            

Listing 168: Active patterns

Das oben stehende dünkt einen nicht sonderlich kompliziert, sein Effekt ist unmittelbar ersichtlich. Das aktive Muster wird durch eine Funktion in den Banana-Brackets (||) repräsentiert. Dabei werden hier sozusagen zwei anonyme Fälle einer Discriminated Union generiert - Gerade und Ungerade. Beim Auswerten des Pattern-Matchings wird die Funktion ausgewertet und zu dem Fall verzweigt, den diese zurückgibt - Fertig.

Eine weitere gern genommene Verwendungsmöglichkeit aktiver Muster ist das elegante Zerlegen von Datenstrukturen, die normales Pattern-Matching nicht erlauben. Typisch hierfür sind z.B. Sequenzen. Zwar existieren hier viele integrierte Hilfsfunktionen und die sehr hilfreiche Notation der Sequence-comprehensions, aber trotzdem ist, anders als bei Listen, die manuelle Verarbeitung nur mit einiger Kenntnis des .NET-Frameworks und relativ unschönen, nicht-funktionalen Schleifenkonstrukten möglich. Abhilfe schaffen aktive Muster:

            
let (|Leer|Knoten|) sequenz = 
    if Seq.isEmpty sequenz
        then Leer
        else Knoten (Seq.hd sequenz, Seq.skip 1 sequenz)

let rec seqSumme = function
    | Leer -> 0
    | Knoten(x, xs) -> x + seqSumme xs
            

Listing 169: Sequenzzerlegung mit aktiven Mustern

Einziger Unterschied zum vorherigen Muster ist, dass der Fall Knoten einen Wert in Form eines 2-Tupels zurückgibt.

Partielle Muster

Die nächste Variante ist schon zu mehr fähig. Es handelt sich um partielle Muster, also solche, die fehlschlagen können und dabei Werte transportieren. Beim Mustervergleich werden die angegebenen Fälle so lange ausgewertet, bis einer Some(wert) zurückgibt.

Folgendes Beispiel zeigt einen eleganten Weg, Daten zu interpretieren und zu konvertieren.

            
let (|Zahl|_|) eingabe =
    match Int32.TryParse eingabe with
    | true, res -> Some(res)
    | _         -> None

let (|Kommazahl|_|) eingabe =
    match Double.TryParse eingabe with
    | true, res -> Some(res)
    | _         -> None

printf "Geben sie etwas ein: "
match Console.ReadLine() with
| Zahl n      -> printfn "Zahl: %i" n
| Kommazahl x -> printfn "Kommazahl: %f" x
| str         -> printfn "<unbekannt>: \"%s\"" str
            

Listing 170: Dateninterpretation mittels aktiven Mustern

Viel Neues ist auch hier nicht dazugekommen - Der Tiefstrich in der Funktionsdefinition symbolisiert die Partialität des Vergleichs, der Typ der Funktion ist immer ein Option-Value.

Interessant ist es dabei auch, die Muster als Spezifikationen für Funktionsargumente zu betrachten.

            
let (|NichtNull|_|) x = 
    if x <> 0
      then Some(x)
      else None

let teilen a (NichtNull b) = a / b

printfn "%A" (teilen 1 2)
printfn "%A" (teilen 2 0)
            

Listing 171: Aktive Muster als Spezifikation für Funktionsargumente

Der zweite Fall wird mit einer MatchFailureException abbrechen, da der 2. Funktionsparameter die Bedingung, er solle nicht 0 sein, nicht erfüllt.

Die Möglichkeit, Muster ineinander zu kombinieren, lässt extrem mächtige Ausdrücke zu.

Folgender Ausdruck kann einen Eingabestring gegen einen regulären Ausdruck prüfen und gibt im Erfolgsfall die angegebenen Gruppen als Liste zurück.

            
let (|RegMatch|_|) (grps : int list) regex eingabe =
    let treffer = Regex.Match(eingabe, regex)
    if not treffer.Success 
      then None
      else 
         let res = [| for g in treffer.Groups -> g.Value |]
         Some([ for i in grps -> res.[i] ])
            

Listing 172: Regex mit aktivem Muster anwenden

Mit den bereits vorhandenen Funktionen kombinieren wir dies zu einer Funktion, die einen String als Angabe von 2D-Koordinaten interpretieren soll, wobei beide Koordinaten ganzzahlig und ungleich 0 sein sollen!

            
let punkt = function
  | RegMatch [1;2] "\((.+?), (.+?)\)" [Zahl(NichtNull x); Zahl(NichtNull y)] -> (x, y)
  | _ -> failwith "Falsches Format"
            

Listing 173: 2D-Koordinaten parsen

Hier wird die vom ersten Muster ausgegebene Ergebnissequenz von weiteren immer mehr zerlegt.

            
printfn "%A" (punkt "(1, 2)")
printfn "%A" (punkt "(1, 0)")
printfn "%A" (punkt "foo")
            

Listing 174: Aufruf des Koordinatenparsers

Logischerweise wird also der erste Aufruf korrekt funktionieren, die beiden anderen aber mit Fehler abbrechen, da eben das spezifizierte Muster nicht erfüllt ist.

Computation Expressions  

Willkommen zu den sog. Computation Expressions. Diese sind zweifellos ein Highlight von F# und machen es unter den Programmiersprachen vielleicht nicht einzigartig, aber auf jeden Fall besonders.

Eine Computation Expression ist eine Verallgemeinerung eines Programmablaufs, den der Programmierer selbst definieren kann. Dabei können in normaler F#-Syntax komplizierte Abläufe automatisch generiert werden.

Einleitendes Beispiel

Ich beginne dieses Kapitel mit einer einfachen Aufgabe: Es gilt eine Funktion zu entwickeln, die den Benutzer auffordert, drei Zahlen a, b und c einzugeben, und deren Summe zurückgibt. Da der Benutzer Fehler machen kann, verwenden wir Option-Typen.

Geschafft?

Das Ergebnis wird vielleicht so aussehen:

            
let zahlEingeben id =
    printf "%s: " id
    match Int32.TryParse (Console.ReadLine()) with
    | true, res -> Some(res)
    | _         -> None

let summe() =
    let a = zahlEingeben "a"
    let b = zahlEingeben "b"
    let c = zahlEingeben "c"
    match a, b, c with
    | Some(x), Some(y), Some(z) -> Some(x + y + z)
    | _ -> None
            

Listing 175: Zahleneingabe und Auswertung wie gehabt

Sieht richtig aus, funktioniert auch. Es gibt nur ein Problem: Man betrachte folgende Eingabe:

          
A: xyz
B: 10
C: 12
            

Hmm, da hat doch der Benutzer schon beim ersten Wert etwas Ungültiges eingegeben, und trotzdem geht die Abfrage weiter. Eigentlich ist doch klar: Das kann gar nichts mehr werden, an dieser Stelle müsste eigentlich Schluss sein! Aber gut, ich habe Sie vermutlich unterschätzt ;) Also ab zur richtigen Funktion:

            
let summe() =
    match zahlEingeben "a" with
    | None -> None
    | Some(a) ->
      match zahlEingeben "b" with
      | None -> None
      | Some(b) ->
        match zahlEingeben "c" with
        | None -> None
        | Some(c) -> Some(a + b + c)
            

Listing 176: Zahleingabe mit schrittweiser Ergebnisprüfung

Bitte was? ZEHN Zeilen für eine so triviale Aufgabe? Die Frage ist berechtigt und im Weiteren geht es darum, wie man diesen Code vereinfachen könnte.

Der obige Code enthält zahlreiche Redundanzen und wie gewöhnlich könnten wir versuchen, den oft verwendeten Code als Funktion auszulagern.

Und hier kommt eine schlagende Idee ins Spiel: Wir definieren eine Funktion namens bind und teilen die Berechnung in einen aktuellen Stand und den Rest der Berechnung auf:

1. Wenn der Benutzer einen gültigen Wert eingibt, führen wir mit diesem Wert die Berechnung fort
2. Wenn der Benutzer einen Fehler macht, ist Schluss; der Rest der Berechnung wird einfach gar nicht fortgesetzt.

Aber wie geben wir "den Rest einer Berechnung" an? Klar: Als Funktion. Et voilà:

            
let bind eingabe rest = 
    match eingabe with
    | Some(ergebnis) -> rest(ergebnis) // Gültig - Rest berechnen 
    | None           -> None           // Ungültig - Tschüss
            

Listing 177: 'Rest der Berechnung' als Funktion

Der Typ ist hierbei

val bind : 'a option -> ('a -> 'b option) -> 'b option

Listing 178: Typsignatur von bind

Mithilfe dieser unscheinbaren Funktion können wir unsere Summenfunktion signifikant vereinfachen:

            
let summe() = 
    bind (zahlEingeben "a") (fun a ->
        bind (zahlEingeben "b") (fun b ->
            bind (zahlEingeben "c") (fun c -> Some(a + b + c))))
            

Listing 179: Einfache Zahleneingabe

Diese Art von Funktionsauswertung, bei der der Rest einer Berechnung als Funktion mitübergeben wird, nennt sich Continuation-passing style (CPS).

Computation Expressions definieren

Verallgemeinert man das Konzept, das wir gerade angewendet haben, so spricht man von sog. Monaden. Vor Monaden haben viele Programmier Angst, denn sie werden oftmals als sehr kompliziert und theoretisch empfunden, aber letzendlich sind sie nur eines: Extrem nützlich.

Dabei ist bei Allem nämlich nichts anderes gemeint, als dass wir für einen Typen zwei Funktionen definiert haben: Die eine ist Bind (oder auch >>=) und tut genau das wie im obigen Beispiel - Einen Wert auf bestimmte Weise mit dem Rest einer Berechnung verknüpfen. Die andere ist Return und dient lediglich dazu, ein Ergebnis zurückzugeben. Für die Option-Typen ist auch Return offensichtlich - Es handelt sich um den Konstruktor Some, denn dieser gibt ja einen (Erfolgs-)Wert zurück.

Hiermit ist auch geklärt, was Computation Expressions eigentlich sind: Monadische Berechnungen

Jetzt geht es nur noch darum, so eine auch zu definieren. Um anzugeben, woher die entsprechenden Funktion (Bind etc.) genommen werden sollen, sieht F# ein sog. Builder-Objekt vor, für das wir eine Klasse schreiben:

            
type MaybeBuilder() = 
    member this.Delay(f)   = f()
    member this.Bind(x, f) = bind x f
    member this.Return(x)  = Some(x)
            

Listing 180: Builder-Klasse

Wie wir sehen, definiert das genau die obigen Funktionen - Bind und Return (und Delay, das werden wir aber vernachlässigen).

Von diesem können wir jetzt eine Instanz erstellen

let maybe = new MaybeBuilder()

Listing 181: Builder-Objekt

und schon sehen die Dinge so aus:

            
let summe() = maybe {
    let! a = zahlEingeben "a"
    let! b = zahlEingeben "b"
    let! c = zahlEingeben "c"
    return a + b + c 
}
            

Listing 182: Zahleneingabe und Summenbildung

Perfekt - Einfacher geht's nicht!

Und so einen Ausdruck nennt man jetzt eben Computation Expression. Die Aufrufe von Bind werden nun vom Compiler automatisch eingesetzt, und zwar immer an den Zuweisungen mit let!.

Weitere Computation Expressions

Aufmerksamen Lesern wird die Funktion, die wir oben geschrieben haben, merkwürdig bekannt vorkommen. Richtig... es existiert doch so eine Syntax mit seq { ... }.

Seq ist tatsächlich der wohl berühmteste Vertreter von Computation Expressions - Er arbeitet nicht mit Option-Werten, sondern mit Listen. Aber nichtsdestotrotz handelt es sich um nichts Anderes als oben, der Zweck ist nur ein anderer. Hier sieht man die außerordentliche Vielfalt von monadischen Berechnungen. F# erlaubt uns nämlich neben der Definition von Bind und Return auch noch, Implementierungen für Kontrollstrukturen zu schreiben - Das bedeutet, innerhalb dieser Blöcke kann man den gesamten F#-Code schrittweise auseinandernehmen und mit "Spezialeffekten aufgerüstet" wieder ins Rennen schicken.

Beweis: Für List-Comprehensions kann ebenso simpel eine Computation Expression definiert werden:

type ListComprehension() = 
    member this.Delay(f)       = f()
    member this.Return(x)      = [x]
    member this.Bind(liste, f) = List.concat [ for x in liste -> f x ]

let list = new ListComprehension()

let punkte = list {
    let! x = [1..3]
    let! y = [1..3]
    return (x, y)
}

printfn "%A" punkte // [(1, 1); (1, 2); (1, 3); (2, 1); (2, 2); (2, 3); (3, 1); (3, 2); (3, 3)]

Listing 183: Statt List-Comprehensions eine Computation Expression

Aber genug theoretisch geredet - Folgende Liste gibt eine Reihe von Operationen an, die monadischen Gesetzen folgen und daher durch Computation Expressions beschreibbar sind:

1. Option-Werte
2. List-Comprehensions
3. Sichere Ein- und Ausgaben
4. Asynchrone Programmabläufe (Multithreading)
5. Transaktionen
6. Continuations (Einfrieren und Speichern von Zeitpunkten in Programmen)
7. Backtracking (Fehlerrückverfolgung)
8. Pseudozufallsgeneratoren
9. Zustandsänderungen / State machines
10. Stochastische Prozesse (Zufallsmodelle)
11. Parser (Texte von Programmen verarbeiten lassen)
12. Interpreter für Programmiersprachen

Mit Computation Expressions lässt sich also auf einer Vielzahl von Objekten operieren. Dabei handelt es sich immer um generische Typen ('a option, 'a list, 'a async, ...). Verallgemeinert nennen wir diesen Typen 'a M und erhalten folgende Signaturen für ein Builder-Objekt.

val Bind   : 'a M * ('a -> 'b M) -> 'b M
val Return : 'a -> 'a M

Listing 184: Typsignaturen von Bind und Return

Pseudozufallsgeneratoren

Zufallsgeneratoren und funktionale Programmierung hatten schon immer eine schwierige Beziehung. Zumeist werden sie, zusammen mit Ein/Ausgaben, von Anfängern oder Gegnern als das Argument gezückt, aufgrund dessen funktionale Programmierung nicht funktionieren könne. Um das spektakuläre Gegenteil zu beweisen, v.A. aber, um einmal die Entwicklung einer Computation Expression vollständig durchzuexerzieren, werden wir nun schrittweise eine vollständig funktionale Zufalls-Monade entwickeln.

Dazu ist ersteinmal wichtig, die Funktionsweise handelsüblicher Zufallsgeneratoren zu verstehen. Normalerweise hält ein jeder Zufallsgenerator einen bestimmten gespeicherten Wert und eine Rechenvorschrift. Ganz am Anfang seiner Existenz wird er mit einem sog. Seed, einem Anfangswert, initialisiert. Bei jeder Anfrage für eine Zufallszahl berechnet er nun aus diesem Seed mithilfe einer hochkomplexen Rechenvorschrift eine Zufallszahl aus. Gleichzeitig kommt er damit auf einen neuen Seed-Wert, der ihn bei der nächsten Berechnung als Ausgangswert dient. (Übrigens: Bei gleichen Startwerten produziert jeder Zufallsgenerator auch die gleiche Zufallsfolge!)

In Ordnung - Das klingt jetzt, von der komplizierten Formel abgesehen, nach nichts, was nicht in ein paar Zeilen machbar ist:

            
type Random(seed : int) =
    let mutable value = seed

    member this.Next(min, max) =
        value <- komplizierteFormel value
        min + value % (max - min)
            

Listing 185: Einfacher Zufallsgenerator in F#

Tjaaaha, freut sich unser Widersacher und das schlechte Gewissen sieht, was er meint (hier zur unmissverständlichen Kenntnis rot hervorgehomben).

type Random(seed : int) =
    let class="redfont">mutable value = seed

    member this.Next(min, max) =
        class="redfont">value <- komplizierteFormel value
        min + value % (max - min)

Listing 186: mutable und Variablenzuweisung

Veränderliche Werte - Schlimmer: Ein globaler Zustand, der sich permantent ändert. Nein, noch schlimmer: Jede Funktion, die den Zufallsgenerator verwendet, ändert einen globalen Zustand. Wenn jetzt noch Multithreading mit ins Spiel käme, hätten wir ein ernstes Problem. In anderen Sprachen ist sowas zwar Gang und Gäbe (ja, auch der System.Random arbeitet so), aber da wir in F# funktional programmieren und genau soetwas vermeiden wollen, muss einfach eine andere Lösung her.

Und die gibt es - Völlig frei von Veränderlichem und mit einer perfekten, durchs Typsystem getragenen Unterscheidung von zufälligem und "normalem" Code. Aber wo kommt diese her?

Gewieftermaßen reicht hier die Kapitelüberschrift zur Antwort: Computation Expressions

Betrachten wir mal den Zufallsgenerator von allen Zustanden gelöst - Was wollen wir haben? Ein Objekt, das, wenn es einen Anfangswert bekommt, einen Zufallswert und einen neuen Anfangswert produziert!

Das zumindest ist problemlos funktional:

type 'a Random = Random of (int -> 'a * int)

Listing 187: Hülle des Zufallsgenerators

Logisch - Ein Objekt, das einen Startwert (eine Zahl) bekommt und ein zufälliges Ergebnis plus den nächsten Startwert produziert... So weit waren wir.

Ein Zufallsobjekt, das aus einem angegebenen Intervall einen Zufallswert erstellt, können wir auch angeben:

            
let choose (min, max) =
     Random (fun seed -> (min + seed % (max - min)          (* Zufallswert *), 
                          abs(327 * seed - 403471) % 37231) (* Neuer Startwert *) )
            

Listing 188: Berechnung der Zufallszahlen an sich

(Die Formeln sind geraten und natürlich nicht auf dem neusten Stand der Dinge - Es geht mehr ums Prinzip).

Um das Schreiben noch etwas einfacher zu gestalten, erhält unser Generatorobjekt noch eine Memberfunktion:

            
type 'a Random = Random of (int -> 'a * int)
    with 
        member this.Gen seed = let (Random f) = this in fst (f seed)
            

Listing 189: Memberfunktion für Random

Mittels der Gen-Funktion können wir bei gegebenem Anfangswert nun einfach das Ergebnis ausgeben lassen.

Jetzt können wir beginnen, Zufallsfolgen zu berechnen.

            
let generator = choose (1, 10)

printfn "%i" (generator.Gen 42)
printfn "%i" (generator.Gen 42)
printfn "%i" (generator.Gen 42)
            

Listing 190: Verwendung von choose

Wundervoll - Wir erhalten drei mal die Ausgabe 7. Sehr zufällig ist das aber nicht - aber bekanntlich ändern sich ja auch keine Werte. Aber halt, wir wissen ja, dass der Generator noch einen neuen Startwert ausspuckt. Den können wir ja einfach weitergeben.

            
let (Random generator) = choose (1, 10)

let startwert1 = 42

let (ergebnis1, startwert2) = generator startwert1
printfn "%i" ergebnis1

let (ergebnis2, startwert3) = generator startwert2
printfn "%i" ergebnis2

let (ergebnis3, startwert4) = generator startwert3
printfn "%i" ergebnis3
            

Listing 191: Manuelle Weitergabe des neuen Startwerts

7, 4, 5 - Das lass ich glatt als Zufallsfolge gelten!

Jetzt geht es einzig darum, das Weitergeben der Startwerte irgendwie vor dem Programmierer zu verbergen. Und genau hier kommt wieder die Bind-Funktion ins Spiel.

            
let bind (Random gen) (next : 'a -> 'b Random) =
    Random (fun seed ->
                let (res, seed2)  = gen seed
                let (Random gen2) = next res
                gen2 seed2)
            

Listing 192: Automatisierung der Startwert-Weitergabe mit bind

Der neue Zufallsgenerator setzt einen gegebenen Startwert in den ersten ein, verarbeitet dessen Ergebnis und macht mit dem neu gelieferten Wert weiter. Damit wird aus unserem Beispiel Folgendes:

            
let generator = choose (1, 10)

let startwert1 = 42

(bind generator (fun ergebnis1 ->
    printfn "%i" ergebnis1
    bind generator (fun ergebnis2 ->
        printfn "%i" ergebnis2
        bind generator (fun ergebnis3 ->
            printfn "%i" ergebnis3
            Random (fun x -> ((), x)))))).Gen startwert1
            

Listing 193: Neues Beispiel mit automatisierter Weitergabe

Super - Zumindest müssen wir keine Werte mehr per Hand herumtragen, bind hält sie schön von uns fern. Damit wir die längst überfällige Computation Expression endlich definieren können, fehlt nur noch eine sinnvolle Implementierung von Return.

Sprich: Ein Generator, der einen Wert x zurückgeben soll, tut dies für jede Eingabe!

Damit lautet das Builder-Objekt so:

            
type RandomBuilder() = 
    member this.Delay(f) = f()
    member this.Return(x) = Random (fun seed -> (x, seed))
    member this.Bind(Random gen, next) = Random (fun seed ->
                                                    let (res, seed2)  = gen seed
                                                    let (Random gen2) = next res
                                                    gen2 seed2)
            

Listing 194: RandomBuilder-Klasse

Hiermit ist es uns also möglich, zufallsabhängigen Code völlig imperativ aussehend zu schreiben. Dennoch kann dieser außerhalb eines Random-Objektes nicht existieren und ist daher perfekt von jeglichem nicht-zufälligen Code getrennt - Seiteneffekte und Wertänderungen haben wir an keiner Stelle! Das war's.

            
let random = new RandomBuilder()

let demo = random {
    let! a = choose (1, 10)
    printfn "%i" a

    let! b = choose (1, 10)
    printfn "%i" b

    let! c = choose (1, 10)
    printfn "%i" c

    return ()
}

demo.Gen 42
            

Listing 195: Anwendung des neuen Zufallsgenerators

Dabei gilt:

val demo : unit Random

Listing 196: Typsignatur des Random-Demos

Hier noch ein Beispiel, das verschiedenste Generatoren kombiniert:

            
let zufallsPunkt = random {
    let! x = choose (-5, 5)
    let! y = choose (-10, 10)

    return (x, y)
}

let rec zufallsSequenz bereich = function
    | 0 -> random { return [] }
    | k -> random {
               let! wert = choose bereich
               let! rest = zufallsSequenz bereich (k - 1)
               return wert::rest 
           }

let zufallsWort =
    let buchstaben = [|'A' .. 'z'|]
    fun länge -> random {
        let! ascii = zufallsSequenz (0, buchstaben.Length) länge
        return new String(ascii |> List.map (fun i -> buchstaben.[i]) |> List.to_array)
    }

let zufallsDemo = random {
    let! länge = choose (5, 10)
    let! liste = zufallsSequenz (1, 100) länge
    printfn "%A" liste

    let! punkt = zufallsPunkt
    printfn "%A" punkt

    printf "Länge des Namens? "
    let  len  = int (Console.ReadLine())
    let! name = zufallsWort len
    printfn "Hallo, %s" name

    return ()
}

zufallsDemo.Gen 42

printfn " ************************* "

zufallsDemo.Gen 1
            

Listing 197: Verschiedenste Zufallsgeneratoren

Asynchrones Programmieren

Aber genug über die Interna von Computation Expressions.

Dieser Abschnitt dreht sich um ein kleines Objekt, das F# von Haus aus definiert und mit wir in der absolut einzigartigen Lage sind, ein sehr kompliziertes Thema über eine Computation Expression abhandeln zu können, ohne auch nur darüber nachdenken zu müssen: Async

Betrachten wir folgende Beispiel: Wir haben eine Berechnung, die potenziell seeehr lange dauert:

            
// val langsameBerechnung : 'a -> 'a
let langsameBerechnung wert = 
    for x in 1..10 do
        printfn "#%A: %i" wert x
        Threading.Thread.Sleep 200 // 200 ms schlafen
    wert
            

Listing 198: Berechnung mit grosser Laufzeit

Wenn wir hiervon ein paar Werte brauchen, ist das kein Problem:

            
let ergebnisse = [ for x in 1..5 -> langsameBerechnung x ]
let summe = List.sum ergebnisse
            

Listing 199: Anwendung der Berechnung

Als Ausgabe bekommen wir fein säuberlich hintereinander:

          
#1: 1
#1: 2
.
.
#1: 10
#2: 1
#2: 2
.
.
#2: 10
#3: 1
.
.
#5: 10
            

Insgesamt müssen wir auf dieses Ergebnis 200ms*10*5=10 Sekunden warten.

Die berechtigte Überlegung ist nun: Wieso berechnen wir die Werte nicht parallel? Keiner von ihnen ändert einen anderen, es sind unabhängige Berechnungen.

Unsere Funktion parallelisierbar zu machen, ist dank Computation Expressions im Schlaf möglich:

            
let langsameBerechnung wert = async {
    for x in 1..10 do
        printfn "#%A: %i" wert x
        Threading.Thread.Sleep 200 // 200 ms schlafen
    return wert
}
            

Listing 200: Langsame Berechnung parallelisiert

Ihre Signatur ändert sich in:

val langsameBerechnung : 'a -> Async<'a>

Listing 201: Typsignatur der parallelisierten Berechnungsfunktion

Das bedeutet, sie gibt ein Async-Objekt zurück, das, wenn es ausgewertet wird, einen Wert vom Typen 'a produziert. Der Trick ist nun, dass wir mit einer weiteren Computation Expression diese Berechnungen bequem kombinieren können.

            
let summe = async {
    let! ergebnisse = [ for x in 1..5 -> langsameBerechnung x ] |> Async.Parallel

    return Array.sum ergebnisse
}
            

Listing 202: Asynchrone Berechnung

Mit Async.Parallel setzen wir eine Liste von asynchronen Berechnungen zu einer neuen zusammen, die die Ergebnisse als Array zusammenfasst.

val Async.Parallel : Async<'a> list -> Async<'a array>

Listing 203: Typsignatur der asynchronen Funktion

Dieses Ergebnis können wir mit der let!-Syntax extrahieren, summieren und zurückgeben. Dabei hat Summe den Typen Async<int>, gibt also eine Berechnung an, die, wenn sie ausgewertet wird, eine Zahl zurückgibt.

Und das tun wir jetzt:

printfn "%i" (Async.RunSynchronously summe)

Listing 204: Aufruf der asynchronen Funktion

Was wir erhalten, sieht nun in etwa so aus:

Dieses Ergebnis zeigt: Die Funktionen werden tatsächlich parallel, d.h. von mehreren Threads, ausgewertet. Und viel wichtiger: Die Rechenzeit ist weit unter 10 Sekunden, da die Funktionen nicht mehr aufeinander warten.

Die Möglichkeit zur parallelen Auswertung gibt es bereits in vielen Programmiersprachen - Der entscheidende Vorteil unserer Async-Ausdrücke ist es allerdings, dass wir jede Art von potenziell asynchroner Berechnung in fast normaler Syntax formulieren können - Seien es asynchrone Internet-, Datei- oder Datenbankzugriffe, Message Passing oder nur eine parallele Auswertung. Mit Thread-Handles oder Callback-Funktionen wie unter VB oder C# müssen wir uns dabei an keiner Stelle herumschlagen - Im let!-Aufruf werden diese vom Compiler automatisch hinzugefügt.

In Kombination mit seiner funktionalen Natur macht dies F# zu einer idealen Multithreading-Sprache. Codes, die in anderen Sprachen Hunderte von Zeilen benötigen und dabei oft fehleranfällig sind, lassen sich mit async {}-Blöcken in wenigen Zeilen, einer völlig offensichtlichen Syntax und mit weitaus geringerem Gefahrenpotenzial notieren. Denn ein weiterer Vorteil ist, dass F# (unbeabsichtigte) Veränderung von Werten unterbindet - An dieser Stelle nämlich krankt viel sonstiger Multithreading-Code, da unkontrolliert auf gemeinsame Werte zugegriffen wird und deren Zustand dadurch Schäden erleidet.

Schlusswort  

So, das war's. Ich hoffe, ich konnte Ihnen einen kleinen Einblick in die doch etwas "andere" Sprache F# geben. Sollten Fragen auftauchen, können Sie diese selbstverständlich in einem unserer Foren stellen.

Quellen  

• F# Programming
• Inside F#

Ihre Meinung  

Falls Sie Fragen zu diesem Tutorial haben oder Ihre Erfahrung mit anderen Nutzern austauschen möchten, dann teilen Sie uns diese bitte in einem der unten vorhandenen Themen oder über einen neuen Beitrag mit. Hierzu können sie einfach einen Beitrag in einem zum Thema passenden Forum anlegen, welcher automatisch mit dieser Seite verknüpft wird.