Funkcja wyższego rzędu

Funkcja wyższego rzędu (ang. higher-order function) – w informatyce jest to funkcja, która zwraca lub przyjmuje jako argument inne funkcje^[1]. Tego rodzaju funkcje są powszechnie stosowane w językach funkcyjnych, takich jak SML, Ocaml, Haskell, Lisp, jak również w Pythonie i JavaScripcie. Aby można było tworzyć funkcje wyższego rzędu, funkcje muszą być typem pierwszoklasowym. Analogicznym pojęciem w matematyce jest funkcjonał.

Funkcje wyższego rzędu służą często do dostarczenia generycznych realizacji algorytmów, zaś programista parametryzuje je własnymi funkcjami (nierzadko bardzo prostymi, patrz przykład niżej). W bibliotekach standardowych są spotykane:

map (funkcja, lista) – zwraca nową listę, zawierającą wyniki funkcji dla każdego elementu z wejściowej listy ( $[x_{1},x_{2},\dots ,x_{n}]$ ${}\quad \to \quad {}$ $[f(x_{1}),f(x_{2}),\dots ,f(x_{n})]$ );
filter (funkcja, lista) – zwraca nową listę, składającą się tylko z tych elementów listy wejściowej, dla których funkcja (predykat) zwróciła prawdę;
foldl (wartość początkowa, funkcja, lista) (fold left) – dla wszystkich elementów listy wywoływana jest funkcja, która przyjmuje dwa argumenty – wartość z listy, oraz wynik dla poprzedniego elementu ( $x_{0},[x_{1},x_{2},\dots ,x_{n}]$ ${}\quad \to \quad {}$ $f(f(f(x_{0},x_{1}),x_{2})\ldots x_{n})]$ );
foldr (wartość początkowa, funkcja, lista) (fold right) – działanie analogiczne do foldl, z tym że lista jest przeglądana od końca;
reduce (funkcja, list) – funkcja występuje w Pythonie działa jak foldr z wartością początkową jako pierwszy element listy;
curry (fun, arg1, arg2, ...) – zwraca nową funkcję która przyjmuje początkowe wartości przekazane jako argumenty. $curry(f,x_{0},x_{1},\dots x_{n})=(y_{0},y_{1},\dots y_{n}\to (f,x_{0},x_{1},\dots x_{n},y_{0},y_{1},\dots y_{n}));$
rcurry (fun, arg1, arg2, ...) – działa tak jak curry tylko argumenty są zamienione $rcurry(f,x_{0},x_{1},\dots x_{n})=(y_{0},y_{1},\dots y_{n}\to (f,y_{0},y_{1},\dots y_{n},x_{0},x_{1},\dots x_{n})).$

Przykłady

SML

 fun kwadrat x = x*x;                        (* funkcja podnosząca do kwadratu *)

 val L = '''map''' kwadrat [1,2,3,4,5];            (* L = [1,4,9,16,25] *)

 fun niezerowe x = x <> 0;                   (* funkcja zwraca prawdę gdy x nie jest zerem *)

 val L = '''filter''' niezerowe [0,1,0,0,5,0,0,0]; (* L = [1,5] *)

 fun suma (x, y)    = x+y;                   (* funkcja zwraca sumę dwóch liczb *)
 fun iloczyn (x, y) = x*y;                   (* ta natomiast iloczyn  *)

 val S = '''foldl''' suma    0 [1,2,3,4,5];        (* S = 0+1+2+3+4+5 = 15  *)
 val I = '''foldl''' iloczyn 1 [1,2,3,4,5];        (* I = 1*1*2*3*4*5 = 120 *)

Funkcje wyższego rzędu mogą również zwracać inne funkcje, co jest wykorzystywane m.in. w curryingu, czyli transformacji funkcji w taki sposób, żeby zamiast przyjmowania ciągu argumentów (krotki), przyjmowała tylko jeden, pierwszy argument, oraz zwracała funkcję przyjmującą kolejne argumenty. Np. w wyliczeniu funkcji podano, że funkcja map przyjmuje dwa argumenty (krotkę dwuelementową): funkcję oraz listę; natomiast map SML-owe w istocie przyjmuje jeden argument – funkcję użytkownika, zwraca zaś funkcję przyjmującą jako argument listę i to dopiero ona zwraca ostateczny wynik obliczeń:

 val NZ = '''map''' niezerowe;                     (* NZ jest funkcją *)
 val L1 = NZ [0,1,0,0,5,0,0,0];              (* L1 = [1,5]      *)
 val L2 = NZ [0,0,0,0];                      (* L2 = []         *)

