Implementierung rekursiv definierter Funktionen

Rekursive Funktionen zu definieren ist wie Fahrradfahren: Es sieht einfach aus, wenn man jemandem dabei zuschaut und scheint unmöglich zu sein, wenn man es selbst zum ersten Mal probiert. Aber mit etwas Übung wird es leichter und ganz natürlich.

An drei Beispielen werden wir hier die Vorgehensweise erklären.

Vorgehensweise:

Mit diesen fünf Schritten kommt man leichter zu funktionierendem Haskell-Code. Oder allgemeiner: zu Code, der dem funktionalen Paradigma entspricht.

Schritt: Definiere den Typ der neu zu schreibenden Funktion
Schritt: Zähle die Fälle auf.
Schritt: Definiere die einfachen Fälle.
Schritt: Definiere die anderen Fälle.
Schritt: Verallgemeinere und Vereinfache die Implementierung der neuen Funktion.

Beispiele

Beipiel 1: Das Produkt von Zahlen in einer Liste

Schritt 1: Definiere den Typ

Über den gewünschten Typ der Funktion nachzudenken, ist eine gute Übung und außerdem sehr hilfreich. In diesem Fall beginnen wir mit dem Typ

product :: [Int] -> Int

der besagt, dass die Funktion product einer Liste von Ints einen Int zuordnet. Zu Beginn sollte man die Typen lieber einfacher wählen und sie später weiter verfeinern.

Schritt 2: Zähle die Fälle auf

Für die meisten Argumente gibt es ganz natürliche Spezialfälle. Für Listen zum Beispiel gibt es als einfache Fall die leere Liste und nicht-leere Listen.

Wir notieren also als Code-Gerüst die Fälle:

product []     = 
product (n:ns) =

Für nichtnegative Zahlen sind die Standardfälle 0 und n, für logische Werte sind es True und False und so weiter. Wie für den Typ müssen wir das später weiter verfeinern.

Schritt 3: Definiere die einfachen Fälle

Wir sind immer noch beim Produkt. Weil die 1 das neutrale Element der Multiplikation ist, ist das Produkt einer leeren Liste sinnvollerweise gleich 1.

product []     = 1
product (n:ns) =

Wie in diesem Beispiel werden die einfachen Fälle häufig die Basisfälle.

Schritt 4: Definiere die anderen Fälle

Wie kann man das Produkt einer nicht-leeren Liste von Ints berechnen? Für diesen Schritt ist es sinnvoll, sich zunächst die Zutaten, die wir verwenden können, anzuschauen: Da sind die Funktion product selbst, die Teile n und ns, und die grundlegenden Bibliotheks-Funktionen wie Addition, Multiplikation usw.

In diesem Fall multiplizieren wir einfach die erste Zahl mit dem produkt der restlichen Liste:

product []     = 1
product (n:ns) = n * product ns

Wie in diesem Fall hier werden die anderen Fälle häufig rekursive Fälle sein.

Schritt 5: Verallgemeinere und Vereinfache

Wenn man mal eine Funktion so definiert hat, wird oft schon klar, wie man sie verallgemeinern oder vereinfachen kann.

Hier ist zum Beispiel sofort klar, dass man das Produkt für jede Art Zahlen und nicht nur für ganze Zahlen bilden kann. Also ist es sinnvoll, den Typ auf alle Zahlen auszudehnen:

product :: Num a => [a] -> a
product []     = 1
product (n:ns) = n * product ns

Beispiel 2: drop

Schritt 1: Definiere den Typ

Die Funktion drop wirft ja die ersten n Elemente einer Liste weg. Der Typ müsste also sein:

drop :: Int -> [a] -> [a]

Wir haben mit dieser einen Zeile Code schon vier Design-Entscheidungen getroffen:

Wir verwenden der Einfachheit halber Int statt irgendeinen numerischen Typ.
Wir verwenden currying anstelle von Tupeln, weil das flexibler ist.
Wir haben entschieden, dass wir zuerst die Zahl und dann die Liste als Argumente übergeben, weil das besser lesbar ist:

drop n xs -- liest sich als: wirf n Elemente der xs weg.
Und wir verwenden direkt Polymorphie im Listentyp, damit die Funktion allgemein nutzbar wird.

Schritt 2: Zähle die Fälle auf

Es gibt zwei Standardfälle für das Int Argument (0 und n) und zwei Standardfälle für die Liste ([] und x:xs). Also haben wir in Kombination vier Fälle:

drop 0 []      =
drop 0 (x:xs)  =
drop n []        =
drop n (x:xs)  =

Schritt 3: Definiere die einfachen Fälle

