Funkcje wyższego rzędu: Fold/Reduce

Kontynuujemy serię postów na temat funkcji wyższego rzędu. Tym razem na tapetę trafia funkcja fold, która w zależności od języka i parametrów wejściowych może nosić różne nazwy jak: reduce, inject czy accumulate. O różnicach kiedy w języku występuje fold jak i reduce opowiem póżniej.

Fold

Fold to nic innego jak, przechodzenie przez dane (głównie listy) i budowanie wyniku końcowego, który jest tworzony przez funkcję przekazaną w parametrze… brzmi skomplikowanie? Ale tak nie jest.

Fold to funkcja, która przyjmuje jako parametry listę elementów, funkcję która ma zostać wykonana na wszystkich elementach oraz wartość początkową – niezależnie czy to będzie zerowy licznik, czy stan czy coś innego. Nie podanie tego powoduje iż zostanie wykorzystany pierwszy element z danych wejściowych jako wartość inicjalizująca.

Możemy wyróżnić dwa rodzaje foldów, left i right.

Left Fold

Left fold jest bardzo prostym foldem, który możemy napisać wykorzystując na przykład pętle foreach:

var result = 0;
var fun = (r, e) => r+e;
foreach(var x in Enumerable.Range(1,9))
{
    result = fun(r, x);
}
Console.WriteLine(result);

Fold, ten sumuje wszystkie elementy w liście. I możemy go rozpisać jako:

(((((0 + 1) + 2) + 3) + 4) + 5)

Gdzie 0 to jest nasza wartość początkowa.

Left fold zwie się tak, gdyż idziemy od lewej do prawej przy sumowaniu. Czyli najpierw musimy wykonać 0 + 1 by móc wykonać + 2. Upraszczając można powiedzieć, że left fold to nic innego jak pętla działająca na liście.

Tak naprawdę, za pomocą left fold jesteśmy wstanie bardzo dużo funkcjo napisać – sum, count, avg, reverse, unique, contains, last, product itp. Trzeba tylko o jednej rzeczy pamiętać, fold to funkcja wyższego rzędu, a więc funkcja która albo zwraca funkcję, albo przyjmuje funkcję jako parametr wejściowy.

W C# mamy dostępną metodę Aggregate która spełnia założenia left fold

Enumerable
    .Range(1, 9)
    .Aggregate(0, (x,y) => x + y);

Tak samo możemy zrobić policzyć avg:

var numbers = Enumerable.Range(1, 9);
decimal average = numbers.Aggregate(
    seed: 0,
    func: (result, item) => result + item,
    resultSelector: result => (decimal)result / numbers.Count());

Warto zwrócić uwagę, że funkjca Sum i Avarge które są dostępne jako rozszerzenia w LINQ, nie są funkcjami wyższego rzędu więc też nie są to funkcje typu fold.

W F# mamy zaś funkcję fold:

[1..9] |> List.fold (fun acc elem -> acc + elem) 0

[1..9]
|> List.fold (fun (sum,len) x -> (sum + x, len + 1)) (0,0)
|> (fun (sum,len) -> sum / len)

Ciekawostka: W Event Store, aktualny stan jest reprezentowany jako left fold wszystkich poprzednich stanów.

f(f(f(initial()), e), e), e)

Gdzie:

• initial() to stan początkowy
• e to zdarzenie
• f to funkcja zwracająca stan po aplikacji danego zdarzenia

Right Fold

Right fold to nic innego jak odwórcona kolejność wykonywania left fold. Czyli nasz prosty przykład pętli i dodawania, powinien dać taki o to wynik

(1 + (2 + (3 + (4 + (5 + 0)))))

A więc idziemy od prawej do lewej strony.

Jakbyśmy mieli sami stworzyć sobie taki right fold to wyglądałby on tak:

var result = 0;
var fun = (r, e) => r+e;
var list = Enumerable.Range(1, 9);
for(int i = list.Count(); i < 0; i--)
{
    var x = list[i];
    result = fun(r, x);
}
Console.WriteLine(result);

Albo można to jeszcze bardziej uprościć:

var result = 0;
var fun = (r, e) => r+e;
foreach(var x in Enumerable.Range(1,9).Reverse())
{
    result = fun(r, x);
}
Console.WriteLine(result);

Stosując metodę Reverse ;)