JavaScript

    function map(fun, array) {
        var result = [];
        var len=array.length;
        for (var i=0; i<len; ++i) {
            result.push(fun(array[i]));
        }
        return result;
    }
    
    function curry(fn) {
        var args = [].slice.call(arguments, 1);
        return function() {
           return fn.apply(null, args.concat([].slice.call(arguments)));
        };
    }
    
    function add(x, y) {
        return x+y; 
    }
    
    map(curry(add, 10), [1, 2, 3, 4, 5]);
    
    => [11, 12, 13, 14, 15]

Scheme

(define (curry fun . args)
  (lambda more-args
    (apply fun (append args more-args))))

(define (reduce fun lst)
  (let iter ((result (car lst))
	     (lst lst))
    (if (null? (cdr lst))
	result
	(iter (fun result (cadr lst)) (cdr lst)))))

(define (repeater n)
  (lambda (fun . args)
    (let iter ((i n))
      (if (> i 0)
          (begin
            (apply fun args)
            (iter (- i 1)))))))

(define ten-times (repeater 10))

(ten-times (curry display "hello"))

Clojure

(defn częściowe-zastosowanie
  "Zwraca funkcję, która wywołuje podaną funkcję, przekazując jej wszystkie
  argumenty i pozwalając na przekazawanie podczas wywoływania opcjonalnego,
  dodatkowego argumentu. BARDZO CZĘSTO MYLONA Z ROZWIJANIEM (CURRYING)!"
  ([f] f)
  ([f arg1 & more] (fn [& args] (apply f arg1 (concat more args)))))

(defn potwarzaj
  "Zwraca funkcję, która będzie wywoływała przyjmowaną jako argument funkcję
  tyle razy, co podana jako pierwszy argument liczba. Wywoływanej funkcji
  będzie przekazywany numer wywołania jako pierwszy i jedyny argument."
  [nr]
  (fn [f]
    (loop [c nr]
      (when-not (zero? c)
        (f c)
        (recur (dec c))))))

(def czterokrotnie (potwarzaj 4))
(def wypisz-siema (częściowe-zastosowanie println "siema"))

(czterokrotnie wypisz-siema)

; >> siema 4
; >> siema 3
; >> siema 2
; >> siema 1
; => nil

Powyższe funkcje dla uproszczenia przykładów, wywołują funkcje zwracaną przez curry od razu po wywołaniu wynikowej funkcji. Poprawną funkcją curry (tak zazwyczaj jest ona zaimplementowana w bibliotekach w różnych językach) powinno być zwracanie funkcji, dopóki liczba argumentów nie jest równa lub większa liczbie argumentów funkcji przekazanej jako argument. W przypadku funkcji, która przyjmuje dowolną liczbę argumentów zakłada się, że jest to zero. Czyli poprawna funkcji curry (w języku JavaScript) powinna się zachowywać tak:

function add(a, b, c, d) {
   return a + b + c + d;
}
var fn_1 = curry(add, 1);
var fn_2 = fn_1(2, 3);
var v = fn_2(4);
// v == 10

Poniżej funkcja curry w języku JavaScript, która spełnia ten warunek:

function curry(fn) {
  var init_args = [].slice.call(arguments, 1);
  var len = fn.length;
  return function() {
    var args = init_args.slice();
    function call() {
      args = args.concat(to_array(arguments));
      if (args.length >= len) {
        return fn.apply(null, args);
      } else {
        return call;
      }
    };
    return call.apply(null, arguments);
  };
}

W języku Scheme funkcja + przyjmuje dowolną liczbę argumentów, czyli w scheme curry powinno zwracać funkcje dwa razy, gdy przekażemy funkcje + do "poprawnej" funkcji curry:

(define fn (curry + 1))
(display (fn 2))
;; 3
(display (fn 2 3 4))
;; 10

To wymaganie (dla funkcji +) będzie spełnione dla dowolnej funkcji curry z tego artykułu.

Przypisy

↑ Simpson 2020 ↓, s. 30.

Bibliografia

Kyle Simpson: JavaScript funkcyjnie. Wydawnictwo Naukowe PWN, 2020. ISBN 83-01-21196-2.

[CITEREFSimpson202030-1] Simpson 2020 ↓, s. 30.

[1]