Funkcja wyższego rzędu

Funkcja wyższego rzędu (ang. higher-order function) - w informatyce jest to funkcja, która zwraca albo przyjmuje jako argument inne funkcje. Tego rodzaju funkcje są powszechnie stosowane w językach funkcyjnych, jak SML, Ocaml, Haskell, jak także w Pythonie oraz Javascripcie. Aby da się było tworzyć funkcje wyższego rzędu, funkcje muszą być typem pierwszoklasowym.

Funkcje wyższego rzędu służą wielokrotnie 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 ( );
• 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 ( );
• 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 jest 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.
• rcurry (fun, arg1, arg2, ...) - działa tak jak curry tylko argumenty są zamienione

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

Javascript

    function map(fun, array) {
        var result = ;
        var len=array.length;
        for (var i=0; i<len; ++i) {
            result.push(fun(arrayi));
        }
        return result;
    }
 
    function curry(fn, scope) {
        var scope = scope || window;
        var args = ;
        for (var i=2, len = arguments.length; oraz < len; ++i) {
            args.push(argumentsi);
        };
        return function() {
             fn.apply(scope, args);
        };
    }
 
    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 (> oraz 0)
          (begin
            (apply fun args)
            (iter (- oraz 1)))))))
 
(define ten-times (repeater 10))
 
(ten-times (curry display "hello"))

Funkcje wyższego rzędu potrafią także 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ę oraz 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 = []         *)

Sprawdź też

• currying
• domknięcie
• funkcjonał