Month / January 2015

by Carsten König

Listen und Morphismen

Listen sind die typischen Datenstrukturen in der funktionalen Programmierung. Da überrascht es kaum, dass F# oder Haskell viele nette Features rund um Listen bereitstellen.

In diesem Teaser möchte ich aber gar nicht so sehr auf alle coolen Sprachfeatures eingehen sondern euch auch einige Grundlagen und ein paar Begriffe zum Angeben mit auf den Weg geben!

Was sind Listen

Listen sind eine rekursive Datenstruktur, ganz ähnlich zu den verketteten Listen die ihr vielleicht schon kennt. In der funktionalen Programmierung jonglieren wir aber ungern mit Zeigern – wir benutzen lieber unveränderliche algebraische Datenstrukturen. In F#-Deutsch Unterscheidungs-Union genannt – gruselig oder?

Eine algebraische Datenstruktur ist sowas wie ein enum, nur das wir für die Fälle noch Daten aufnehmen können:

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

Damit definieren ich hier eine generische (das 'a) Datenstruktur namens Liste (übrigens hätte ich auch Liste<'a> schreiben können – aber das sieht so nach C# aus!).
Es gibt zwei Fälle aus denen so eine Liste aufgebaut werden kann (durch die | getrennt):

  • Nil falls die Liste leer ist
  • Cons um ein Element vorne vor eine Liste anzufügen – das ist der rekursive Teil. Der Cons-Fall besteht (hinter dem of angegeben) aus einem Wert von Typ 'a und einer weiteren Liste (hatte ich schon erwähnt, dass die Struktur rekursiv ist?).

Der * dort ist kein Malzeichen sondern dient in F# dazu den Typ eines Tupels anzugeben – ein C# Programmierer kann sich also 'a * 'b als Tupel<'a,'b> denken. Die Werte eines Tupels selbst werden aber nicht mit * (das könnte dann zu leicht mit Mal verwechselt werden) sondern mit Klammern und Komma geschrieben: (5,"Hallo") wäre also vom Typ int * string.

Bemerkung

Das * ist gar nicht so schlecht gewählt – Tupel sind Produktdatentypen. Zählt einfach mal die Werte von Bool*Bool und erinnert euch an die Kombinatorik 😉

Übrigens wird das h in Cons (h, tl) Head und die Liste tl Tail genannt. Also ist eine Liste immer entweder leer oder besteht aus einem Kopf und einer weiteren Liste, dem Schwanz (ein Schelm, wer Böses dabei denkt) der Liste.

Wenn wir eine Liste erzeugen wollen können wir so vorgehen:

// string Liste:
let farben = Cons ("rot", Cons ("grün", Cons ("blau", Nil)))

// int Liste:
let zahlen = Cons (1, Cons (2, Cons (3, Cons (4, Nil))))

Und das alles erinnert natürlich stark an LISP (naja … List Prozessing eben).

F# benutzt hier aber einen etwas anderen Syntax:
– statt Nil ist die leere Liste []
– statt Cons benutzen wir einen Operator ::

Das Beispiel sieht dann also so aus:

let farben = "rot" :: "grün" :: "blau" :: []
let zahlen = 1 :: 2 :: 3 :: 4 :: []

Was doch schon besser aussieht: wenigstens die vielen Klammern fallen weg!
Weil das noch nicht gut genug ist, erlaubt F# das auch einfach direkt in []-Klammern zu schreiben:

let farben = ["rot"; "grün"; "blau"]
let zahlen = [1;2;3;4]

und weil die Zahlen so hübsch aufzählbar sogar noch kürzer

let zahlen = [1..4]

Bei den Farben geht das natürlich nicht – so smart ist F# auch nicht!

Quizz

Welches Problem ergibt sich, wenn man versucht alle strings zwichen “a” und “b” aufzulisten?

F# erlaubt es uns natürlich auch zu mischen: 5::[1..4] ist ok!

Übrigens – die Frage kommt ja doch früher oder später – es gibt auch einen Operator um Listen zu verketten: @ – so ergibt [1..4] @ [5..8] == [1..8]. Ihr solltet nur wissen, dass @ ein nicht gerade performanter Operator ist. Es ist eine schöne Aufgabe sich den Operator einmal selbst für Liste zu definieren und zu schauen warum.

Für tail und head der Liste gibt es natürlich auch entsprechende Funktionen. Diese liegen im List Modul von F# und heißen List.head und List.tail – aber Vorsicht: Beide werfen eine Exception, wenn die Liste leer war.

Aber genug der Trivialitäten – ich möchte ja Appetit auf auf die Spartakiade machen und dort soll es ja sportlich zugehen!

Morphismen …

Unterhalten wir uns also über die wohl wichtigsten Operationen auf Listen: folds und unfolds. Natürlich klingen diese Namen noch viel zu harmlos. Sagen wir also lieber Katamorphismus und Anamorphismus!

Anamorphismus / unfold

Die Idee ist es eine abstrakte Funktion für den Aufbau von Listen zu haben. Dabei wird ein Generator benutzt, um aus einem Zustand ein neues Listen-Element und einen neuen Zustand zu erzeugen. Außerdem gibt es ein Abbruchskriterium, das entscheidet, wann der Prozess zu Ende ist. Das ganze wird schließlich mit einem Anfangszustand gefüttert und wir bekommen eine Liste.

Die Typsignatur ist dementsprechend:

unfold : ('state -> ('value * 'state)) 
       -> ('state -> bool) 
       -> 'state 
       -> 'value list

oder mit Argumentnamen:

unfold (next : 'state -> ('value * 'state)) 
       (condition : 'state -> bool) 
       (init : 'state) 
       : 'value list = ...

und eine einfache Implementation kann so aussehen:

let rec unfold (next : 'state -> ('value * 'state)) 
               (condition : 'state -> bool) 
               (init : 'state) 
               : 'value list =
        
    if condition init
    then
        let (value, init') = next init
        value :: unfold next condition init'
    else
        []

Das rec Schlüsselwort wird hier gebraucht, damit ich die Funktion rekursiv aufrufen kann bzw. damit das Symbol unfold innerhalb von unfold auch “in scope” ist.
Die Funktion prüft also zunächst, ob der aktuelle Zustand init (der Name wurde für den Aufrufer statt für die Implementation gewählt) noch die Bedingung condition erfüllt:
– falls nicht sollen also keine Listenelemente mehr erzeugt werden und die leere Liste wird zurückgegeben.
– falls ja wir next benutzt um den nächsten Zustand init' und einen weiteren Wert für die Liste value zu erzeugen. Dann wird eine Liste zurückgegeben, deren Kopf value ist und deren tail rekursiv mittels unfold berechnet wird.

Bemerkung

Seltsamerweise hat es der unfold (noch) nicht in das List Modul geschafft (da hat jemand Angst vor der Unendlichkeit) – dafür gibt es das aber für Seq.

Übungen

Problem 1:

Was ergibt folgender Code?

unfold (fun i -> (i,i+1)) 
       (fun i -> i <= 4)
       1

Problem 2:

Erzeuge die Liste aller Quadratzahlen zwischen 1 und 100 mit Hilfe von unfold.

Problem 3:

Setze das Collatz-Problem mittels unfold um:

Schreibe eine Funktion collatz n, die ausgehend von einer Zahl n eine Liste von Zahlen liefert. Dabei sollen die Elemente x iterativ bestimmt werden:
– falls x gerade ist, dann soll die nächste Zahl in der Folge x/2 sein
– falls x ungerade ist, dann soll die nächste Zahl 3*x+1 sein
– falls x = 1 ist soll die Folge abgebrochen werden.

Beispiel:
collatz 5 = [5; 16; 8; 4; 2; 1]

Hinweise Problem 3:
Wenn ihr es mit den Zahlen übertreiben wollt könnt ihr auch System.Numerics.BigInteger verwenden.
Außerdem müsst ihr vielleicht tricksen um eine abschließende 1 zu bekommen – konzentriert euch zunächst auf den Rest.

Einschub

Mir ist bewusst, dass unfold hier ein großes Problem hat:

> unfold (fun i -&gt; (i,i+1)) (fun i -&gt; i &lt; 100000) 1;;

Process is terminated due to StackOverflowException.

Das liegt daran, dass die hier gezeigte Version nicht tail-recursive ist – sprich jeder rekursive Aufruf landet auf dem Stack. Das kann ich leicht reparieren, nur wird damit die Funktion etwas komplizierter und das wirklich Wichtige versteckt sich etwas hinter den technischen Details:

let unfold (next : 'state -> ('value * 'state)) 
           (condition : 'state -> bool) 
           (init : 'state) 
           : 'value list =
    let rec recurse state cont =
        if condition state
        then
            let (value, state') = next state
            recurse state' (fun rest -> value::rest |> cont)
        else
            cont []
    recurse init id

Damit ist dann alles in Ordnung:

> unfold (fun i -&gt; (i,i+1)) (fun i -&gt; i &lt; 100000) 1;;
val it : int list =
  [1; 2; 3; 4; 5; 6; 
   7; 8; 9; ...]

Ich komme in einem späteren Beitrag sicher nochmals auf dieses Problem und die Lösungstechniken zu sprechen.

Katamorphismen / fold

Duale zum Anamorphismus ist der Katamorphismus: Anstatt eine Liste zu erzeugen, möchte ich eine Liste verarbeiten. Das ist sozusagen die Mutter aller Listen-Operationen. In der Tat ist die Church-Kodierung der Liste genau die Funktion, die wir gleich kennen lernen werden! Falls ihr neugierig seid, wie sowas aussehen kann: habe ich da eine Gist. Aber Vorsicht: die ist in Haskell und spielt ein wenig mehr mit dem Typsystem herum.

Die Intuition hinter fold ist:

In einer Liste l = a :: b :: c :: ... :: z :: [] = Cons(a, Cons (b, ... (Cons z, Nil)..) soll fold f n l jedes Cons durch f und Nil durch n ersetzen.

Beispiel:

fold (+) 0 [1,2,3] = 1 + (2 + (3 + 0))

Weil dabei nach rechts geklammern wird wird das genauer right-fold genannt und ja es gibt auch einen left-fold.

Wie auch immer – die Funktion ist relativ leicht zu implementieren:

let rec fold (f : 'a -> 's -> 's) 
             (n : 's)
             (l : 'a list) =
    match l with
    | []    -> n
    | h::tl -> f h (fold f n tl)

Hier verwende ich ein neues Feature: pattern matching mit dem match Schlüsselwort. Pattern matching ist hier so etwas wie ein erweitertes switch – nicht nur kann ich die Liste auf die einzelnen Fälle untersuchen, sondern dabei auch noch gleich lokal gebundene Namen für die Teile des patterns vergeben (hier zum Beispiel h und tl).

Ich prüfe also, ob die übergebene Liste l:
– leer ist: dann wird einfach n zurückgegeben
– dem Pattern h::tl entspricht: dann berechne ich mit fold f n tl rekursiv den Rest und wende f auf h und diesen Rest an.

Wie oben gibt es wieder Probleme mit dem Stack und ich sollte besser schreiben:

let fold (f : 'a -> 's -> 's) 
             (n : 's)
             (l : 'a list) =
    let rec recurse cont =
        function
        | []    -> cont n
        | h::tl ->
            let cont' tl =
                f h tl |> cont
            recurse cont' tl
    recurse id l

Was aber wieder etwas komplizierter wird. Hier habe ich übrigens ein weiteres Feature genutzt, dass den Code etwas verkleinert: Anstatt

let f x =
   match x with
   | ...

darf ich auch kürzer

let f x =
   function
   | ...

schreiben – function ist nimmt sozusagen ein Argument und leitet gleich ein match darauf ein (intuitiv: function = fun x -> match x with ...).

Der Vollständigkeit halber hier noch die links-geklammerte Version (left-fold):

let rec foldL (f : 's -> 'a -> 's)
              (n : 's)
              (l : 'a list) =
    match l with
    | []    -> n
    | h::tl -> foldL f (f n h) tl

Interessanterweise ist hier der tail-call geschenkt. Bitte beachtet aber, dass sich die Argumentreihenfolge für das f auch umgekehrt hat.

Quiz

Was ergibt foldL (fun tl h -> h::tl) [] [1..5]?

Natürlich müsst ihr diese Funktionen nicht selbst implementieren – ihr findet sie im List-Modul. Unser fold ist List.foldBack und foldL heißt einfach List.fold.

One fold to rule them all

Ich hatte ja erwähnt, dass fold sozusagen der eine Ring für Listen ist. Hier mal eine kurze Auswahl, was man so alles damit machen kann:

Transformation

Angenommen ich möchte eine Liste element-weise transformieren (das Select in LINQ).
Mit fold ist das einfach:

let map f = fold (fun h tl -> f h :: tl) []

Das ist leicht einzusehen: In der Liste ersetzt ja fold jetzt:
– [] mit []
– und Cons (h, tl) mit Cons (f h, tl) – sprich jedes Element h wird mit f h ersetzt.

Summe

Angenommen ich möchte Liste von Zahlen aufaddieren – das geht ebenso einfach:

let summe = fold (+) 0

Naja fast – denn Zahlen übersetzt uns F# jetzt in int (wegen der 0) – ein Problem das Haskell mit seiner Typklasse Num übrigens nicht hätte.

Mit ein paar fortgeschrittenen Features von F# geht das aber durchaus auch generisch – F# hat für Zahlen sowas wie eine abgespeckte Typklasse eingebaut, ich muss die Funktion nur inline definieren und eine generische 0 verwenden:

let inline summe l = 
    fold (+) LanguagePrimitives.GenericZero l

F#-Interactive gibt dann den Typ als

val inline summe :
  l: ^a list ->  ^b
    when ( ^a or  ^b) : (static member ( + ) :  ^a *  ^b ->  ^b) 
    and ^b : (static member get_Zero : ->  ^b)

an und die Funktion ist nicht mehr auf int beschränkt:

> summe [1..5];;
val it : int = 15
> summe [0.1; 0.2; 0.3; 0.4];;
val it : float = 1.0

Und Nein ihr müsst das hier nicht verstehen – das soll ja nur ein Appetitmacher sein 😉

Übungen

  • Versucht doch einmal mit fold die Funktion List.filter (auch bekannt als Where in LINQ) zu implementieren.
  • Für die Bonuspunkte: Implementiert foldL nur mit Hilfe von fold

So das war es für heute.