F# - Funktionales Programmieren unter .NET

Informatik Seminar WS09/10 von Sören Militzer

Seminarthemen WS09/10 :: Einleitung | Grundlagen Funktionaler Programmierung | Datenstrukturen | Imperative Aspekte | Objektorientierte Aspekte

Datenstrukturen

Tupel

Tupel sind die einfachsten Datenstrukturen in F#, können jedoch sehr mächtig werden. Sie sind eine Kombination von mehreren Werten um einen neuen Wert zu formen, dabei kann jeder möglicher Wertetyp verwendet werden, auch Tupel selbst. Tupel können über den folgenden Tupel Ausdruck erzeugt werden (wobei die Klammern optional anzusehen sind):

let Tupel = (Element1, ..., ElementN)

und auch über den gleichen Ausdruck nur in unterschiedlicher Reihenfolge wieder in die einzelnen Bestandteile zerlegt werden:

let Symbol1, ..., SymbolN = Tupel.

Dabei werden die Symbole in der Reihenfolge auf die Werte des Tupels gebunden, wie sie in diesem Ausdruck angegeben worden sind. Mithilfe des Tupel-Ausdrucks können einige pfiffige Dinge realisiert werden wie z.B. das Currying von Funktionen verhindert werden, indem die Parameter einer Funktion einfach durch ein Leerzeichen getrennt und mit runden Klammern zusammengefasst angegeben werden. Technisch gesehen werden die Parameter immer noch als einem Parameter übergeben - dem Tupel - praktisch gesehen wird das Currying verhindert da Tupel nicht partiell definiert werden könnnen.

Let sayHelloTo(greet,thing) =
    printfn "%s %s!" greet thing

val sayHelloTo : string * string -> unit

Weiterhin können durch Tupel mehrere Werte von einer Funktion zurückgegeben werden, indem die Rückgabe der Funktion als Tupel erzeugt wird.

let DoubleAndTriple x =
    2*x,3*x

val DoubleAndTriple : int -> int * int

Typdefinitionen - Typalias

Die einfachste Form in F# einen Typen zu definieren ist mittels eines Typalias.

type PLZ = string
type myFuncParams = int * string

Die somit definierten Typen können frei bei allen expliziten Typenangaben verwendet werden, jedoch wird der Compiler im Zuge der Typinferenz nicht auf diesen Typen zugreifen, wie man im folgenden Beispiel sehen kann.

type myFuncParams = int * string
let myFunc myParams =
    printfn "Int: %i" (fst myParams)
    printfn "String: %s" (snd myParams)

type myFuncParams = int * string
val myFunc = int * string -> unit

Die Typen des Funktionsparameters sowie des Typenalias sind gleich, dennoch ermittelt der Compiler als Typ für den Funktionsparameter nicht den Typenalias. Im Gegensatz zu anderen Sprachen bedeutet Typengleichheit in F# nicht, dass die Namen der Typen gleich lauten müssen, sondern das die tatsächliche Signatur der Typen gleich sein muss, zu sehen im folgenden Beispiel:

let someParam : myFuncParams = 3,"Hallo"

val someParam : myFuncParams = (3, "Hallo")

myFunc someParam
Int: 3
String: Hallo
val it : unit = ()

Die Signaturen der beiden Typen - Funktionsparameter und dem Symbol "someParam" - sind gleich, somit sind die beiden Typen auch gleich.

Als Abschluss zu Typalias sei noch gesagt, dass durch die Definition eines Typalias der Typ nicht konkret dupliziert wird, sondern einfach nur der gleiche Typ unter einen anderen Namen ansprechbar ist. Ein Typalias wird im Zuge des Compile-Prozesses entfernt und die Typen von Symbolen durch den konkreten Typen ersetzt.

Typdefinitionen - Records

