Technisch gesehen ist eine Higher Order Function einfach eine Funktion, die mindestens eines von beidem tut:
- Sie nimmt eine Funktion als eines ihrer Argumente entgegen.
- Sie gibt eine Funktion als ihr Ergebnis zurück.
In der Welt der funktionalen Programmierung ist die Verwendung meist enger gefasst.
Der Begriff bezeichnet meist Funktionen wie filter, map und reduce, die eine übergebene Funktion auf die Elemente einer Kollektion anwenden.
Mit Kollektionen arbeiten
An diesem Punkt im Lehrplan haben wir bereits verschiedene Wege gesehen, eine Operation auf alle Elemente einer iterierbaren Kollektion wie einem Vector anzuwenden:
- Eine Schleife verwenden (wie die meisten Programmiersprachen seit den Anfängen des digitalen Rechnens).
- Eine Comprehension verwenden (im Python-Stil).
- Broadcasting verwenden (eine typisch Julia-Syntax, auch wenn sie R, Matlab und NumPy viel verdankt).
Dieses Konzept konzentriert sich auf Funktionen höherer Ordnung (bekannt aus jeder funktionalen Sprache wie Haskell oder F#).
Weitere mögliche Ansätze sind:
- Rekursion (wie in Sprachen der ML-Familie).
- Julia erlaubt das, aber ohne Tail-Call-Optimierung droht ein Stack Overflow.
- Metaprogrammierung mit Makros (traditionell ein Merkmal von Lisp).
- Das wird in der fortgeschrittenen Julia-Programmierung häufig verwendet, aber in den meisten Fällen gilt: mit Vorsicht anwenden.
- Andere Optionen sind wahrscheinlich leichter zu schreiben und viel leichter zu debuggen.
Filtern
Die Funktion filter() nimmt eine übergebene Funktion mit einem booleschen Rückgabewert und wendet sie auf eine Kollektion an.
Nur Elemente, die true zurückgeben, sind im Rückgabewert enthalten, der denselben grundlegenden Typ wie die Eingabe hat (siehe unten).
julia> filter(iseven, 1:6)
3-element Vector{Int64}:
2
4
6
# String is a collection of Chars, so String in -> String out
julia> filter(!isascii, "Hrōðgār")
"ōðā"
# tuple input -> tuple output
julia> filter(iseven, (1, 2, 3, 4, 5))
(2, 4)
Bei mehrdimensionalen Arrays flacht filter die Dimensionen der Eingabe ab und gibt einen Vector zurück: die wichtigste Ausnahme von jeder Regel, nach der der Ausgabetyp zum Eingabetyp passt.
julia> m
2×3 Matrix{Int64}:
1 2 3
4 5 6
julia> filter(isodd, m)
3-element Vector{Int64}:
1
5
3
Die Beispiele oben verwenden eingebaute Funktionen, aber der Einsatz anonymer Funktionen ist in diesem Zusammenhang sehr verbreitet.
julia> filter(x -> x % 3 == 0, 1:20)
6-element Vector{Int64}:
3
6
9
12
15
18
Es gibt auch eine In-Place-Version, filter!(), wie für viele der Funktionen in diesem Konzept.
Abbilden
Die Funktion map() transformiert eine Kollektion, indem sie eine Funktion auf jedes Element anwendet.
In einfachen Fällen kann das ähnlich wie Broadcasting sein, wobei die Form der Ausgabe zur Eingabe passt.
julia> map(√, [1, 4, 9])
3-element Vector{Float64}:
1.0
2.0
3.0
julia> map(x -> x^2 + 1, 1:4)
4-element Vector{Int64}:
2
5
10
17
julia> m
2×3 Matrix{Int64}:
1 2 3
4 5 6
julia> map(√, m)
2×3 Matrix{Float64}:
1.0 1.41421 1.73205
2.0 2.23607 2.44949
map() arbeitet auch elementweise auf mehreren Kollektionen.
julia> map(*, [1, 2], [3, 4])
2-element Vector{Int64}:
3
8
Konzeptionell können wir uns das so vorstellen, als würden wir zip() auf den mehreren Eingabekollektionen ausführen und dann map() auf jedes Element des Zwischenergebnisses anwenden.
Das ist nur eine grobe Analogie und sagt nichts über die Implementierung aus!
Wie bei zip() werden Kollektionen mit nicht zueinander passender Form auf die Dimension(en) der kleinsten gekürzt.
Manchmal werden nur die Seiteneffekte der übergebenen Funktion gebraucht, etwa ein Schreibvorgang in eine Datenbank oder ein push! in ein Array.
Dann steht die Funktion höherer Ordnung foreach() zur Verfügung, die immer nothing zurückgibt.
Reduzieren
Die Funktion reduce() nimmt eine Funktion mit zwei Argumenten und wendet sie auf eine Kollektion an, was zu einer Dimensionsreduktion führt.
Das mag abstrakt verwirrend klingen, aber denk an Funktionen wie sum() oder prod(), die eine Kollektion entgegennehmen und einen einzelnen Wert zurückgeben.
julia> sum(1:4) # add
10
julia> prod(1:4) # multiply
24
Diese speziellen Funktionen sind hoch optimiert und sollten immer verwendet werden, wenn sie verfügbar sind.
Weitere Beispiele sind maximum() und minimum(), die logischen Funktionen all() und any() sowie viele statistische Funktionen.
Nur zur Veranschaulichung: betrachte dieselbe Funktionalität, umgesetzt mit dem allgemeineren reduce() (zur Erinnerung: die Infix-Operatoren + und * sind intern eigentlich Funktionen).
julia> reduce(+, 1:4) # add
10
julia> reduce(*, 1:4) # multiply
24
Wie sum() und andere Aggregationsfunktionen kann reduce() ein optionales Keyword-Argument dims annehmen, um die zu reduzierenden Dimension(en) anzugeben.
julia> m
2×3 Matrix{Int64}:
1 2 3
4 5 6
julia> reduce(+, m; dims=1)
1×3 Matrix{Int64}:
5 7 9
Das sind einfache Beispiele, weil Addition und Multiplikation sowohl kommutativ (1+2 == 2+1) als auch assoziativ sind ( (1+2)+3 == 1+(2+3) ).
Das ist alles andere als universell!
Selbst so gängige Operationen wie Subtraktion und Division sind nicht assoziativ.
Dazu kommt das Problem, dass sich Gleitkommafehler über große Kollektionen hinweg ansammeln können, sodass ein Reduce von links nach rechts ein etwas anderes Ergebnis liefern kann als von rechts nach links.
Die Richtung der reduce-Funktion von Julia ist implementierungsabhängig und nicht garantiert.
Um die Richtung explizit zu steuern, gibt es die Funktionen foldl() und foldr(), die nominell bei „links“ bzw. „rechts“ beginnen (bei einem Vector tatsächlich oben und unten).
julia> foldl(-, 1:3) # (1 - 2) - 3
-4
julia> foldr(-, 1:3) # 1 - (2 - 3)
2
Beachte, dass diese für Kollektionen gedacht sind, die sich als eindimensional behandeln lassen und ein skalares Ergebnis zurückgeben.
Ein dims-Argument wird für foldl und foldr nicht unterstützt, nur für reduce.
MapReduce
Eine map-Operation mit einem reduce zu kombinieren, ist in vielen Programmierbereichen sehr verbreitet.
Wir könnten nacheinander map ausführen und dann reduce auf eine Zwischenkollektion anwenden.
Das ist jedoch bestenfalls ineffizient und skaliert sehr schlecht, je größer die Kollektion wird.
Es wird dringend empfohlen, stattdessen die kombinierte Funktion mapreduce() zu verwenden.
Sie kann einen deutlich leistungsfähigeren Algorithmus umsetzen, der die map/reduce-Operationen ineinander verschränkt.
Das erste Argument ist die Funktion, mit der abgebildet wird, das zweite Argument ist der Reduce-Operator.
julia> mapreduce(x -> x^2 + 1, +, 1:3)
17
# equivalent to (2 + 5 + 10)
julia> sum(map(x -> x^2 + 1, 1:3))
17
Wie zu erwarten, hat Julia auch mapfoldl()- und mapfoldr()-Funktionen für Situationen, in denen die Richtung wichtig ist.
Lernübung
