Katamorfizmusok és F-algebrák

ezért gyakran hallom a “katamorfizmus” és a “rekurziós sémák”szavakat. Mi ez az egész?

a Katamorfizmusok (vagy cata) a fold fogalmának általánosítása a funkcionális programozásban. Az F-Algebra és a rekurzív adatstruktúra alapján a katamorfizmus értéket fog előállítani az adatstruktúra rekurzív értékelésével.

mi az F-Algebra? Talán először megmutathat néhány kódpéldát?

a beállítás nem olyan egyszerű, Tehát kezdjük egyszerűen. Tegyük fel, hogy a következő adatstruktúrával rendelkezik egy kifejezés ábrázolásához:

és egy egyszerű kifejezés így nézhet ki:

miután csak egy kifejezés adatstruktúra haszontalan, természetesen szüksége lesz egy függvényt, hogy értékelje, majd kap az eredmény:

itt jön be a katamorfizmus általánosítása:

🤨, de mi értelme? Csak egy érvet alkalmaz egy függvényre?

ez azért van, mert notReallyCata. A valós cata függvény általános, és nem függ semmilyen adatstruktúrától vagy kiértékelő függvénytől. Lát, rekurzív adatstruktúra létrehozása, majd áthajtása egy általános minta, amelyet cata megpróbál általánosítani.

Ok, akkor hogyan néz ki az igazi cata?

🤯

ezért kezdtük a notReallyCata – val. Később lebontjuk a megvalósítást, amíg kattan. De most folytassuk a Expression példánkkal. Először meg kell szabadulnunk a rekurziótól egy típusparaméter bevezetésével:

minden Expression hivatkozást a típusú paraméterrel helyettesítünk, így az adatszerkezet már nem rekurzív.

miért van egy F a típuskonstruktorok végén?

örülök, hogy megkérdezte — Ez egy tipp, hogy ExpressionF lehet egy Functor:

semmi divatos, csak valamilyen funkciót alkalmaz a becsomagolt értékmegőrző szerkezetre.

nem tudom, miért van szükségünk erre 🤔

most nincs értelme, de egy kicsit később lesz. A kifejezés létrehozásának módja nem változott (kivéve a konstruktor nevét):

de a kapott Típus más:

expr mindent egyetlen Expression – re omlik össze, míg a exprF kódolja az expressziós fa fészkelési szintjével kapcsolatos információkat. Az értékelésről szólva, így mehetünk az eval végrehajtásáraExpressionF:

a fő különbség az eredeti evalExpr az, hogy nincs rekurzív hívás evalExprF (ExpressionF nem rekurzív, emlékszel?). Ez azt is jelenti, hogy kiértékelőnk csak egyetlen szintű kifejezéssel tud dolgozni:

és nem fordítja ezt:

egyszerűen azért, mert a exprF elvárja a ExpressionF Int – t, mi pedig a ExpressionF (ExpressionF Int) – t toljuk.

ahhoz, hogy ez a munka tudnánk meghatározni egy másik értékelő:

úgy néz ki, kicsit ad hoc, mi van, ha mélyen beágyazott kifejezések?

Igen, tetszőleges beágyazott kifejezésnél ez a megközelítés nem skálázható — minden további fészkelési szinthez speciális függvényt kell írni.

van egy módja annak, hogy általánosítsuk ezt a fészkelést egy új típussal:

megjavítani? Úgy néz ki, mint egy rekurzív adatstruktúra, amely nem sokat tesz. Hogyan hasznos?

először nézzük meg az egyenlőségjel előtti kifejezést: valóban Fixegy rekurzív adatszerkezet, amelynek egy típusa van paraméter f. Ennek a paraméternek a kind * -> * értéke van, pl. típusparamétert is igényel. Például nem lehet Fix konstrukciót megadni Int vagy Bool, valami olyasminek kell lennie, mint Maybe, List vagy… ExpressionF. Ezért vezettük be a type paramétert ExpressionF. Ezután az egyenlőségjel után egyetlen Fx típusú konstruktorunk van, amely egyetlen f (Fix f) típusú argumentumot vesz fel, amely alapvetően egy kifejezés, amely felépíti f értékét. Abban az esetben, Maybe lenne Maybe (Fix Maybe), majd az egész dolog csomagolva Fxa típus Fix Maybe.