Als erste konkrete Typdefinition sind hier die Records zu nennen, die zwar so simpel zu definieren sind wie ein Tupel, jedoch weitaus einfacher zu handhaben sind, da auf die einzelnen Komponenten eines Records einfach per Punkt-Notation zugegriffen werden kann. Hier ein Beispiel für die Definition und die Verwendung eines Records innerhalb einer Funktion:

type Vector2D = { X : float; Y : float; }
let lenVec2D aVec =
    sqrt (aVec.X * aVec.X + aVec.Y * aVec.Y)

val lenVec2D : Vector2D -> float

lenVec2D { X = 1.0; Y = 1.0 }

val it : float = 1.414213562

Im Gegensatz zum Typalias verwendet der Compiler diesen Typ auch in der Typ Inferenz und erkennt das der Parameter der Funktion lenVec2D vom Typ Vector2D sein muss, da kein anderer Typ im akuellen Gültigkeitsraum diese Typsignatur inne hat. Auch muss bei dem Typkonstruktor für den Aufruf der Funktion kein expliziter Typ angegeben werden, da der F# Compiler anhand der Funktionssignatur erkennt das der übergebene Parameter vom Typ Vector2D sein muss.

Da Records konkrete Typen sind, sind diese Typen auch nach Ausserhalb sichtbar, sodass andere .NET Programme auf diese Typen von Ausserhalb zugreifen können. Hier nun der Code, wie die obrige Recorddefinition in C# aussieht und verwendet werden kann.

public sealed class Vector2D : IStructuralEquatable, IComparable, IStructuralComparable
{
    internal double X@;
    internal double Y@;

    public Vector2D(double x, double y);

    public double X { get; }
    public double Y { get; }
}

Typdefinitionen - Discrimnated Unions

Discriminated Unions werden verwendet um einen abgeschlossenen Typenraum mit einer begrenzten Menge von Typen zu definieren, die alle in diesem Typenraum disjunkt zueinander sind. Jeder dieser Typen kann jeweils ein Tupel beinhalten, in dem die Daten für diesen Typ gespeichert werden.

type KartenFarbe = string
type KartenWert = int

type Kartenspiel =
    | NormaleKarte of KartenFarbe * KartenWert
    | Joker

let aPikSieben = NormaleKarte("Pik", 7)
let aJoker = Joker

val aPikSieben : Kartenspiel = NormaleKarte ("Pik", 7)
val aJoker : Kartenspiel = Joker

Jede Alternative in diesem Typenraum wird "Discriminator" genannt. Der Name eines Discriminators ist zugleich auch der Name für einen Konstruktur, anhand dessen ein Wert von diesem Typ erzeugt werden kann. Wie am Beispiel mit dem Joker zu sehen, kann ein Discriminator ein Tupel mit Daten beinhalten, muss aber nicht. Ein Discriminator kann auch rekursive Referenzen auf den eigenen Typenraum bzw. Discriminator beinhalten.

type BoolExpr =
    | SimpleValue of bool
    | AndExpr of BoolExpr * BoolExpr
    | OrExpr of BoolExpr * BoolExpr
    | NegExpr of BoolExpr

Außerdem kann solch ein Typenraum auch generisch definiert sein.

type Tree<'a%gt; =
    | Tree of 'a * Tree<'a> * Tree<'a>
    | Leaf of 'a

Möchte man ein Discrimated Union ausserhalb von F# verwenden, ist dieser Discriminated Union eine abstrakte Basisklasse. Für jeden Discriminator existiert eine versiegelte Klasse, die von dieser Basisklasse erbt und die Daten für den entsprechenden Discriminator beinhaltet.

Listen

