Higher Order Function : Przykłady Funkcji wyższego rzędu w C#

OrderCzęść NR.11 Czy wiesz, że mam na tym blog kurs Funkcyjnego programowania w C#. Dawno go nie odświeżałem, a wraz z pojawieniem się C# 9.0 myślę, że warto robi wpisy, które potrafią przełożyć filozofię funkcyjnego programowania na C#.  A sam C# tak jak przewidziałem na początku tego kursu będzie się zbliżał do trendów funkcyjnego programowania i brał pomysły z F#.

Dzisiaj po wielkim powrocie omówimy Funkcje wyższego rzędu (Higher-order function).

Jak wpiszesz "funkcje wyższego rzędu" do Google to zgłoszą Ci języki jak : Python, JavaScript. A jak to ma wyglądać w C#.

Funkcje wyższego rzędu są filarem funkcyjnego programowania.  Są to funkcje, które biorą albo inne funkcje jako parametry, albo zwracają nowe funkcję, które mogą być tworzone dynamicznie.

Wiele języków wspiera tą filozofię bez problemu tylko zawsze jest problem z tym dynamicznym tworzeniem funkcji. Na przykład w C jest możliwe przesłanie wskaźnika do funkcji, ale nie masz możliwości dynamicznego tworzenia nowej funkcji.

Tak samo było z C# w wersji 1, gdzie miałeś tylko delegaty i one były wskaźnikiem do metody. W C# 2.0 pojawiły się anonimowe metody, a w C# 3.0 pojawiły się wyrażenia lambda. Czy możemy tworzyć nowe funkcje wywołując funkcję? Na razie nie poruszę tej kwestii w tym wpisie. Na pewno w C#  mamy funkcję, które przyjmują inne funkcję.

Najlepiej to wykazać na przykładzie standardowych funkcji wyższego rzędu. Wiem, że takie standardu nie ma, ale się przyjęło, że pewne metody są fantastycznym przykładem takich funkcji.

Są to trzy funkcje:

• Map
• Filter
• Fold

Te funkcje istnieją już w wielu językach i nawet w .NET one istnieją jako metody LINQ. Każda z tych funkcji pracuje nad listą elementów i używa do niej funkcji, która jest przesłana w jej wywołaniu.

Zobaczmy jak Map,Filter, Fold są zaimplementowane przy pomocy LINQ i FCslib. Dla przypomnienia FCslib to biblioteka pomysłów z F# przełożony na język C#.

Map

Funkcja mapowania jest bardzo prosta i często jest ona blokiem w programowaniu funkcyjnym. Map bierze listę elementów i funkcje, którą ma wywołać przy każdym elemencie. Buduje ona w ten sposób nową listę elementów, która jest rezultatem tej transformacji. 

Używając iteratora i słowa kluczowego yield możesz taką metodę łatwo napisać. Tak samo ona jest stworzona w bibliotece FCslib

static IEnumerable<R> Map<T, R>(Converter<T, R> function, IEnumerable<T> list)
{
    foreach (T sourceVal in list)
        yield return function(sourceVal);
}

Converter<T,R> jest funkcją, którą ma otrzymać coś typu T i zwrócić typ R. Czyli mapujemy.

To niesamowite, że ten kod działa z wyrażeniem lambda w taki sposób. Mogę np. zrobić listę nazw gier z kolekcji obiektów gier.

static void Main(string[] args)
{
    var games = new List<Game>()
    { new Game() {Name="Mortal Kombat"}};

    var names = Map(p => p.Name, games);
}

static IEnumerable<R> Map<T, R>(Converter<T, R> function, IEnumerable<T> list)
{
    foreach (T sourceVal in list)
        yield return function(sourceVal);
}

public class Game
{
    public string Name { get; set; }
}

Mogę też łatwo zrobić wyrażenia matematyczne.

var squares = Functional.Map(i => i * i, Enumerable.Range(1, 10));
var squares2 = Map(i => i * i, Enumerable.Range(1, 10));

