Funkcje wyższego rzędu

W zeszłym tygodniu opowiedziałem o tym czym jest rekurencja i rekurencja ogonowa. Pora przejść do kolejnych podstaw programowania funkcyjnego i nie tylko. Dziś tematem przewodnim będą funkcje wyższego rzędu.

Funkcje wyższego rzędu

Po angielsku, higher-order function, to funkcje które albo jako jeden z parametrów przyjmują funkcję, albo zwracają funkcję.

Czyli w najprostszej postaci w C# byśmy zapisali to tak:

public Func<string> sayHello(string name) 
{
    return () => "Hello, " + name;
}

public static int Mutiple2By(Func<int> getter) 
{
    return 2 * getter();
}

Action<string> sayHello = x => Console.WriteLine("Hello, " + x);
sayHello("Jakub");

Do tego też oczywiście można zaliczyć 90% extension methods od LINQ.

W f# zaś by to wyglądało mniej więcej tak:

let provideTen f = (f 10)
let square x = x * x
printf "%A" (provideTen square)

let sayHello n = fun () -> "hello, " + n
let say = (sayHello "Jakub")

Jak widzicie, mimo, że jest to paradygmat języków funkcyjnych, C# jak najbardziej wspiera higher-order function. Więc wiedza niby funkcyjna a w życiu codziennym się też przyda ;) A jak piszecie w JavaScript to już na pewno, pojęcie funkcji wyższego rzędu powinno być wam znane.

Co prawda w C#, znacznie zostało to uproszczone przez wprowadzenie lambdy. Jednak przed wprowadzeniem lambdy (C# 2.0, w C# 3.0 lambda została wprowadzona), mogliśmy osiągnąć higer-order function za pomocą delegatu, poniższe wyrażenia są równoważne:

// opcja 1, C# >= 2.0
delegate(Foo x) { return x.Size > 10; }

// opcja 2, C# >= 2.0
delegate bool FilterFoo(Foo x);
bool IsOverThen(Foo x) { return x.Size > 10; }

// opcja 3, C# >= 3.0
x => x.Size > 10

W JavaScript to jednak zawsze było dość… banalne:

setTimeout(function() { 
    console.log('hello'); 
}, 5000);

function getValue(f, name) {
   return f(10, name);
}

function sayHello(name) {
   return function () {
       return 'Hello, ' + name;
   };
}

// usage
var say = sayHello('Jakub');
say();
say();

Ogólnie, każdy język który wspiera funkcje jako first-class citizen (typ pierwszoklasowy), wspiera higher-order function. Typ pierwszoklasowy to taki który umożliwia operacje dostępne dla pozostałych bytów. To znaczy może być przypisywany, przekazywany czy też zawracany z funkcji. Jeżeli funkcja jest typem pierwszkoklasowym to się zwie first-class function (funkcją pierwszkolasową).

Trochę to brzmi jak czarna krowa w kropki bordo. Więc mówiąc prościej. Jeżeli możemy zwracać, przypisywać i przekazywać funkcję to znaczy, że jest wspierana funkcja wyższego rzędu. Proste? Proste.

Rodzaje funkcji pierwszego rzędu

Funkcje pierwszego rzędu można podzielić na cztery różne typy:

1. Map – funkcje wyższego rzędu które przyjmują jako parametr funkcję dokonującą transformacji danego elementu. Funkcje wyższego rzędu zwracają zazwyczaj listę elementów.
2. Filter – funkcje wyższego rzędu które przyjmują jako parametr funkcję wybierającą określone elementy z listy. Funkcje wyższego rzędu zwracają zazwyczaj listę elementów.
3. Fold/Reduce – funkcje wyższego rzędu które mają za zadanie zwrócenie jakieś z akumulowanej wartości po tym jak przeszły listę w określony sposób.
4. Currying – funkcja wyższego rzędu która złożoną wieloargumentową funkcję zamienia na listę funkcji przyjmujących po jednym argumencie i zwracającą na koniec oryginalną funkcję. Pogmatwane ;) ale postaram się to wytłumaczyć prościej.

Przez kolejne tygodnie (albo może nawet dni, zobaczę jak mi czasu starczy) będę zajmował się poszczególnymi rodzajami funkcji wyższego poziomu. Dlaczego to rozbijam? Z kilku ważnych powodów, po pierwsze istnieje coś takiego co się zwie cognative backlog o czym będę chciał napisać w niedzielę. Po drugie, naprawdę ciężko jest znaleźć 3-4h by opisać to na raz :) Więc zamiast czekać jak będzie całość, będę udostępniał kolejne etapy – czy to będzie jeden post czy może 2-3 zobaczymy. Tak chyba będzie fair?

Teraz, zanim zakończymy, wspomniałem o lambda… no właśnie.

Lambda

Co to jest ta lambda? W skórcie można powiedzieć, że jest to funkcja anonimowa. No ale jak to ze skrótami bywa ;) Ogólnie, funkcja anonimowa to taka, która nie jest przypisana do żadnej zmiennej, w niektórych językach można nawet powiedzieć nie jest z boundowana do identyfikatora/aliasu/zmiennej. Nie ważne jak to nazwać. Chodzi o to, że funkcja nie ma reprezentacji w postaci jakieś zmiennej. Czyli aby to było możliwe, funkcja musi zostać przekazana jako parametr lub zwrócona jako wynik działania innej funkcji.

Funkcje anonimowe, bazują na lamba calculus (λ-calculus) – w dużym skrócie: formalny system zapisu operacji w postaci abstrakcyjnej funkcji, gdzie wszystkie funkcje są anonimowe. To właśnie od lambda claculus pochodzi wyrażenie lambda czy w ogóle określenie lambda w informatyce.

Zapis językowy komputerowy przeważnie wygląda tak:

// c#
x => x // zwraca siebie samego
x => x*2 // zwiększa wartość dwukrotnie

// f#
fun x -> x * 2
fun x -> x

// w f# można to jeszcze wywołać:
(fun x-> x*2) 2 // 4
(fun x-> x) 2 // 2

I na tym zakończę pisanie co to takiego. Matematykiem nie jestem, wywodów matematycznych ciągnąć też nie będę. Ważne by zrozumieć, że lambda którą my mamy w programowaniu wywodzi się z lambda calculus i ma ona spełniać pewne określone zasady.

Podsumowanie

Dzisiaj było trochę dużo podstaw, ale są one potrzebne do tego by zrozumieć kolejne elementy. To wszystko naprawdę łączy się w całość, rekurencja, rekurencja ogonowa, funkcje wyższego poziomu itd. Materiału trochę jest ale zrozumienie tego spowoduje, że będziemy lepszymi programistami. W skrócie: 6 strony A4 tekstu załatwi nam podstawy i da wiedzę do wykorzystanie świadomego parydygmatów programowania funkcyjnego w językach nie tylko funkcyjnych.