Funktionale Programmierung mit Haskell/ Rekursion

Rekursion ist in sehr vielen Programmiersprachen ein wichtiges Programmierprinzip. Die folgenden Beispiele zeigen rekursive Algorithmen in Haskell.

Rekursion auf einer Liste Bearbeiten

Im Kapitel Funktionen auf Listen wurde bereits eine Rekursion auf eine Liste besprochen: die Funktion letztes ruft sich selbst (mit immer kürzer werdender Liste) so lange auf, bis nur noch ein Element in der Liste vorhanden ist. Dieses Element ist dann das Ergebnis - und gleichzeitig die Abbruchbedingung:

Haskell-Programm in Datei letztes.hs
-- Liefert das letzte Element einer Liste
letztes [] = []
letztes [x] = [x]
letztes (x:xs) = letztes xs
  Ausgabe
$>'ghci letztes.hs
...Ok, modules loaded: Main.
*Main>letztes []
[]
*Main>letztes [8,9,10]
[10]
*Main>letztes ['a'..'z']
"z"
*Main>letztes "String als Liste" -- hier wird ein String als Liste übergeben
"e"
*Main>


Quicksort Bearbeiten

Der Quicksort ist ein sehr schneller rekursiver Algorithmus zur Sortierung von Listen [1]:

Dateiname qsort.hs
{- Quicksort -}
qsort :: Ord a => [a] -> [a]
qsort []     = []
qsort (x:xs) = qsort kleinergl ++ [x] ++ qsort groesser
            where
              kleinergl = [y | y <- xs, y <= x]
              groesser  = [y | y <- xs, y > x]
  Ausgabe
Prelude> :l qsort.hs 
[1 of 1] Compiling Main             ( qsort.hs, interpreted )
Ok, modules loaded: Main.

*Main> qsort [80, 9, 133, 55, -8, 7, 222]
[-8,7,9,55,80,133,222]

*Main> qsort "Ein Quicksort-Programm"
" -EPQacgiikmmnoorrrstu"

*Main> qsort [("Eins",1),("Zwei",2),("Drei",3),("Vier",4),("Fuenf",5)]
[("Drei",3),("Eins",1),("Fuenf",5),("Vier",4),("Zwei",2)]

*Main> qsort [(1,"Eins"),(5,"Fuenf"),(4,"Vier"),(2,"Zwei"),(3,"Drei")]
[(1,"Eins"),(2,"Zwei"),(3,"Drei"),(4,"Vier"),(5,"Fuenf")]

Dieser Quicksort kann alle Datentypen sortieren, die von der Typklasse Ord abgeleitet sind, d.h. für alle Werte, die mit Größer- und Kleiner-Operationen vergleichbar sind.

Man beachte, wie klar und einfach diese Implementierung ist. Es werden keine übergeordneten Variablen benötigt, selbst die Reihenfolge der Befehle ist irrelevant.


Die Fibonacci-Folge Bearbeiten

Die Fibonacci-Folge ist eine Zahlenfolge, die mit 0 und 1 beginnt. Jede weitere Zahl setzt sich aus den beiden vorhergehenden Zahlen zusammen. Diese einfache Regel lässt sich so in ein Programm fassen:

Dateiname fib1.hs
{- Fibonacci-Folge -}
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
  Ausgabe
Prelude> :l fib1.hs 
[1 of 1] Compiling Main             ( fib.hs, interpreted )
Ok, modules loaded: Main.

*Main> fib 0
0
*Main> fib 1
1
*Main> fib 2
1
*Main> fib 3
2
*Main> fib 20
6765
*Main> fib 40          -- Achtung, lange Laufzeit!
102334155

So kann also die Fibonacci-Zahl an einer bestimmten Stelle der Reihe bestimmt werden. Das Programm ist leicht zu verstehen, aber die Laufzeit ist durch die umständlichen rekursiven Aufrufe unglaublich lang.

Das Kleinste gemeinsame Vielfache aus einer Liste von Zahlen Bearbeiten

Für das kleinste gemeinsame Vielfache (abk. kgV, engl. lowest common multiple, abk. lcm) gibt es den Befehl lcm:

Prelude> :t lcm
lcm :: Integral a => a -> a -> a
Prelude> lcm 14 18
126

Eine Aufgabe aus dem Euler-Projekt lautet:

Finde das kleinste gemeinsame Vielfache aller Zahlen von 1 bis 20[2]


Dieser Lösungsansatz liefert ein gültiges Ergebnis:

Prelude> lcm 1 (lcm 2 (lcm 3 (lcm 4 (lcm 5 (lcm 6 (lcm 7 (lcm 8 (lcm 9 (lcm 10 (lcm 11 (lcm 12 (lcm 13 (lcm 14 (lcm 15 (lcm 16 (lcm 17 
(lcm 18 (lcm 19 (20)))))))))))))))))))
232792560
Prelude>
Hinweis: die Zeilenumbrüche hinter lcm 17 wurden hier und in den unteren Kästen zur besseren Lesbarkeit per Hand einfgefügt.

Aber dies ist keine praktikable Lösung. Gerade in Haskell wäre es geschickt, Listen einzusetzen. Dann könnte der Befehl so lauten:

Prelude> lcm [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]

Aber natürlich existiert der Befehl so nicht, er lässt sich aber schreiben. Der Pseudocode dafür geht so:

Gegeben ist eine beliebige Liste mit mindestens zwei ganzen Zahlen. Gesucht ist das kleinste gemeinsame Vielfache:
1. Wenn die Liste nur zwei Elemente besitzt, gib deren kgV zurück
2. Wenn die Liste mehr als zwei Elemente besitzt: 
   a. nimm die ersten beiden Zahlen und bestimme deren kgV
   b. ersetze die ersten beiden Zahlen der Liste durch den errechneten kgV