Chociaż pracując z LINQ zapewne wiesz, że podobne mapowanie możesz zrobić używając metody select.

var squares3 = Enumerable.Range(1, 10).Select(i => i * i);

Czyli nasza metoda SELECT jest funkcją wyższego rzędu. Chociaż na razie te przykłady nie zwracają dynamicznych funkcji.

Filter

Filter jest funkcją, którą dodaje kryterium do istniejącej listy. Te kryterium jak zgadłeś jest funkcją samą w sobie i jest ona wywoływana przy każdy elemencie listy. Implementacja tej metody w FCSlib wygląda tak:

public static IEnumerable<T> Filter<T>(Predicate<T> predicate,
    IEnumerable<T> list)
{
    foreach (T val in list)
        if (predicate(val))
            yield return val;
}

Naszą funkcja jest Predicate<T>,  zwraca ona logiczną wartość. Jeśli mamy prawdę to zwracamy element, jeśli nie to go pomijamy. Oto filtracja

static void Main(string[] args)
{
    var games = new List<Game>()
    { new Game() {Name="Mortal Kombat"}};

    var namesHavingM = Filter(p => p.Name.Contains("M"), games);

}

public static IEnumerable<T> Filter<T>(Predicate<T> predicate,
    IEnumerable<T> list)
{
    foreach (T val in list)
        if (predicate(val))
            yield return val;
}

public class Game
{
    public string Name { get; set; }
}

Wiem co mi chcesz powiedzieć ...przypadkiem metoda WHERE z Linq nie działa podobnie?

games.Where(p => p.Name.Contains("M"));

Zaraz Ci udowodnię, że korzystasz z funkcji wyższego rzędu nawet o tym nie wiedząc. Wiem na razie nie rozwalam twojego świata. Pora spojrzeć na Fold.

Fold

Fold jest...zaraz co to jest. Fold to "zagięcie"? Fold ma wiele zastosowań i istnieje fold prawostronny i lewostronny. Najpierw zobaczmy jak wygląda fold od lewej strony i w sumie co te zagięcie robi.

Pobierzemy w tej funkcji 3 parametry : funkcję akumulacyjną, startową wartość oraz listę. W przeciwieństwie do innych funkcji tutaj nie zwróci listy. Zwrócimy tutaj jedną wartość, czyli zagniemy listę w formie jakieś kumulacji  i zwrócimy jeden element.

Aby to zrobić nasza metoda Fold przejdzie po elementach i będzie wywoływać funkcję akumulacyjną, która przyjmie wartość poprzednią tej funkcji i wartość elementu listy.

Przy pierwszy uruchomieniu nie ma poprzedniej wartości więc mamy wartość startową, którą podajemy.

Oto implementacja tej funkcji z FCSlib.

public static R FoldL<T, R>(Func<R, T, R> accumulator, R startVal,
    IEnumerable<T> list)
{
    R result = startVal;
    foreach (T sourceVal in list)
        result = accumulator(result, sourceVal);
    return result;
}

A wywołanie wygląda tak:

var sumOf1to100 = FoldL((r, v) => r + v, 0,
Enumerable.Range(1, 100));

Wyrażenie (r,v) => r + v jest naszą funkcją akumulacyjną. "r" jest poprzednią wartością wyniku tej funkcji, a "v" wartością obecną z listy. Liczenie zaczynamy od 0.

Mamy więc wyrażenie :  0 + 1 + 2 + 3 + 4 + 5...+ 99 + 100 

Wartość początkowa ma znaczenie. Gdybyś chciał np. zrobić mnożenie w tej sekwencji to logiczne by było zacząć od 1. Przy okazji uświadomiłem sobie, że to jest silnia.

var silnijaz7 = FoldL((r, v) => r * v, 1,
Enumerable.Range(1, 7));

Jak widzisz mam tutaj proste algorytmy matematyczne.  Kto też powiedział, że musisz pracować z jedną wartością na raz. Oto przykład wyliczenia przeciętnego wieku ludzi.

