15 Programmieren mit Higher-Order Funktionen
In diesem Kapitel wollen wir uns einige Funktionen und Programmiertechniken anschauen, die typisch für funktionale Programmierung mit Higher-Order Funktionen sind.
15.1 Funktionskomposition und "Point-Free Style"
Eine Standard Higher-Order Funktion ist die Funktionskomposition.
Funktionen wie compose ermöglichen einen Programmierstil auf einem abstrakteren Level, bei dem vermieden wird, explizite Funktionsargumente zu verwenden wird, sondern stattdessen verschiedene Higher-Order Funktionen wie compose verwendet werden (solche Higher-Order Funktionen werden häufig auch Kombinatoren genannt) um Funktionen miteinander zu verknüpfen.
Eine Funktion, die zu ihrem Argument zwei hinzuaddiert, könnten wir im "Point-Free Style" so definieren:
; Number -> Number (define add2 (compose add1 add1))
Der konventionelle Programmierstil, in dem alle Argumente explizit benannt und verwendet werden, wird in diesem Zusammenhang manchmal "Pointful Style" genannt.
15.2 Currying und Typisomorphien von Funktionstypen
Um Klammern zu vermeiden, wird der Funktionspfeil typischerweise als rechtsassoziativ interpretiert, also X -> Y -> Z bedeutet X -> (Y -> Z) und nicht (X -> Y) -> Z.
; [X Y Z] (X Y -> Z) -> X -> Y -> Z (define (curry f) (λ (x) (λ (y) (f x y)))) ; [X Y Z] (X -> Y -> Z) -> X Y -> Z (define (uncurry f) (λ (x y) ((f x) y)))
Beispielsweise können wir eine Funktion zur Addition von 5 zu ihrem Argument definieren als:
; Number -> Number (define add5 ((curry +) 5))
Man kann statt einem nachträglichen Aufruf von curry auch direkt in einer Funktionsdefinition currying betreiben. Die foldr Funktion kann beispielsweise so umformuliert werden, dass die Liste auf der gefaltet werden soll noch nicht direkt als Argument mitgegeben wird sondern stattdessen eine Funktion zurückgegeben wird die auf die Liste wartet.
; [X Y] (X Y -> Y) Y -> (list-of X) -> Y (define (foldr op z) (λ (l) (cond [(empty? l) z] [else (op (first l) ((foldr op z) (rest l)))])))
; (list-of Number) -> Number (check-expect (sum-list (list 2 3 4)) 9) (define sum-list (foldr + 0)) ; (list-of Number) -> Number (check-expect (product-list (list 2 3 4)) 24) (define product-list (foldr * 1))
In der Kategorientheorie werden Funktionstypen verallgemeinert zu sogenannten exponential objects.
Für das Rechnen mit Exponenten kennen wir die gewohnten Gleichungen
XY*Z = XYZ
und
XY+Z = XY * XZ
Die erste Gleichung beschreibt exakt die durch curry und uncurry ausgedrückte Typisomorphie.
Die zweite Gleichung gibt an, dass die Typen Y+Z -> X und (Y -> X) * (Z->X) isomorph sind. Dies ist nicht schwer zu sehen. Wenn ich eine Funktion von Y+Z nach X habe, so kann ich sie offensichtlich als Funktion von Y nach X wie auch von Z nach X verwenden, denn sie kann ja mit beiden Typen von Argumenten umgehen. Umgekehrt kann ich (bei disjunkten Summen) eine Paar von Funktionen (Y -> X) * (Z->X) umbauen zu einer Funktion vom Typ Y+Z -> X, indem ich in der zu erstellenden Funktion prüfe, ob die Eingabe zum linken oder zum rechten Fall gehört und je nachdem die richtige Funktion aus dem Paar aufrufe.
Auch weitere typische Identitäten aus der Algebra können für Typisomorphien verwendet werden. Erinnern Sie sich daran, dass der Typ 1 die Äuivalenzklasse aller Typen mit nur einem Wert ist, der Typ 2 die Äquivalenzklasse aller Typen mit zwei Werten (wie Boolean) ist. Dann gilt
X1 = X
sowie
X2 = X * X
Die erste Isomorphie sagt aus, dass Funktionen von 1 nach X isomorph zu X sind. Da es nur ein mögliches Argument gibt, muss das Resultat jedes Funktionsaufrufs das immer gleiche Element aus X sein.
Die zweite Isomorphie sagt aus, dass der Typ Bool -> X isomorph zu X*X ist. Dies ist nicht schwer zu sehen. Da #true und #false die einzigen möglichen Argumente der Funktion sind, gibt es genau zwei Werte aus X die die Funktion liefern kann. Umgekehrt kann aus einem Paar aus X*X leicht eine Funktion vom Typ Bool -> X gemacht werden: Wenn das Argument #true ist, nimm die erste Komponente des Paars, bei #false das zweite.
15.3 Map, filter, flatmap
Weitere typische Higher-Order Funktionen für den Umgang mit Listen sind map, filter und flatmap. Sie sind wie folgt definiert:
; [X Y] (X -> Y) (list-of X) -> (list-of Y) (define (map f xs) (cond [(empty? xs) empty] [(cons? xs) (cons (f (first xs)) (map f (rest xs)))])) ; [X] (X -> Boolean) (list-of X) -> (list-of X) (define (filter f xs) (cond [(empty? xs) empty] [(cons? xs) (if (f (first xs)) (cons (first xs) (filter1 f (rest xs))) (filter f (rest xs)))])) ; [X Y] (X -> (list-of Y)) (list-of X) -> (list-of Y) (define (flatmap f xs) (foldr append empty (map f xs)))
Die filter Funktion gibt alle Elemente einer Liste zurück, für die eine boolsche Funktion #true ergibt.
> (filter even? (list 1 2 3 4)) '(2 4)
In anderen Sprachen heisst diese Funktion manchmal concatMap oder selectMany. Es gibt eine mächtige Verallgemeinerung der flatmap Funktion durch sogenannte Monaden.
{ (x,y,z) | x in {1..n}, y in {x..n}, z in {x..n}, x*x+y*y = z*z}
In der Sprache Racket (nicht BSL/ISL) kann beispielsweise eine Liste der pythagoreischen Tripel wie folgt berechnet werden:
(define (pyth n) (for*/list ((x (range 1 n 1)) (y (range x n 1)) (z (range x n 1)) #:when (= (+ (* x x) (* y y)) (* z z))) (list x y z)))
; Nat -> (list-of (list-of Nat)) (check-expect (pyth 15) (list (list 3 4 5) (list 5 12 13) (list 6 8 10))) (define (pyth n) (flatmap (λ (x) (flatmap (λ (y) (flatmap (λ (z) (if (= (+ (* x x) (* y y)) (* z z)) (list (list x y z)) empty)) (range y n 1))) (range x n 1))) (range 1 n 1)))
15.4 Konstruktion von Listen mit unfold
Die foldr Funktion von oben abstrahiert das Pattern der strukturellen Rekursion auf Listen, also des Zerlegens (Dekonstruktion) von Listen. Es gibt auch eine "duale" Funktion zur Konstruktion von Listen. Es wird also keine Liste als Eingabe genommen und zerlegt sondern es geht in der unfold Funktion um die Konstruktion von Listen. Man kann sie wie folgt definieren:
; [X Y] (Y -> Bool) (Y -> Y) (Y -> X) Y -> (list-of X) ; (stop (next ... (next seed))) must yield #true after a finite number of iterations (define (unfold stop next emit seed) (if (stop seed) empty (cons (emit seed) (unfold stop next emit (next seed))))) ; Number -> (list-of Number) (check-expect (one-to-n 5) (list 1 2 3 4 5)) (define (one-to-n n) (unfold (λ (m) (> m n)) add1 identity 1))
Ein Beispiel für die Verwendung von unfold sehen wir in der one-to-n Funktion. Die unfold Funktion ist in einem präzisen mathematischen Sinn das "Gegenteil" ("Dual") von foldr, aber das ist nicht Bestandteil dieser Lehrveranstaltung.
15.5 Fold und unfold zusammen, Deforestation
Häufig tritt der Fall auf, dass eine Berechnung in zwei Teile zerlegt werden kann, wobei der erste Teil der Berechnung sein Ergebnis in einer Datenstruktur wie einer Liste zurückgibt und der zweite Teil der Berechnung diese Datenstruktur wieder zerlegt. Häufig können solche Berechnungen als Hintereinanderausführung eines unfolds und eines folds definiert werden. Beispielsweise können wir die Fakultät einer Zahl n berechnen, indem wir zunächst eine Liste mit den Zahlen 1 bis n erzeugen und diese Zahlen dann alle miteinander multiplizieren.
; Nat -> Nat (check-expect (factorial 5) 120) (define factorial (compose product-list one-to-n))
Allerdings ist es in einem gewissen Sinne eine Verschwendung, erst eine Liste zu konstruieren um sie dann sofort wieder auseinanderzunehmen. Techniken, um die Erzeugung solcher temporären Zwischenergebnisse zu verhindern, nennt man oft Deforestation. Für folds und unfolds gibt es eine sehr allgemeine Technik, die Zwischenergebnisse zu überspringen und direkt das Resultat zu erzeugen. Wenn wir uns anschauen, was mit den von unfold erzeugten Listenelementen durch foldr gemacht wird, so sehen wir, dass wir die Argumente von foldr auch sofort auf die von unfold erzeugten Ergebnisse anwenden können, und zwar so:
; [X Y Z] (Y -> Bool) (Y -> Y) (Y -> X) Y (X Z -> Z) Z -> Z (define (unfold-and-fold stop next emit seed op z) (if (stop seed) z (op (emit seed) (unfold-and-fold stop next emit (next seed) op z)))) (define (factorial n) (unfold-and-fold (λ (m) (> m n)) add1 identity 1 + 0))
15.6 Verallgemeinerung von fold und unfold auf beliebige algebraische Datentypen
Die Funktionen foldr und unfold können nicht nur für Listen sondern sogar für beliebige algebraische Datentypen definiert werden. Auch die Idee der Komposition von unfold und foldr sowie der Optimierung durch Deforestation funktioniert für beliebige algebraische Datentypen. Die Verallgemeinerungen diese Konzepte haben beeindruckende Namen: Die foldr Funktion ist ein Catamorphismus, die unfold Funktion ist ein Anamorphismus und die Komposition von unfold gefolgt von foldr Funktion ist ein Hylomorphismus.
Wir wollen anhand eines algebraischen Datentyps für Binärbäume die Verallgemeinerung dieser Konzepte illustrieren.
(define-struct branch (left right)) ; A (tree-of X) is one of: ; - (make-branch (tree-of X) (tree-of X)) ; - X (define a-tree (make-branch (make-branch 3 5) (make-branch 7 8)))
Die fold Funktion für Bäume abstrahiert wie bei Listen das Prinzip der strukturellen Rekursion. Wir verwenden Currying in der Definition von fold-tree um die Funktionen sum-tree und sum-tree im "point-free style" definieren zu können.
; [X Y] (X X -> X) (Y -> X) -> (tree-of Y) -> X (define (fold-tree b l) (λ (t) (match t [(branch left right) (b ((fold-tree b l) left) ((fold-tree b l) right))] [x (l x)]))) ; (tree-of Number) -> Number (check-expect (sum-tree a-tree) 23) (define sum-tree (fold-tree + identity)) ; tree-to-list as fold of the tree ; [X] (tree-of X) -> (list-of X) (check-expect (tree-to-list a-tree) (list 3 5 7 8)) (define tree-to-list (fold-tree append list))
; [X Y] (Y -> Bool) (Y -> Y) (Y -> Y) (Y -> X) Y -> (tree-of X) (define (unfold-tree stop nextl nextr emit seed) (if (stop seed) (emit seed) (make-branch (unfold-tree stop nextl nextr emit (nextl seed)) (unfold-tree stop nextl nextr emit (nextr seed)))))
; Nat -> (tree-of Nat) (check-expect (fib-tree 3) (make-branch (make-branch 1 1) 1)) (define (fib-tree n) (unfold-tree (λ (m) (<= m 1)) sub1 (compose sub1 sub1) (λ (_) 1) n)) ; Nat -> Nat (check-expect (fibonacci 6) 13) (check-expect (fibonacci 7) 21) (define fibonacci (compose sum-tree fib-tree))
Auch für Hylomorphismen auf Bäumen kann "Deforestation" betrieben werden, also die Konstruktion des Bäumes der direkt wieder zerlegt wird kann vermieden werden indem unfold und fold gleichzeitig und synchron das Endergebnis berechnen.
; the argument f of type Y -> Z is the composition of the ; two functions Y->X (from the unfold) and X->Z (from the fold) ; [X Y Z] (Y -> Bool) (Y -> Y) (Y -> Y) (Y -> Z) Y (Z Z -> Z) -> Z (define (unfold-and-fold-tree stop ls rs f seed b) (if (stop seed) (f seed) (b (unfold-and-fold-tree stop ls rs f (ls seed) b) (unfold-and-fold-tree stop ls rs f (rs seed) b)))) ; Nat -> Nat (check-expect (fibonacci2 6) 13) (check-expect (fibonacci2 7) 21) (define (fibonacci2 n) (unfold-and-fold-tree (λ (m) (<= m 1)) sub1 (compose sub1 sub1) (λ (_) 1) n +))
(define (fibonacci seed) (if (<= seed 1) 1 (+ (fibonacci (sub1 seed)) (fibonacci (sub1 (sub1 seed))))))
Am Rande wollen wir erwähnen dass es eine weitere Optimierung der Fibonacci-Funktion gibt, die allerdings nichts mit Deforestation zu tun hat sondern verhindert, dass der Algorithmus Fibonacci-Zahlen mehrfach berechnet und sogar eine exponentielle Laufzeit hat. Ein viel schnellerer Algorithmus um Fibonacci-Zahlen zu berechnen ist dieser:
Erwähnen möchten wir an dieser Stelle jedoch, dass sich der oben stehende Algorithmus auch so umformulieren läßt, dass wir mit Hilfe von unfold effizient eine Liste der ersten n Fibonacci-Zahlen berechnen. Der Zustand in dem unten stehenden unfold ist ein Tripel (kodiert als Liste der Länge 3, wobei die ersten beiden Listenelemente jeweils die beiden vorhergehenden Fibonacci-Zahlen repräsentieren und die das dritte Listenelement zählt wieviele Listenelemente noch erzeugt werden müssen.)
(check-expect (fib2 10) (list 1 1 2 3 5 8 13 21 34 55)) (define (fib2 n) (unfold (lambda (m) (= (third m) n)) (lambda (p) (list (second p) (+ (first p) (second p)) (add1 (third p)))) second (list 0 1 0)))