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, 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.

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 ( );
  • 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 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.
  • rcurry (fun, arg1, arg2, ...) - działa tak jak curry tylko argumenty są zamienione

Przykłady[edytuj]

SML[edytuj]

 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[edytuj]

    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]

(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[edytuj]

(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