Funkcja wyższego rzędu

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

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, \ldots, x_n] \quad\rightarrow\quad [f(x_1), f(x_2), \ldots, 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, \ldots, x_n] \quad\rightarrow\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, \ldots x_n) = (y_0, y_1, \ldots y_n\rightarrow(f, x_0, x_1, \ldots x_n, y_0, y_1, \ldots y_n))
  • rcurry (fun, arg1, arg2, ...) - działa tak jak curry tylko argumenty są zamienione rcurry(f, x_0, x_1, \ldots x_n) = (y_0, y_1, \ldots y_n\rightarrow(f, y_0, y_1, \ldots y_n, x_0, x_1, \ldots x_n))


Przykłady[edytuj | edytuj kod]

SML[edytuj | edytuj kod]

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

Javascript[edytuj | edytuj kod]

    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, scope) {
        var scope = scope || this;
        var args = [];
        for (var i=2, len = arguments.length; i < len; ++i) {
            args.push(arguments[i]);
        };
        return fn.apply(scope, args);
    }
 
    function add(x, y) {
        return x+y; 
    }
 
    map(function(x) { return curry(add, this, 10, x)}, [1, 2, 3, 4, 5]);
 
    => [11, 12, 13, 14, 15]

Scheme[edytuj | edytuj kod]

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


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

Zobacz też[edytuj | edytuj kod]