Jedna wartość sumuje mi liczbę ludzi, a druga wartość sumuje mi ich wiek. Potem dziele jedną wartość przez drugą i ma przeciętną. 

static void Main(string[] args)
{
    var people = new List<Person>()
    {
        new Person() {Name = "A", Age = 21},
        new Person() {Name = "B", Age = 22},
        new Person() {Name = "C", Age = 23},
        new Person() {Name = "D", Age = 24},
        new Person() {Name = "E", Age = 25},
        new Person() {Name = "F", Age = 19},
        new Person() {Name = "G", Age = 20},
        new Person() {Name = "H", Age = 21},
        new Person() {Name = "I", Age = 21},
        new Person() {Name = "J", Age = 22},
        new Person() {Name = "K", Age = 24},
    };

    var acc = FoldL((r, v) => Tuple.Create(r.Item1 + v.Age, r.Item2 + 1),
        Tuple.Create(0, 0),
        people);

    var averageAge = (double)acc.Item1 / (double)acc.Item2;


}
public class Person
{
    public string Name { get; set; }

    public int Age { get; set; }
}


public static R FoldL<T, R>(Func<R, T, R> accumulator, R startVal,
    IEnumerable<T> list)
{
    R result = startVal;
    foreach (T sourceVal in list)
        result = accumulator(result, sourceVal);
    return result;
}

Tuple istnieją od C# 4.0 i wiesz mi od tamtego czasu rozwinęły się trochę bardziej. 

Różnica pomiędzy Fold a poprzednimi funkcjami jest taka, że zwraca ona jeden obiekt.  Jednakże skoro ten obiekt może być np. Tuple, czyli zwracać dwie wartości to oznacza, że jeden obiekt zwracany przez Fold może być też listą.

Wiem, ale spójrz na ten kod.

var cloneList = FoldL((r, v) =>
{
    r.Add(v);
    return r;
},
new List<int>(),
Enumerable.Range(1, 5).ToList());

R jest listą, którą ciągle uzupełniam, a V jest elementem istniejącej już listy. Mówiąc krótko ta funkcja kopiuje wartości jednej listy na drugą.

Istnieje też tutaj mały szkopuł, bo ciągle operuje na tej samej liście, a w prawdziwym programowaniu funkcyjnym lista byłaby niezmienna i bym nową listę w każdej iteracji takiego algorytmu. 

Mógłbym to rozwiązać w taki sposób, ale chodzi o sprawienie by sama lista była typem niezmiennym. 

var cloneList = FoldL((r, v) =>
{
    var newList = new List<int>();
    newList.AddRange(r);
    newList.Add(v);
    return newList;
},
new List<int>(),
Enumerable.Range(1, 5).ToList());

Dodatkowo pokaże ci co można zrobić z funkcją fold .Oto implementacja Map i Filter.

public static IEnumerable<R> FoldMap<T, R>(Converter<T, R> converter,
    IEnumerable<T> source)
{
    return FoldL(
    (r, v) =>
    {
        var newList = new List<R>();
        newList.AddRange(r);
        newList.Add(converter(v));
        return newList;
    },
    new List<R>(), source);
}

public static IEnumerable<T> FoldFilter<T>(Predicate<T> predicate,
IEnumerable<T> source)
{
    return FoldL(
    (r, v) =>
    {
        var newList = new List<T>();
        newList.AddRange(r);
        if (predicate(v))
            newList.Add(v);
        return newList;
    },
    new List<T>(), source);
}


public static R FoldL<T, R>(Func<R, T, R> accumulator, R startVal,
    IEnumerable<T> list)
{
    R result = startVal;
    foreach (T sourceVal in list)
        result = accumulator(result, sourceVal);
    return result;
}

A jaka jest różnica pomiędzy lewostronną, prawostronną funkcją fold? Wyobraź sobie, że mamy przestawioną kalkulacje sumy w taki sposób.

Func<int, int, int> su = (r, x) => r + x;
var sum = FoldL(su, 0, Enumerable.Range(1, 4));