3. mach mit der Liste weiter bei 2.

In Haskell lautet der Code und dessen Auswirkung so:

Dateiname lcm'[3].hs
lcm' :: Integral a => [a] -> a
lcm' [x,y] = lcm x y
lcm' (x:y:xs) =  lcm' (lcm x y : xs)
  Ausgabe
Prelude> :l lcm'.hs 
[1 of 1] Compiling Main             ( lcm'.hs, interpreted )
Ok, modules loaded: Main.
*Main> -- normale Sortierung
*Main> lcm' [1..20]
232792560
*Main> -- Abwärts-Sortierung
*Main> lcm' [20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]
232792560
*Main> -- Zahlen durcheinander
*Main> lcm' [19,2,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,20,1]
232792560
-- Zahlen durcheinander, manche kommen mehrmals vor
*Main> lcm' [13,12,20,17,19,2,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,20,1]
232792560

Dieser Algorithmus ist einfach und sehr robust. Aber das nächste Kapitel zeigt, das es in Haskell hierfür auch standardisierte Lösungen gibt.

Die foldr1-Funktion Bearbeiten

Da die Operationen auf Listen in Haskell große Bedeutung haben und Algorithmen wie der oben gezeigte lcm-Algorithmus durchaus häufig sind, gibt es eine Reihe von sehr mächtigen Befehlen dafür. Der Befehl unserer Wahl heißt foldr1.

Prelude> foldr1 lcm [1..20]
232792560
Prelude>

Dieser beeindruckend kurze Befehl wird im Kapitel Funktionen höherer Ordnung noch genauer beschrieben. Übrigens ist foldr1 auch in der Lage, den verschachtelten lcm-Befehl von oben selbst darzustellen:

Prelude> let lcmShow a b = "lcm "++a++" ("++b++")"
Prelude> let stringList = map show [1..20]
Prelude> foldr1 (lcmShow) stringList 
"lcm 1 (lcm 2 (lcm 3 (lcm 4 (lcm 5 (lcm 6 (lcm 7 (lcm 8 (lcm 9 (lcm 10 (lcm 11 (lcm 12 (lcm 13 (lcm 14 (lcm 15 (lcm 16 (lcm 17 
(lcm 18 (lcm 19 (20)))))))))))))))))))"
Prelude> lcm 1 (lcm 2 (lcm 3 (lcm 4 (lcm 5 (lcm 6 (lcm 7 (lcm 8 (lcm 9 (lcm 10 (lcm 11 (lcm 12 (lcm 13 (lcm 14 (lcm 15 (lcm 16 (lcm 17 
(lcm 18 (lcm 19 (20)))))))))))))))))))
232792560
Prelude>

Hier wurde das Ergebnis der foldr1-Funktion kopiert und selbst als Befehl ausgeführt.

Zahlwörter bilden Bearbeiten

Die rekursive Routine zahlWort zur Bildung von Zahlwörtern ruft sich selbst an fünf Stellen auf[4]:

Dateiname zahlWort.hs
{- Zahlen als Zahlwörter darstellen -}
import Data.Char (digitToInt)
 
eins = ["ein","zwei","drei","vier","fuenf","sechs","sieben","acht",
     "neun","zehn","elf","zwoelf","dreizehn","vierzehn","fuenfzehn",
     "sechzehn","siebzehn","achtzehn", "neunzehn"]
zig = ["zwanzig","dreissig","vierzig","fuenfzig","sechzig","siebzig","achtzig","neunzig"]

zahlWort :: Int -> [Char]
zahlWort x
    | x < 0                        = "minus " ++ zahlWort (-x)
    | x == 0                       = "null" 
    | x == 1                       = "eins"
    | x < 20                       = eins !! (x-1)
    | (x >= 20) && (x < 100) && (einerStelle x == 0) = zig !! ((linkeZiffer x) -2)
    | x >= 20 && x < 100           = 
        eins !! ((einerStelle x)-1) ++ "und" ++ zig !! ((linkeZiffer x) -2)
    | x < 1000 && x `mod` 100 ==0  = 
        eins !! (linkeZiffer (x)-1) ++ "hundert"
    | x < 1000					   = 
        eins !! ((linkeZiffer x) -1) ++ "hundert" ++  zahlWort ( x - linkeZiffer (x) * 100)
    | x < 10^6 && (x `mod`1000) == 0 =
        zahlWort (x `div`1000) ++ "tausend"
    | x < 10^6                     = 
        zahlWort (x `div`1000) ++ "tausend" ++ zahlWort (x `mod`1000)
    | otherwise                    = "kann ich nicht"
  where 
     einerStelle x = digitToInt . last . show $ x
     linkeZiffer x = digitToInt . head . show $ x
{- Programmende -}
  Ausgabe
*Main> zahlWort 0
"null"
*Main> zahlWort 1
"eins"
*Main> zahlWort 13
"dreizehn"
*Main> zahlWort 22
"zweiundzwanzig"
*Main> zahlWort (22+33)
"fuenfundfuenfzig"
*Main> zahlWort (-22)
"minus zweiundzwanzig"
*Main> zahlWort (-123455)
"minus einhundertdreiundzwanzigtausendvierhundertfuenfundfuenfzig"
*Main> zahlWort (-102101)
"minus einhundertzweitausendeinhunderteins"
*Main> zahlWort 100000
"einhunderttausend"
*Main> zahlWort 1000000
"kann ich nicht"



  1. Der Sourcecode stammt aus der Wikipedia
  2. Siehe Weblinks [4], Euler-Problem Nr. 5
  3. das Hochkomma ' heißt Tick und kann in Haskell als Teil des Variablennamens verwendet werden
  4. Die Idee stammt aus Weblinks [4], Euler-Problem Nr. 17