Funktionale Programmierung mit Haskell/ Funktionen höherer Ordnung
Einfache Funktionen besitzen eine bestimmte Menge an Werten (z.B. Listen, Zahlen oder Tupel) als Funktionsargumente. Funktionen höherer Ordnung besitzen auch Funktionen als Funktionsargumente. Sie sind ein wichtiger Teil der Haskell-Programmierung.
Die Funktion map
[Bearbeiten]Manchmal wird eine Funktion auf jedes Element einer Liste angewandt und das Ergebnis wird wieder in eine Liste gepackt. Hier ein einfaches Beispiel mit der Funktion odd
, die auf ungerade Zahlen True
ausgibt, sonst False
:
Wird die Funktion odd x
durch (x+3)
ersetzt, addiert die Funktion den Wert drei auf jedes Listenelement. Dieser zweizeilige rekursive Algorithmus repräsentiert also ein Schema für Listenverarbeitung. Er ist in der Funktion map
so implementiert:
map f [] = []
map f (x:xs) = f x : map f xs
Wobei f x
für die Funktionen wie odd x
oder (x+3)
steht. In Pseudocode lautet der Algorithmus so:
Gegeben ist eine Liste und eine Funktion f, die auf jedes Listenelement angewendet werden soll. Gesucht ist eine Liste mit den Ergebniswerten. 1. Ist die Liste leer, gib eine leere Liste zurück (und brich damit die Rekursion ab) 2. Ist die Liste nicht leer, wende f auf das erste Listenelement an und lege das Ergebnis in einer Liste ab 3. Mach weiter bei 1. mit dem Rest der Liste
Damit entsteht ein mächtiges Werkzeug zur Listenverarbeitung:
Prelude> map odd [1..5]
[True,False,True,False,True]
Prelude> map (+3) [1..5]
[4,5,6,7,8]
Prelude> map snd [("Eins",1),("Zwei",2),("Drei",3),("Vier",4),("Fuenf",5)]
[1,2,3,4,5]
Prelude> map (Data.Char.digitToInt) "987654"
[9,8,7,6,5,4]
Prelude> map (show.Data.Char.digitToInt) "987654"
["9","8","7","6","5","4"]
Prelude> map zahlWort [97..103] -- Funktion zahlWort aus dem Kapitel Rekursion
["siebenundneunzig","achtundneunzig","neunundneunzig","einhundert","einhunderteins","einhundertzwei","einhundertdrei"]
Prelude> map Data.Char.toUpper "siebenundneunzig"
"SIEBENUNDNEUNZIG"
Prelude>
Die Funktion flip
[Bearbeiten]Eine sehr seltsam anmutende Funktion ist flip
. Ihre Definition sieht so aus:
flip :: (a -> b -> c) -> b -> a -> c
flip f x y = f y x
Eine Funktion f
mit zwei Parametern x
und y
, die als y
und x
ausgeführt werden? Genau das ist damit gemeint. flip
tauscht lediglich die Position der zwei Übergabeparameter aus:
Prelude> div 10 3 -- Zehn geteilt durch drei ist 3 (der Rest interessiert uns hier nicht)
3
Prelude> div 3 10 -- drei geteilt durch zehn ist 0 (der Rest interessiert uns hier nicht)
0
Prelude> flip div 3 10 -- flip vertauscht die Argumente in der Reihenfolge
3
Prelude> flip 3 `div`10 -- aber nicht in Infix-Notation
<interactive>:6:1:
No instance for (Show (b0 -> a0 -> c0))
arising from a use of ‘print’
In a stmt of an interactive GHCi command: print it
Prelude>Prelude>
Hier ein kleines Anwendungsbeispiel zur Anzeige von ganzzahligen Werten als binäre Strings[1]:
Die Funktion Numeric.showIntAtBase
hat eine etwas komplizierte Parameterleiste:
Prelude> :t Numeric.showIntAtBase
Numeric.showIntAtBase
:: (Show a, Integral a) => a -> (Int -> Char) -> a -> ShowS
Prelude> Numeric.showIntAtBase 16 Data.Char.intToDigit 1000 "hex"
"3e8hex"
Prelude>
Der erste Wert steht für die Basis der Zahl, die ausgegeben werden soll (hier 16, also das Hexadezimalsystem), dann eine Funktion, die eine Zahl in einen Character verwandelt, dann die Zahl, die umgewandelt werden soll, dann einen String, der nur angehängt wird ("hex"). Diese Formel soll nun in eine Funktion verwandelt werden:
Prelude> let showBin x = Numeric.showIntAtBase 2 Data.Char.intToDigit x ""
Prelude> showBin 50
"110010"
In Haskell muss der Übergabeparameter x
nicht angegeben werden, wenn x
in der Formel ganz hinten steht. Daher wäre es schön, wenn die Formel so aussehen würde: let showBin x = Numeric.showIntAtBase 2 Data.Char.intToDigit "" x
. Diesen "Parametertausch" bietet die flip
-Funktion:
Prelude> let showBin x = flip (Numeric.showIntAtBase 2 Data.Char.intToDigit) "" x -- In dieser Form kann auf das x ganz verzichtet werden.
Prelude> let showBin = flip (Numeric.showIntAtBase 2 Data.Char.intToDigit) ""
Prelude> showBin 4
"100"
Prelude> showBin 132987
"100000011101111011"
Es ist vielleicht etwas umständlich, eine Formel aus diesem Grund umzubauen, aber immerhin ist es möglich.
Die Funktion zipWith
[Bearbeiten]zipWith
verarbeitet die Inhalte zweier Listen gemäß einer Funktion und gibt eine neue Liste zurück:
Prelude> -- Addition von Listenelementen
Prelude> zipWith (+) [1,2,3,4,5] [10,20,30,40]
[11,22,33,44]
Prelude> -- Addition von Listenelementen, davon ist eine Liste unendlich groß
Prelude> zipWith (+) [1..] [10,20,30,40]
[11,22,33,44]
Prelude> -- Größer/Gleich-Vergleich:
Prelude> zipWith (>=) [1,2,3,4,5] [10,20,3,4]
[False,False,True,True]
Prelude> -- Größer-Als-Vergleich zwischen einer Zahl und einer Zahl in Stringform (mit Lambda-Funktion)
Prelude> zipWith (\x y -> x > read (y) ) [1,2,30,40] ["10","20","3","4"]
[False,False,True,True]
Prelude>
Für die Funktion zipWith
braucht es in Haskell nicht mehr als vier Zeilen Code:
zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith f [] bs = []
zipWith f as [] = []
zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
Erläuterung:
- Die Typdefinition in der ersten Zeile wird im Kapitel Typen von Funktionen erläutert
- die Funktion wird als
f
bezeichnet. Wenn die erste Liste leer ist, gib eine leere Liste zurück (Rekursionsende) - Wenn die zweite Liste leer ist, gib eine leere Liste zurück (Rekursionsende). as und bs steht für die Mehrzahl von a und b
- Wenn beide Listen nichtleer sind: wende die Funktion
f
auf die ersten Elemente der Liste an und rufe zipWith mit dem Rest der beiden Listen wieder auf. Der Doppelpunkt zeigt an, dass hier eine Liste aufgebaut wird. DiezipWith
-Funktion ist also eine typische Rekursion mit Listenerzeugung.
Die Funktionen curry und uncurry
[Bearbeiten]Funktionsparameter werden in den meisten Fällen hinter dem Funktionsnamen aufgeführt, getrennt von Leerzeichen. In diesem Fall spricht man von curried functions. Uncurried functions sind Funktionen, deren Werte Teile von Tupeln sind. Die Funktion curry
ist dazu da, uncurried functions als curried functions auszuführen, die Funktion uncurry
wandeld curried functions in uncurried functions um:
-- 'curry' converts an uncurried function to a curried function.
curry :: ((a, b) -> c) -> a -> b -> c
curry f x y = f (x, y)
-- 'uncurry' converts a curried function to a function on pairs.
uncurry :: (a -> b -> c) -> ((a, b) -> c)
uncurry f p = f (fst p) (snd p)
Ein paar Beispiele:
Prelude> curry fst 5 6 -- ist äquivalent zu fst (5,6)
5
Prelude> curry snd 5 6 -- ist äquivalent zu snd (5,6)
6
Prelude> uncurry (+) (3,4) -- ist äquivalent zu 3 + 4
7
Prelude> uncurry (/) (3,4) -- ist äquivalent zu 3 / 4
0.75
Prelude>
Die fold-Funktionen
[Bearbeiten]Die fold
-Funktionen verarbeiten immer eine Liste gemäß einer Funktion mit zwei Parametern. Das Ergebnis ist immer ein einzelner Wert, z.B. eine Zahl oder ein String.
foldr1
[Bearbeiten]foldr1
wurde bereits im Kapitel Rekursion aus Sicht der Rekursionen behandelt. Seine Definition ist:
foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 _ [x] = x
foldr1 f (x:xs) = f x (foldr1 f xs)
foldr1 _ [] = errorEmptyList "foldr1"
Diese Definition ist sicherlich nicht leicht zu verstehen. Vereinfacht gesagt, arbeitet foldr1
eine Liste von rechts nach links ab, gemäß einer Funktion f
.
Zum besseren Verständnis des Algorithmus definieren wir einen Subtraktions-Befehl sub
und setzen ihn in die foldr1
-Funktion ein, zusammen mit einer kurzen Liste mit den Zahlen eins bis sechs[2]:
Prelude> let sub a b = a - b
Prelude> sub 5 3
2
Prelude> foldr1 (sub) [1..6]
-3
Nun nutzen wir die foldr1
-Funktion selbst, um den Algorithmus dahinter darzustellen. Dafür definieren wir eine foldrShow
-Funktion und bauen mit foldr1
einen String auf, der selbst als Befehl ausführbar ist und das gleiche Ergebnis liefert:
Prelude> let foldrShow a b = "sub " ++ a ++ " (" ++ b ++")"
Prelude> foldr1 (foldrShow) (map show [1..6])
"sub 1 (sub 2 (sub 3 (sub 4 (sub 5 (6)))))"
Prelude> sub 1 (sub 2 (sub 3 (sub 4 (sub 5 (6))))) -- Das Ergebnis wird ohne Anführungszeichen auf die Befehlszeile kopiert und ausgeführt
-3
foldrShow
besitzt natürlich zwei Parameter, denn wie oben erwähnt arbeiten fold
-Funktionen immer mit Funktionen, die zwei Parameter besitzen. Mit (map show [1..6]
wird aus den Zahlen eins bis sechs diese Liste: ["1","2","3","4","5","6"]
. So baut sich foldr1
einen Befehl auf, den er (unter Weglassung der Ausführungszeichen) selbst ausführen kann. Mit diesem Ansatz lässt sich die Arbeitsweise von fold
-Befehlen mit wenig Aufwand erklären und nachvollziehbar darstellen.
foldl1
[Bearbeiten]Die Funktion foldl1
unterscheidet sich von foldr1
dadurch, dass die Liste von links nach rechts abgearbeitet wird:
foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs) = foldl f x xs
foldl1 _ [] = errorEmptyList "foldl1"
Auch hier verdeutlicht sich die Funktionsweise mit dem sub
-Befehl, allerdings weicht die Klammersetzung im foldlShow
von der Klammersetzung in foldrShow
ab:
Prelude> foldl1 (sub) [1..6]
-19
Prelude> let foldlShow a b = "( sub " ++ a ++ " " ++ b ++")"
Prelude> foldl1 (foldlShow) (map show [1..6])
"( sub ( sub ( sub ( sub ( sub 1 2) 3) 4) 5) 6)"
Prelude> ( sub ( sub ( sub ( sub ( sub 1 2) 3) 4) 5) 6)
-19
foldl und foldr
[Bearbeiten]Was ist nun der Unterschied zwischen den Funktionen foldr1
bzw. foldl1
zu den Funktionen foldr
bzw. foldl
? Ganz einfach der, dass bei den letzteren beiden ein Startwert mitgegeben wird:
Prelude> foldl (foldlShow) "0" (map show [1..6])
"( sub ( sub ( sub ( sub ( sub ( sub 0 1) 2) 3) 4) 5) 6)"
Prelude> foldl (sub) 0 [1..6]
-21
Prelude> foldr (foldrShow) "0" (map show [1..6])
"sub 1 (sub 2 (sub 3 (sub 4 (sub 5 (sub 6 (0))))))"
Prelude> foldr (sub) 0 [1..6]
-3
Der Startwert wird also bei foldl
links an der Liste angefügt, bei foldr
rechts. Natürlich hat das Auswirkungen auf das Ergebnis.
foldl' und foldr'
[Bearbeiten]Die unfold-Funktionen
[Bearbeiten]Die scan-Funktionen
[Bearbeiten]Die scan
-Funktionen verarbeiten, ähnlich wie die foldr
-Funktionen, eine Liste gemäß einer Funktion f
. Das Ergebnis ist aber kein einzelner Wert, sondern wiederum eine Liste. Zum Verständnis testen wir wieder das Verhalten des sub
-Befehls in den Funktionen scanl
, scanl1
, scanr
und scanr1
:
Prelude> let sub a b = a - b
Prelude> sub 5 (sub 4 2)
3
Prelude> let scanlShow a b = "(sub " ++ a ++ " " ++ b ++")"
Prelude> scanl (sub) 0 [1..5]
[0,-1,-3,-6,-10,-15]
Prelude> scanl (scanlShow) "0" (map show [1..5])
["0","(sub 0 1)","(sub (sub 0 1) 2)","(sub (sub (sub 0 1) 2) 3)","(sub (sub (sub (sub 0 1) 2) 3) 4)",
"(sub (sub (sub (sub (sub 0 1) 2) 3) 4) 5)"]
Prelude> (sub (sub (sub (sub (sub 0 1) 2) 3) 4) 5) -- Kopie von oben; der letzte Wert in der Liste
-15
Prelude> scanl1 (sub) [1..5]
[1,-1,-4,-8,-13]
Prelude> scanl1 (scanlShow) (map show [1..5])
["1","(sub 1 2)","(sub (sub 1 2) 3)","(sub (sub (sub 1 2) 3) 4)","(sub (sub (sub (sub 1 2) 3) 4) 5)"]
Prelude> (sub (sub (sub (sub 1 2) 3) 4) 5)
-13
Prelude> let scanrShow a b = "sub " ++ a ++ " (" ++ b ++")"
Prelude> scanr (sub) 0 [1..5]
[3,-2,4,-1,5,0]
Prelude> scanr (scanrShow) "0" (map show [1..5])
["sub 1 (sub 2 (sub 3 (sub 4 (sub 5 (0)))))","sub 2 (sub 3 (sub 4 (sub 5 (0))))","sub 3 (sub 4 (sub 5 (0)))",
"sub 4 (sub 5 (0))","sub 5 (0)","0"]
Prelude> sub 1 (sub 2 (sub 3 (sub 4 (sub 5 (0))))) -- Der erste Term aus obiger Liste
3
Prelude> scanr1 (sub) [1..5]
[3,-2,4,-1,5]
Prelude> scanr1 (scanrShow) (map show [1..5])
["sub 1 (sub 2 (sub 3 (sub 4 (5))))","sub 2 (sub 3 (sub 4 (5)))","sub 3 (sub 4 (5))","sub 4 (5)","5"]
Prelude>