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.

Z cyklu funkcje wyższego rzędu, do tej pory ukazały się artykuły:

  1. Funkcje wyższego rzędu
  2. Map i Filter
  3. Fold/Reduce
  4. Currying

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. Mapfunkcje 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. Filterfunkcje 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/Reducefunkcje 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. Curryingfunkcja 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.

3 KOMENTARZE

Comments are closed.