Katamorfizmy i F-algebry

często słyszę więc słowa “katamorfizm” i “schematy rekurencyjne”. O co chodzi?

Katamorfizmy (lub cata) są uogólnieniami pojęcia fałdy w programowaniu funkcyjnym. Biorąc pod uwagę F-algebrę i rekurencyjną strukturę danych, katamorfizm wytworzy wartość poprzez rekurencyjną ocenę struktury danych.

co to jest Algebra F? Może najpierw pokażesz kilka przykładów kodu?

konfiguracja nie jest tak prosta, więc zacznijmy od prostego. Załóżmy, że masz następującą strukturę danych do reprezentowania wyrażenia:

i proste wyrażenie może wyglądać tak:

posiadanie tylko struktury danych wyrażenia jest bezużyteczne, oczywiście będziesz potrzebował funkcji, aby obliczyć i uzyskać wynik:

tutaj pojawia się uogólnienie katamorfizmu:

🤨, ale po co? Używasz tylko argumentu do funkcji?

to dlatego, że jest notReallyCata. Rzeczywista funkcja cata jest ogólna i nie zależy od żadnej konkretnej struktury danych ani funkcji ewaluatora. Zobacz, Tworzenie rekurencyjnej struktury danych, a następnie składanie nad nią jest powszechnym wzorcem, który cata próbuje uogólnić.

Ok, to jak wygląda prawdziwe cata?

🤯

dlatego zaczęliśmy od notReallyCata. Rozwalimy implementację później, dopóki nie kliknie. Ale teraz przejdźmy do naszego przykładu Expression. Po pierwsze, musimy pozbyć się rekurencji, wprowadzając parametr typu:

wszystkie odniesienia do Expression są zastępowane parametrem typu a, więc struktura danych nie jest już rekurencyjna.

dlaczego na końcu konstruktorów typu znajduje się F?

cieszę się, że pytasz-to podpowiedź, że ExpressionF może być Functor:

nic wymyślnego, po prostu zastosowanie jakiejś funkcji do zawiniętej wartości zachowującej strukturę.

Nie wiem po co nam to 🤔

teraz to nie ma sensu, ale trochę później. Sposób w jaki tworzymy nasze wyrażenie nie uległ zmianie (poza nazwami konstruktorów):

ale wynikowy typ jest inny:

expr zwija wszystko w jeden Expression, podczas gdy exprF koduje informacje o poziomie zagnieżdżania naszego drzewa wyrażeń. Mówiąc o ewaluacji, w ten sposób możemy wdrożyć eval dla ExpressionF:

główną różnicą w stosunku do oryginalnego evalExpr jest to, że nie mamy rekurencyjnego wywołania evalExprF (ExpressionF nie jest rekurencyjna, pamiętasz?). Oznacza to również, że nasz ewaluator może pracować tylko z jednym wyrażeniem poziomu:

i nie skompiluje się na tym:

po prostu dlatego, że exprF expepects ExpressionF Int a my popychamy ExpressionF (ExpressionF Int).

aby to zadziałało możemy zdefiniować inny ewaluator:

wygląda trochę doraźnie, co jeśli masz głęboko zagnieżdżone wyrażenia?

tak, dla dowolnego zagnieżdżonego wyrażenia to podejście nie jest skalowalne — każdy dodatkowy poziom zagnieżdżenia wymaga napisania wyspecjalizowanej funkcji.

jest sposób na uogólnienie tego zagnieżdżenia nowym typem:

naprawić? Wygląda jak rekurencyjna struktura danych, która niewiele robi. Jak to jest przydatne?

spójrzmy najpierw na wyrażenie przed znakiem równości: rzeczywiście Fixjest rekurencyjną strukturą danych, która ma jeden parametr typu f. Parametr ten ma rodzaj * -> * np. przyjmuje również parametr type. Na przykład, nie można skonstruować Fix podając Int lub Bool, musi to być coś w stylu Maybe, List lub… ExpressionF. Dlatego wprowadziliśmy parametr type dla ExpressionF. Następnie, po znaku równości mamy konstruktor pojedynczego typu Fx przyjmujący pojedynczy argument typu f (Fix f), który jest w zasadzie wyrażeniem, które konstruuje wartość f. W przypadku Maybe byłoby to Maybe (Fix Maybe), a następnie całość jest owinięta Fxdo typu Fix Maybe.

