Haskell Language
Funktionen höherer Ordnung

Bemerkungen

Grundlagen höherer Funktionen

Überprüfen Sie die Teilanwendung, bevor Sie fortfahren.

In Haskell wird eine Funktion, die andere Funktionen als Argumente oder Rückgabefunktionen annehmen kann, eine Funktion höherer Ordnung genannt .

Es folgen alle Funktionen höherer Ordnung :

map       :: (a -> b) -> [a] -> [b]
filter    :: (a -> Bool) -> [a] -> [a]
takeWhile :: (a -> Bool) -> [a] -> [a]
dropWhile :: (a -> Bool) -> [a] -> [a]
iterate   :: (a -> a) -> a -> [a]
zipWith   :: (a -> b -> c) -> [a] -> [b] -> [c]
scanr     :: (a -> b -> b) -> b -> [a] -> [b]
scanl     :: (b -> a -> b) -> b -> [a] -> [b]

Dies ist besonders nützlich, da sie es uns ermöglichen, neue Funktionen zusätzlich zu den bereits vorhandenen Funktionen zu erstellen, indem Funktionen als Argumente an andere Funktionen übergeben werden. Daher der Name, Funktionen höherer Ordnung .

Erwägen:

Prelude> :t (map (+3))
(map (+3)) :: Num b => [b] -> [b]

Prelude> :t (map (=='c'))
(map (=='c')) :: [Char] -> [Bool]

Prelude> :t (map zipWith)
(map zipWith) :: [a -> b -> c] -> [[a] -> [b] -> [c]]

Diese Fähigkeit, einfach Funktionen zu erstellen (wie zum Beispiel durch Teilanwendung, wie sie hier verwendet wird), ist eine der Eigenschaften, die die Funktionsprogrammierung besonders leistungsfähig macht und kurze, elegante Lösungen ermöglicht, die sonst Dutzende Zeilen in anderen Sprachen benötigen. Die folgende Funktion gibt beispielsweise die Anzahl der ausgerichteten Elemente in zwei Listen an.

aligned :: [a] ->  [a] -> Int
aligned xs ys = length (filter id (zipWith (==) xs ys))

Lambda-Ausdrücke

Lambda-Ausdrücke ähneln anonymen Funktionen in anderen Sprachen.

Lambda-Ausdrücke sind offene Formeln, die auch Variablen angeben, die gebunden werden sollen. Die Auswertung (Ermitteln des Werts eines Funktionsaufrufs) erfolgt dann durch Ersetzen der gebundenen Variablen im Körper des Lambda-Ausdrucks durch die vom Benutzer angegebenen Argumente. Vereinfacht ausgedrückt, erlauben uns Lambda-Ausdrücke, Funktionen durch variable Bindung und Substitution auszudrücken.

Lambda-Ausdrücke sehen aus

\x -> let {y = ...x...} in y

Innerhalb eines Lambda-Ausdrucks werden die Variablen auf der linken Seite des Pfeils auf der rechten Seite, dh dem Körper der Funktion, als gebunden betrachtet.

Betrachten Sie die mathematische Funktion

f(x) = x^2

Als Haskell-Definition gilt es

f    x =  x^2

f = \x -> x^2

was bedeutet, dass die Funktion f dem Lambda-Ausdruck \x -> x^2 .

Betrachten Sie die Parameter der Funktion höherer Ordnung map , das ist eine Funktion vom Typ a -> b . Wenn es nur einmal in einem Aufruf zur map und an keiner anderen Stelle im Programm, ist es zweckmäßig, es als Lambda-Ausdruck anzugeben, anstatt eine solche Wegwerffunktion zu benennen. Als Lambda-Ausdruck geschrieben,

\x -> let {y = ...x...} in y

x enthält einen Wert vom Typ a , ...x... ist ein Haskell-Ausdruck, der auf die Variable x verweist, und y enthält einen Wert vom Typ b . So könnten wir zum Beispiel folgendes schreiben

map (\x -> x + 3)

map (\(x,y) -> x * y)

map (\xs -> 'c':xs) ["apples", "oranges", "mangos"]

map (\f -> zipWith f [1..5] [1..5]) [(+), (*), (-)]

Currying

In Haskell werden alle Funktionen als Curried betrachtet: Das heißt, alle Funktionen in Haskell benötigen nur ein Argument.

Nehmen wir die Funktion div :

div :: Int -> Int -> Int

Wenn wir diese Funktion mit 6 und 2 aufrufen, erhalten wir wenig überraschend 3:

Prelude> div 6 2
3

Dies verhält sich jedoch nicht ganz so, wie wir denken könnten. First div 6 wird ausgewertet und liefert eine Funktion vom Typ Int -> Int . Diese resultierende Funktion wird dann auf den Wert 2 angewendet, der 3 ergibt.

Wenn wir uns die Typensignatur einer Funktion ansehen, können wir unser Denken von "zwei Argumente vom Typ Int " in "ein Int und eine Funktion zurückgeben, die ein Int . Dies wird bekräftigt, wenn man bedenkt, dass Pfeile in der Typnotation rechts zugeordnet sind , so dass div tatsächlich folgendermaßen gelesen werden kann:

div :: Int -> (Int -> Int)

Im Allgemeinen können die meisten Programmierer dieses Verhalten zumindest beim Lernen der Sprache ignorieren. Aus theoretischer Sicht "sind formale Beweise einfacher, wenn alle Funktionen einheitlich behandelt werden (ein Argument in, ein Ergebnis heraus)."