Per Definition sollte das Entfernen von 0 Elementen wieder die ursprüngliche Liste ergeben. Das ergibt die ersten beiden Definitionen:

drop 0 []      = []
drop 0 (x:xs)  = x:xs
drop n []        =
drop n (x:xs)  =

Der dritte Fall würde einen Fehler produzieren, weil man von einer leeren Liste nichts wegnehmen kann. Also definieren wir hier, dass das Ergebnis die leere Liste wird.

drop 0 []      = []
drop 0 (x:xs)  = x:xs
drop n []        = []
drop n (x:xs)  =

Schritt 4: Definiere die anderen Fälle

Wie kann man mehrere (n) Elemente von einer nicht-leeren Liste entfernen? Indem man eins weniger (n-1) vom Rest der Liste enfernt:

drop 0 []      = []
drop 0 (x:xs)  = x:xs
drop n []        = []
drop n (x:xs)  = drop (n-1) xs

Schritt 5: Verallgemeinere und Vereinfache

Wir könnten den einzelnen Typ Int durch den allgemeineren Typ Integral (ganzzahlige Typen) ersetzen:

drop :: Integral b => b -> [a] -> [a]

Es ist aber effizienter, das nicht zu tun, also lassen wir die Typdefinition wie zu Beginn.

Zur Vereinfachung können wir die beiden ersten Fälle zusammenfassen: Wir liefern einfach die Liste wieder zurück.

drop :: Int -> [a] -> [a] 
drop 0 xs      = xs
drop n []        = []
drop n (x:xs)  = drop (n-1) xs

Da es bei einer leeren Liste vollkommen egal ist, wieviele Elemente enfernt werden sollen, ignorieren wir das n:

drop :: Int -> [a] -> [a] 
drop 0 xs      = xs
drop _ []        = []
drop n (x:xs)  = drop (n-1) xs

Und als letzte Vereinfachung ignorieren wir genauso das erste Element der Liste im dritten Fall:

drop :: Int -> [a] -> [a] 
drop 0 xs      = xs
drop _ []        = []
drop n (_:xs)  = drop (n-1) xs

Beispiel 3: Die Library-Funktion init

Die Funktion init entfernt das letzte Element von einer nicht-leeren Liste.

Schritt 1: Definiere den Typ

Init nimmt eine Liste von irgendeinem Typ a und macht daraus eine Liste vom Typ a.

init [a] -> [a]

Schritt 2: Zähle die Fälle auf

Die leere Liste ist kein gültiges Argument für init. Also ist das kein echter Fall. Es bleibt nur der Fall:

init (x:xs) =

Schritt 3: Definiere die einfachen Fälle

Bei den beiden Fällen oben war es sehr direkt und leicht, die einfachen Fälle zu definieren. Hier muss man etwas mehr denken. Jedenfalls: wenn man das letzte Element einer ein-elementigen Liste entfernt, hat man die leere Liste. Diesen Fall kann mit einem guard erledigen:

init (x:xs) | null xs   = [] 
            | otherwise =

Hinweis: die Funktion

null :: [a] -> Bool

entscheidet, ob eine Liste leer ist. Da bei einer ein-elementigen Liste (x:xs) x das eine Element ist und xs die leere Liste ist, ist das genau der Fall hier.

Schritt 4: Definiere die anderen Fälle

Wie kann man das letzte Element einer nicht-leeren Liste entfernen? Indem man einfach das erste Element behält und vom Rest der Liste das letzte Element entfernt:

init (x:xs) | null xs   = [] 
            | otherwise = x : init xs

Schritt 5: Verallgemeinere und Vereinfache

Der Typ von init ist schon so allgemein wie möglich. Aber die Definition kann noch vereinfacht werden: Wir können mit dem Wildcard Pattern die Konstruktion mit den guards loswerden:

init [a] -> [a]
init [_]    = []
init (x:xs) = x : init xs

Das ist genau die Definition aus dem Standard-Prelude.

Übungen:

Definiere eine rekursive Funktion

sumdown :: Int -> Int

die die Summe herab von einer ganzen Zahl n an berechnet:

sumdown 3 -- sollte das Resultat 6 -- 3+2+1+0 = 6 zurückliefern.
Definiere einen Exponentiations-Operator 'hoch' für nicht-negative ganze Zahlen, indem du das Muster der product-Funtion oben verwendest. Und zeige, wie 2 'hoch' 3 ausgewertet wird.
Definiere eine rekursive Funktion

euclid :: Int -> Int -> Int

die den euklidischen Algorithmus zum Finden des größten gemeinsamen Teilers von zwei Zahlen findet. Zum Beispiel:

euclid 6 27 3