podpis typu jest mylący do odczytania na początku, ponieważ konstruktor typu może mieć taką samą nazwę jak sam Typ plus samo odwołanie. Ale nie ma w tym nic więcej niż tylko zawijanie typu wyższego rzędu do struktury danych. Btw, unfix jest przeciwieństwem Fx i wszystko, co robi, to dopasowanie wzorca do Fx i zwraca zapakowaną wartość, nic wielkiego.

teraz zamienimy każdy ExpressionF naszego drzewa wyrażeń na Fix ExpressionF. Zwróć uwagę na różnicę w konstruowaniu wyrażeń z i bez Fx – są one zasadniczo takie same, z tym, że musimy poprzedzić Fx $:

wynikowy Typ “stałej” wersji to Fix ExpressionF, więc wracamy do rekurencyjnej reprezentacji, ale teraz musimy użyć funkcji unfix, aby odzyskać naszą nie rekurencyjną strukturę danych.

jakie są korzyści z posiadania Fix? Wygląda na to, że to jest to samo podejście co oryginalny typ Expression ale teraz mamy ten dziwny Fix i unfix nonsens?

tak, ale staramy się uogólnić proces składania, wymaga to wprowadzenia dodatkowych abstrakcji, takich jak Fix i Algebra, które omówimy później. Cierpliwości, to powinno mieć sens później.

mamy więc naszą “stałą” strukturę danych, jak wyglądałaby funkcja ewaluacyjna?

biorąc pod uwagę Fix ExpressionF jedyne co możemy z nim zrobić to wywołać unfix co daje ExpressionF (Fix ExpressionF):

zwracany parametr ExpressionF może być jednym z naszych ValueF, AddF lub MultF z parametrem Fix ExpressionF jako parametrem typu. To ma sens, aby zrobić dopasowanie wzorca i zdecydować, co zrobić dalej:

tak, wygląda tak samo jak nasz pierwszy rekurencyjny ewaluator dla Expression z dodatkiem konieczności rozpakowania wyrażenia za pomocą unfix. Więc po co zawracać sobie głowę Fix?

oto klucz: ponownie użyjemy naszego oryginalnego’ fix-less ‘ ewaluatora dla ExpressionF i w jakiś sposób rozłożymy go na strukturę Fix ExpressionF. Więc powinna to być funkcja przyjmująca dwa argumenty-ewaluator i strukturę do ewaluacji:

spróbujmy zrozumieć implementację-pierwszą logiczną rzeczą do zrobienia jest użycie unfix, aby uzyskać ExpressionF i być może przekazać ją do evaluator:

oczywiście to nie działa, evaluator oczekuje ExpressionF Int, a nie ExpressionF (Fix ExpressionF). Przy okazji, pamiętasz, że ExpressionF to Functor? W tym momencie staje się to przydatne-możemy użyć fmap, aby zastosować ten sam proces do wewnętrznego poziomu naszego drzewa wyrażeń:

poświęć chwilę i zastanów się, co się dzieje: przekazujemy funkcję rekurencyjną almostCata evaluatordo fmap. Jeśli bieżącym wyrażeniem jest AddF lub MultF, to ta funkcja zostanie przekazana o jeden poziom głębiej i fmap zostanie ponownie wywołana. Tak się stanie, dopóki nie osiągniemy wartości ValueF, fmapping over ValueF zwróci wartość typu ExpressionF Int i to jest dokładnie to, co nasza funkcja evaluator akceptuje.

patrząc na almostCata widzimy, że tak naprawdę nie ma niczego konkretnego dla typu ExpressionF lub Int i teoretycznie można go uogólnić za pomocą jakiegoś parametru typu f. Jedynym ograniczeniem powinno być wystąpienie Functor dla f, ponieważ używamy fmap:

i to jest ostateczna wersja cata. Oto pełna implementacja z przykładami użycia:

to chyba spoko. Ale dlaczego?

wiele pojęć w teorii kategorii i programowaniu funkcyjnym jest dość abstrakcyjnych i czasami trudno jest znaleźć natychmiastowe praktyczne zastosowanie dla określonego pomysłu. Ale szukanie abstrakcji i uogólnień jest przydatne do znajdowania wzorców i eleganckich rozwiązań problemów, które w przeciwnym razie wymagają doraźnej implementacji.

przy okazji, uogólniając naszą ExpressionF -> Int funkcję do Functor f => (f a -> a) odkryliśmy inną ważną koncepcję zwaną F-algebrą. Zasadniczo F-Algebra jest potrójnym funktorem f, pewnym typem ai funkcją ewaluatora f a -> a. Zauważ, że a tutaj nie jest polimorficzny-musi to być Typ konkretny, jak Int lub Bool i nazywa się to typem nośnym. Dla dowolnego endo-funktora f można na jego podstawie utworzyć wiele F-algebr. Weźmy przykład wyrażeń-endo-functor f to ExpressionF, a to Int, a evaluator to evalExprF. Ale możemy zmienić typ nośnika i stworzyć więcej algebr:

to tylko różne ewaluatory, które można przekazać do cata, prawda?

tak, wybieramy różne typy nośników i wybieramy nasze wdrożenie. Ale tam jest sztuczka-jest matka wszystkich oceniających, które możemy stworzyć wybierając nasz typ nośnika na … Fix ExprF.

ocenianie do Int lub Bool CAŁKOWICIE ma sens, ale co by to initialAlgebra oceniało? Kiedy muszę mieć Fix czegoś w wyniku mojego oceniającego?

oczywiście nie napiszesz czegoś takiego sam, po prostu chcesz pokazać głębsze znaczenie za f-algebrami i cata. W rzeczywistości mamy już implementację dla takiego ewaluatora i to dokładnie Fx konstruktor:

czekaj, Fx to ewaluator? To szaleństwo.

tak i robi najprostszą rzecz, jaką możesz zrobić — zapisuje expesję do struktury danych. Podczas gdy wszystkie inne ewaluatory (algebra0, algebra1) wytworzyły pewną wartość poprzez zmniejszenie wyrażenia (jak np. sumowanie lub konkatenacja) Fx po prostu zawija wyrażenie bez utraty danych.

dlatego wprowadziliśmy Fix w pierwszej kolejności — najpierw oceniasz swoją pierwotną strukturę danych za pomocą Fx do algebry początkowej Fix f, a następnie za pomocą cata‘prawdziwa’ ewaluacja odbywa się przez fmap w twoim konkretnym ewaluatorze nad algebrą inicjalną.

z punktu widzenia teorii kategorii wszystkie algebry oparte na tym samym endo-funktorze tworzą kategorię. Kategoria ta ma obiekt początkowy, który jest naszą algebrą początkową utworzoną przez wybranie typu nośnika jako Fix f. Jest kilka świetnych blogów Bartosza Milewskiego, które Gorąco polecam sprawdzić, jeśli chcesz uzyskać głębokie kategoryczne zrozumienie.

to wciąż dość trudne do zrozumienia, nie sądzę, że w pełni rozumiem pojęcie

zawsze lepiej zrobić ręce: spróbuj ponownie zaimplementować Fix i cata na własną rękę, pomyśl o możliwych strukturach danych i algebrach. Na przykład String może być reprezentowany rekurencyjnie (jako Char głowa i ogon String), length ciągu może być obliczony z cata. Oto kilka świetnych zasobów do dalszej lektury:

• zrozumienie F-algebr i nieco innych F-algebr autorstwa Bartosza Milewskiego
• Katamorfizmy w 15 minut autorstwa Chrisa Jonesa
• Pure Functional Database Programming with Fixpoint Types autorstwa Roba Norrisa
• Katamorfizmy na Haskell wiki
• praktyczne Schematy rekurencji autorstwa Jareda Tobina