No ale takie wyjście nie koniecznie jest najlepsze. Jednak jest możliwe. W C# nie ma implementacji right fold jako takiej, ale możemy wykorzystać implementację left fold do zrobienia right fold… ;)

W skrócie, w zależności co chcemy osiągnąć, możemy nasze sumowanie zapisać następująco:

Enumerable
   .Range(1, 9)
   .Aggregate<int, Func<int,int>>(
       seed: x => x,
       func: (f, n) => x => f(x + n)
    )(0);

Seed to nasz akumulator, nasz stan, nasz wynik. Czyli jest to funkcja która przyjmuje wartość i ją zwraca. Zaś naszym celem jest zbudowanie czegoś takiego:

f(1 + f(2 + f(3 + f(4 + f(5 + f(0))))))

Func zaś to funkcja, która umożliwi nam zbudowanie WARTOŚĆ + f(x).

Zapisanie tego w postaci pętli wyglądało by tak:

Func<int, int> result = x => x;
Func<Func<int, int>, int, Func<int, int>> fun = (f, n) => (x => f(x + n));
foreach(var x in Enumerable.Range(1,9))
{
    result = fun(result, x);
}
Console.WriteLine(result(0));

Niezły mózgojeb? :) ale mamy tak jak chcieliśmy :) A jak chcecie długie wytłumaczenia dojścia do tej formułki, to może ten artykuł wam pomoże – na końcu jest fajna funkcj zrobiona, która umożliwia zapis ten metody w postaci “czytelnej”.

Jeżeli zaś chcemy to samo zapisać w F# to mamy metodę foldBack ;) więc jest duuuużo łatwiej ;)

[1..9] |> List.foldBack (fun acc elem -> acc + elem) 0

Right vs Left

Nie licząc przypadków granicznych (patrz podsumowanie), to czy wykorzystamy left czy right zależy głównie od tego jak chcemy by nasze “nawiasy” działały.  Na przykład dodawanie i wartości ujemne, albo odejmowanie i wartości ujemne. Czyli ogólnie, kolejność z jaką chcemy obrabiać elementy decyduje o tym jaki fold mamy użyć.

Reduce

PS.: tak cały ten punkt powstał ze względu na F# :)

W językach funkcyjnych reduce czasami występuje jako funkcja wyższego rzędu, która różni się tym od fold, że nie przyjmuje wartości początkowej. To znaczy, że wynikiem reduce musi by typ danych elementów listy. Gdzie w fold typem danych zwracanych będzie ten który jest przekazywany jako wartość początkowa. Dokładniej reduce bierze pierwszy element listy, jako wartość początkowa.

Nie jest to regułą! I przeważnie reduce == fold. Jednak w f# tak nie jest i reduce zachowuje się tak jak napisałem wyżej. Do tego, reduce zwróci wyjątek jeżeli podacie pustą listę jako parametr wejściowy. W C# rozszerzenie Aggregate jest przeciążone tak, że może przyjąć wartość początkową lub nie. Warto więc o tym wiedzieć, w szczególności jak piszemy w F# ;)

W F# zapiszemy nasze sumowanie tak:

[0..9] |> List.reduce(fun acc elem -> acc + elem)

W C# tak:

Enumerable
   .Range(0, 10)
   .Aggregate((x,y) => x + y);

Podsumowanie

Nie taki fold straszny jak go malowano :) Oczywiście, są przypadki graniczne w których na przykład right fold sprawdzi się lepiej od left fold i vice versa. Jednak są to przypadki… lazy loading i nieskończona lista gdzie left fold może działać w nieskończoność. No ale nic nie jest idealne ;)

To co warto zapamiętać, to:

• Fold zwraca wynik który jest rezultatem wykonania funkcji na wszystkich elementach listy.
• Istnieją dwa rodzaje foldów, left i right.
  • Left można traktować jako petle po elementach (czy przez rekurencje czy przez pętle)
  • Right to inaczej rekurencja po elementach, lub przechodzenie od początku listy (czy prze rekurencje czy przez pętle)
• Reduce to jest to samo co fold i przeważnie istnieje jedno nazewnictwo chyba, że mówimy o F#

Jeszcze pozostała jedna funkcja do opisu, z tych które wymieniłem w pierwszym artykule – funkcje wyższego rzędu. Więc do przeczytania niebawem :)