Func<int, int, int> mi = (r, x) => r - x;
var minustwo = Functional.FoldR(mi, 0, Enumerable.Range(1, 4));
var minusten = FoldL(mi, 0, Enumerable.Range(1, 4));

Ta kalkulacja ostatecznie wygląda tak : su(su(su(su(0,1),2),3),4)

Dla prawostronnego fold wyglądałoby to tak su(1,su(2, su(3, su(4,0))))

Liczby są dodawane według określonej kolejności od lewej do prawej. Co więcej, kolejność nie ma znaczenia, ponieważ tutaj dodajemy. Jednak dla innych równań byłoby inaczej.

Dla funkcji "mi" - Fold lewostronny będzie wyglądać  tak : ((0 - 1) - 2) - 3) - 4) = -10

Dla funkcji "mi" - Fold prawostronny będzie wyglądać tak :  1 - (2 - (3 - (4 - 0))) = -2

Czyli dla Fold-a prawostronnego akumulator działa od końca od ostatniej wartości z listy z parametrów. Jakbyś się zastanawiał jak FoldR działa w FCSlib to jego sekret polega na odwróceniu kolejności i robi to poprzez umieszczenie elementów na stosie. Jak pamiętasz ostatni element dodany do stosu wyjdzie jako pierwszy.

Stos ten pozwala mu wyciągnąć ostatni element naszej listy jako pierwszy, czyli zrobić wywoływanie funkcji od końca. Myślisz, że żartuje, ale kod tak wygląda :

public static IEnumerable <T> Reverse <T> (IEnumerable <T> source) 
{
    FCSColl::List <T> stack = FCSColl::List <T> .Empty;
    foreach (T item in source)
    stack = stack.Cons(item);
    while (stack != FCSColl.List < T > .Empty) {
        yield return stack.Head;
        stack = stack.Tail;
    }
}
public static R FoldR<T, R> (Func< T, R, R > accumulator,
 R startVal,
IEnumerable<T> list) {
    return FoldL((r, x) = > accumulator(x, r), startVal,
    Functional.Reverse(list));
}

Teraz pytanie czy możemy napisać coś podobnego w LINQ. Istnieje metoda Aggregate, która spełnia podobną funkcję.

var numbers = new List<int> { 6, 2, 8, 3 };
int sum1 = numbers.Aggregate((r, x) => r + x);

Swoją drogą, dlaczego metody LINQ jak

- Select nie nazywa się Map, 

- Where nie nazywa się Filter

- Aggregate nie nazywa się Fold

Microsoft chciał aby te metody bardziej kojarzyły Ci się z nazewnictwem występujący bazach danych SQL niż metodami z języków funkcyjnych. SELECT, WHERE, rozumiesz

Chodziło przetłumaczenie niby zapytania SQL-podobnych do C#. Widać to zwłaszcza w takim stylu pisania zapytań LINQ

var ordersWithValueGreater =
    from t in
    from o in orders
    select new {
    Date = o.Date,
    Value = o.Lines.Sum(ol = > ol.Product.Price * ol.Count)
}

LINQ jest zorientowanych w kolekcjach tak bardzo, że nie uświadamiamy sobie, że są one funkcjami wyższego rzędu jak : map, filter i fold.

Co więcej, metody LINQ są metodami rozszerzeniowych i ma się wrażenie, że żyją one w kolekcjach i nie mają nic wspólnego z programowaniem funkcyjnym, ale tak nie jest.

A co z tymi funkcjami: map, filter, fold. Są to przykłady pewnych wzorców w językach funkcyjnych. W naszym języku obiektowym także mamy swoje wzorce projektowe.  Co więcej, te przykłady nie są rewolucyjne i być może istnieją one już gdzieś pod inną nazwą.

Funkcje map, filter, fold jeszcze do nas wrócą, gdy będziemy rozbijać funkcję na moduły. Na razie chciałbym Ci u świadomość, że pewne elementy programowania funkcyjnego mogą się wydawać trudne, bo się dziwnie nazywają, ale tak naprawdę są to rzeczy, które robisz już w programowaniu od wielu lat.