a típus aláírás zavaró olvasni az első, mert típus konstruktor lehet ugyanaz a neve, mint maga a Típus Plusz önálló hivatkozás. De nincs sokkal több, mint egy magasabb rendű típus becsomagolása egy adatstruktúrába. A btw, unfix ellentéte a Fx – nek, és csak a minta illesztése a Fx – nél, és csomagolt értéket ad vissza, nem nagy ügy.

most minden ExpressionFkifejezést kicserélünk Fix ExpressionF – re. Figyeljük meg a különbséget a kifejezések szerkesztésében Fx — vel és anélkül-alapvetően ugyanazok, kivéve, hogy elöl kell Fx $:

az így kapott ‘fix’ verzió típusa Fix ExpressionF tehát visszatérünk a rekurzív ábrázoláshoz, de most a unfix függvényt kell használnunk a nem rekurzív adatstruktúra visszaállításához.

milyen előnyökkel jár a Fix? Úgy tűnik, hogy ugyanaz a megközelítés, mint az eredeti Expression típus, de most van ez a furcsa Fix és unfix ostobaság?

igen, de megpróbáljuk általánosítani a hajtogatás folyamatát, további absztrakciók bevezetését igényli, mint például a Fix és a Algebra, amelyeket később tárgyalunk. Légy türelmes, majd később értelmesebb lesz.

tehát megvan a rögzített adatstruktúránk, hogyan nézne ki az értékelési funkció?

mivel a Fix ExpressionF az egyetlen dolog, amit tehetünk vele hívja unfix amely termel ExpressionF (Fix ExpressionF):

a visszaadott ExpressionF lehet az egyik ValueF, AddF vagy MultF, amelynek típusparamétere Fix ExpressionF. Érdemes elvégezni a minta illesztését, és eldönteni, hogy mi a következő lépés:

igen, ugyanúgy néz ki, mint a legelső rekurzív kiértékelőnk Expression azzal a kiegészítéssel, hogy a kifejezést unfix – val kell kibontani. Akkor miért zavarja a Fix egyébként?

itt a kulcs: újra felhasználjuk az eredeti ‘fix-less’ kiértékelőt ExpressionF – re, és valahogy elosztjuk a Fix ExpressionF struktúrán. Tehát ennek a függvénynek két argumentumot kell tartalmaznia — az értékelő és az értékelendő struktúra:

próbáljuk kitalálni a megvalósítást — az első logikus dolog az, hogy a unfix használatával ExpressionF – et kapunk, majd talán átadjuk evaluator:

nyilvánvaló, hogy ez nem működik, a evaluator ExpressionF Int – re számít, nem pedig ExpressionF (Fix ExpressionF) – re. Egyébként ne feledje, hogy a ExpressionF egy Functor? Ez az, ahol hasznos lesz — a fmap használatával ugyanazt a folyamatot alkalmazhatjuk az expressziós fa belső szintjére:

álljunk meg egy pillanatra, és gondoljuk át, mi történik: egy almostCata evaluator rekurzív függvényt adunk át a fmap – be. Ha az aktuális kifejezés AddF vagy MultF, akkor ez a függvény egy szinttel mélyebbre kerül, és a fmap ismét meghívásra kerül. Ez addig fog történni, amíg el nem érjük a ValueF értéket, a ValueF feletti fmapping a ExpressionF Int típusú értéket adja vissza, és pontosan ez az, amit a evaluator függvényünk Elfogad.

ha megnézzük a almostCata – et, láthatjuk, hogy valójában nincs semmi konkrét ExpressionF vagy Inttípusra, és elméletileg általánosítható valamilyen f típusparaméterrel. Az egyetlen kényszer kell, hogy legyen egy Functor példánya f, mert a fmap:

