WikiClone

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.

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.

Przykład ich wykorzystania w SML-u:

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 w przykładowym programie map 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 = []         *)

[edytuj] Zobacz też

• currying
• domknięcie