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
BearbeitenIm 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:
-- 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
BearbeitenDer Quicksort ist ein sehr schneller rekursiver Algorithmus zur Sortierung von Listen [1]:
{- 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]
AusgabePrelude> :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
BearbeitenDie 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:
{- Fibonacci-Folge -}
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
AusgabePrelude> :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
BearbeitenFü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>
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:
lcm' :: Integral a => [a] -> a
lcm' [x,y] = lcm x y
lcm' (x:y:xs) = lcm' (lcm x y : xs)
AusgabePrelude> :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
BearbeitenDa 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
BearbeitenDie rekursive Routine zahlWort zur Bildung von Zahlwörtern ruft sich selbst an fünf Stellen auf[4]:
{- 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"