Listen sind in F# mit einer der am häufigsten verwendeten Datenstrukturen und sollen deshalb hier ein wenig mehr in der Tiefe beleuchtet werden. Listen werden intern durch einfach verkettete Listen repräsentiert, deren Kettenglieder einen Zeiger zu dem gespeicherten Element sowie einen Zeiger zu dem nächsten Kettenglied speichern. Wenn Listen aneinander angehängt werden, wird eine neue Liste erstellt, die die Verknüpfung von einer Liste zu Nächsten beinhaltet. Durch die Unveränderlichkeit einer Liste sowie dieser Vorgehensweise, wird gewährleistet das Listen keinen unnötigen Speicherplatz verbrauchen wenn viele Operationen auf Listen durchgeführt werden. Jedoch kommt dieses auch mit einem Nachteil, auf die Listenelemente kann nur sequentiell vom ersten bis zum letzten Element zugegriffen werden, die Komplexität des Zugriffs ist hier in der Klasse O(n) mit n der Anzahl der Listenelemente. Daher sind Listen nicht dafür gedacht sehr viele Elemente zu beinhalten, für solche Dinge sind andere Datenstrukturen eher geeignet.

Die Funktionen die Listen kapseln bzw. vom Modul "List" bereitgestellt wird, beinhalten eine Fülle von Funktionen mit denen sehr viele Probleme bewältigt werden können, daher hier eine kurze Auflistung der wichtigsten Funktion für Listen:

Funktion Typ Beschreibung
List.length 'a list -> int Ermittelt zu einer gegebenen Liste die Anzahl der Elemente
List.hd 'a list -> 'a Ermittelt das erste Element einer nichtleeren Liste
List.tl 'a list -> 'a list Ermittelt zu der gegebenen Liste eine Liste die alle Elemente der Ersten enthält, ohne das erste Element
List.init int -> (int -> 'a) -> 'a list Erzeugt eine neue Liste mit einer gegebenen Anzahl von Elementen die durch die gegebene Funktion erzeugt werden können.
List.append 'a list -> 'a list -> 'a list Hängt zwei Listen aneinander
List.iter ('a -> unit) -> 'a list -> unit Führt die gegebene Funktion für alle Elemente der Liste aus
List.map ('a -> 'b) -> 'a list -> 'b list Erzeugt eine neue Liste die durch die gegebene Funktion und der alten Liste
List.filter ('a -> bool) -> 'a list -> 'a list Erzeugt eine neue Liste, die die Elemente der alten Liste enthält, bei denen die Funktion true zurückgibt.

Zusätzlich zu diesen Funktionen kennt F# auch noch Ausdrücke und Operatoren, die für die Arbeit mit Listen wichtig sind:

Ausdruck / Operator Beschreibung Beispiel
[] Leere Liste []
Element :: Liste Hängt das Element an erster Position an die Liste ran 1::[2;3]
[Elem1;...;ElemN] Ein Listenausdruck zum Erzeugen von Listen [1;2;3]
[Zahl1..Zahl2] Ein Reichweiten Ausdruck, mithilfe dessen eine Liste gefüllt mit den Zahl von Zahl1 bis Zahl2 erzeugt werden kann [1..10], [1.0..10.0]
[ for Symbol in Liste -> Ausdruck ] Kurzform für List.map [ for x in [1;2;3] -> x*x ]
Liste1 @ Liste2 Hängt zwei Listen in der gegebenen Reihenfolge aneinander [1;2] @ [3;4]

Pattern Matching

Pattern Matching in F# kann vage mit dem aus den imperative Sprachen vertrauten Konstrukt der Case-Verteiler verglichen werden, bei beiden wird ein Wert gegen mehrere Regeln verglichen. So könnte man über Pattern Matching eine Fibunacci Funktion realisieren.

let rec fib n =
    match n with
    | 0 -> 0
    | 1 -> 1
    | _ -> fib (n-1) + fib (n-2)

Dabei gilt der Unterstrich als Wildcardzeichen und ist gleichzusetzen mit dem Else-Fall eines Case-Verteilers. Dies waren aber schon die Gemeinsamkeiten, in den folgenden Punkten unterscheidet sich Pattern Matching von den Case-Verteilern: