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 (${\displaystyle [x_{1},x_{2},\dots ,x_{n}]}$ ${\displaystyle {}\quad \to \quad {}}$ ${\displaystyle [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 (${\displaystyle x_{0},[x_{1},x_{2},\dots ,x_{n}]}$ ${\displaystyle {}\quad \to \quad {}}$ ${\displaystyle 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. ${\displaystyle 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 ${\displaystyle 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

 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 *)

 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 = []         *)

    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]

(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"))

(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

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

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);
  };
}

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

Przypisy

Bibliografia

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