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

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:

Dateiname oddList.hs

oddList [] = []
oddList (x:xs) = odd x : oddList xs

Ausgabe

*Main> oddList [1..5]
[True,False,True,False,True]

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

Eine sehr seltsam anmutende Funktion ist flip. Ihre Definition sieht so aus:

Definition von flip in GHC.base

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:

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

zipWith verarbeitet die Inhalte zweier Listen gemäß einer Funktion und gibt eine neue Liste zurück:

Beispiele mit zipWith

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:

Definition von zipWith in GHC.list (vereinfacht dargestellt)

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. Die zipWith-Funktion ist also eine typische Rekursion mit Listenerzeugung.

Die Funktionen curry und uncurry

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:

Definition von curry und uncurry aus dem Modul Data.Tuple

-- '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

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

foldr1 wurde bereits im Kapitel Rekursion aus Sicht der Rekursionen behandelt. Seine Definition ist:

Definition von foldr1 in GHC.list

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:

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

Die Funktion foldl1 unterscheidet sich von foldr1 dadurch, dass die Liste von links nach rechts abgearbeitet wird:

Definition von foldl1 in GHC.list

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

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:

foldl und foldr mit Startwerten 0

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.

Die scan-Funktionen

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:

scan-Funktionen

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>