és ez a cata végleges változata. Itt található a teljes megvalósítás néhány használati példával:

azt hiszem, ez király. De miért tho?

a kategóriaelméletben és a funkcionális programozásban sok fogalom meglehetősen elvont, és néha nehéz azonnali gyakorlati alkalmazást találni bizonyos ötletekre. De az absztrakciók és általánosítások keresése hasznos minták és elegáns megoldások megtalálásához olyan problémákra, amelyek egyébként ad-hoc megvalósítást igényelnek.

mellesleg, a ExpressionF -> Int függvényünk Functor f => (f a -> a) -ra történő általánosításával felfedeztünk egy másik fontos fogalmat, az úgynevezett F-Algebra. Alapvetően az F-Algebra a functor f hármasa, néhány típus a és az értékelő függvény f a -> a. Ne feledje, hogy a a itt nem polimorf — konkrét típusnak kell lennie, például Int vagy Bool, és hordozótípusnak hívják. Bármely endo-functor f hozhat létre több F-Algebra azon alapul. Vegyük például az endo — functor f ExpressionF, a Int és az értékelő evalExprFkifejezéseket. De megváltoztathatjuk a hordozó típusát és több algebrát állíthatunk elő:

ez csak a különböző értékelők, hogy át lehet adni cata, jobb?

igen, különböző hordozótípusokat választunk, és a megvalósítást választjuk. De ott a trükk — van egy anya az összes értékelő, hogy tudjuk létrehozni a szedés a fuvarozó típusát, hogy… Fix ExprF.

Értékelés Int vagy Bool teljesen van értelme, de mi lenne ez initialAlgebra értékelni? Mikor kell Fix valaminek lennie az értékelő eredményeként?

természetesen nem írsz ilyesmit magad, csak meg akarod mutatni az f-algebrák és a cata mögött rejlő mélyebb jelentést. Valójában már van egy implementáció az ilyen értékelő számára, és pontosan Fx konstruktor:

várj, Fx egy értékelő? Ez őrültség.

Igen, és ez nem a legegyszerűbb dolog, amit tehetünk — mentse a expesszió egy adatstruktúra. Míg az összes többi értékelő (algebra0, algebra1) valamilyen értéket produkált a kifejezés csökkentésével (például összegzés vagy összefűzés) Fx csak becsomagolja a kifejezést anélkül, hogy bármilyen adatot elveszítene.

ezért vezettük be először a Fix — ot-először az eredeti adatstruktúrát Fx – vel értékeljük a kezdeti algebra Fix f – be, majd a cata – et használva a ‘valós’ értékelés fmap – vel történik a konkrét értékelő inital algebra felett.

kategóriaelméleti szempontból az ugyanazon endo-functoron alapuló összes algebrák kategóriát alkotnak. Ennek a kategóriának van egy kezdeti objektuma, amely a kezdeti algebra, amelyet a hordozó típusának Fix fkiválasztásával hoztunk létre. Van néhány nagyszerű blogbejegyzés Bartosz Milewski-tól, amelyeket nagyon ajánlom megnézni, ha mély kategorikus megértést szeretne kapni.

ez még mindig elég nehéz megérteni, nem hiszem, hogy teljesen értem a koncepció

ez mindig jobb, hogy nem a kezét: próbálja újra végrehajtási Fix és cata a saját, gondolni a lehetséges adatstruktúrák és algebrák. Például egy String rekurzív módon ábrázolható (Char fej és farok String), a length karakterlánc kiszámítható cataértékkel. Íme néhány nagyszerű forrás a további olvasáshoz:

• az F-algebrák és a kissé eltérő F-algebrák megértése Bartosz Milewski-tól
• Katamorfizmusok 15 perc alatt Chris Jones-tól
• tiszta funkcionális adatbázis programozás fixpont típusokkal Rob Norris-tól
• Katamorfizmusok a Haskell wikin
• Jared gyakorlati rekurziós sémái Tobin