Catamorphisms a F-Algebry

Tak často slyším slova “catamorphism” a “rekurze systémy”. O co jde?

Katamorfismy (nebo cata) jsou zobecněním konceptu záhybu ve funkcionálním programování. Vzhledem k F-algebře a rekurzivní datové struktuře katamorfismus vytvoří hodnotu rekurzivním vyhodnocením datové struktury.

co je F-Algebra? Možná můžete nejprve ukázat některé příklady kódu?

nastavení není tak jednoduché, takže začněme jednoduše. Řekněme, že máte následující datové struktury reprezentovat výraz:

A jednoduchý výraz může vypadat takto:

Mají výraz, struktura dat je k ničemu, samozřejmě, budete potřebovat funkce vyhodnotit a získat výsledek:

To je místo, kde catamorphism zobecnění je dodáván v:

🤨, ale k čemu to je? Vy jen uplatňujete argument na funkci?

je to proto, že je notReallyCata. Funkce real cata je obecná a nezávisí na žádné konkrétní datové struktuře nebo funkci hodnotitele. Viz, vytvoření rekurzivní datové struktury a pak skládání přes to je běžný vzor, který cata se snaží zobecnit.

Ok, jak tedy vypadá skutečná cata?

🤯

proto jsme začali s notReallyCata. Implementaci rozebereme později, dokud nezaklapne. Ale teď pokračujme v našem příkladu Expression. Nejprve se musíme zbavit rekurze zavedením parametru typu:

všechny odkazy na Expression jsou nahrazeny parametrem typu a, takže datová struktura již není rekurzivní.

proč je na konci konstruktérů typu F?

jsem Rád, že jsi se zeptal — to je náznak, že ExpressionF může být Functor:

Nic vymyšleného, jen použití některých funkcí zabalené hodnotu zachování strukturu.

nejste si jisti, proč to potřebujeme🤔

teď to nedává smysl, ale bude to o něco později. Nyní, způsob, jakým vytváříme naše výraz nezměnil (až na konstruktor jména):

Ale výsledný typ je jiný:

expr zhroutí se všechno do jednoho Expression, zatímco exprF kóduje informace o hnízdění úroveň našeho stromu výraz. Když už mluvíme o hodnocení, to je, jak můžeme jít o provádění hodnocení za ExpressionF:

hlavní rozdíl s původní evalExpr je, že nemáme rekurzivní volání evalExprF (ExpressionF není rekurzivní, pamatuješ?). To také znamená, že naše hodnotitel může pracovat pouze s jedním úrovni výrazu:

A nebudu kompilovat na to:

Jednoduše proto, exprF expepects ExpressionF Int a budeme strkat ExpressionF (ExpressionF Int).

aby to fungovalo, mohli bychom definovat jiného hodnotitele:

vypadá trochu ad hoc, co když máte hluboce vnořené výrazy?

Ano, pro libovolný vnořený výraz není tento přístup škálovatelný — každá další úroveň vnoření vyžaduje, abyste napsali specializovanou funkci.

existuje způsob, jak zobecnit toto hnízdění novým typem:

opravit? Vypadá to jako rekurzivní datová struktura, která moc nedělá. Jak je to užitečné?

Pojďme se nejprve podívat na výraz, než rovnítko: opravdu Fix je rekurzivní datová struktura, která má jeden parametr typu f. Tento parametr má druh * -> *, např. Například nemůžete konstruovat Fix poskytující Int nebo Bool, musí to být něco jako Maybe, List nebo … ExpressionF. Proto jsme zavedli typový parametr pro ExpressionF. Dále za znaménkem rovná máme Konstruktor jednoho typu Fx s jediným argumentem typu f (Fix f), což je v podstatě výraz, který konstruuje hodnotu f. V případě Maybe by to bylo Maybe (Fix Maybe) a pak je celá věc zabalena Fx do typu Fix Maybe.

signatura typu je na první pohled matoucí, protože konstruktor typu může mít stejný název jako samotný typ a vlastní odkazování. Ale není toho mnohem víc, než jen zabalit Typ vyššího řádu do datové struktury. Btw, unfix je opakem Fx a vše, co dělá, je shoda vzorů na Fx a vrací zabalenou hodnotu, žádný velký problém.

nyní nahradíme každý ExpressionF našeho výrazového stromu Fix ExpressionF. Všimněte si rozdílu v konstrukci výrazy s a bez Fx — jsou to v podstatě stejné, s výjimkou musíme předřadit Fx $:

výsledný typ “pevné” verze je Fix ExpressionF takže jsme zpět na rekurzivní reprezentaci, ale teď musíme použít unfix funkce, aby se naše non rekurzivní datové struktury zpět.

jaké jsou výhody mít Fix? Vypadá to, že je to stejný přístup jako původní typ Expression, ale teď máme tento podivný Fix a unfix nesmysl?

Ano, ale snažíme se zobecnit proces skládání, to vyžaduje zavedení dodatečných abstrakce, jako Fix a Algebra které budeme diskutovat později. Mějte se mnou, mělo by to dávat větší smysl později.

takže máme naši “pevnou” datovou strukturu, jak by vypadala hodnotící funkce?

Vzhledem Fix ExpressionF jediná věc, kterou můžeme udělat, je volání unfix, které produkuje ExpressionF (Fix ExpressionF):

vrácené ExpressionF může být jeden z našich ValueF, AddF nebo MultF s Fix ExpressionF jako svůj parametr typu. Má smysl dělat vzorů a rozhodnout, co dělat dál:

Ano, vypadá to stejně jako náš první rekurzivní hodnotitel pro Expression s přídavkem museli rozbalovat výraz s unfix. Tak proč se obtěžovat s Fix?

zde je klíč: budeme re-použijte náš originál fix-méně’ hodnotitel pro ExpressionF a nějak distribuovat to přes Fix ExpressionF struktura. Takže by to měla být funkce bere dva argumenty — hodnotitel a struktura hodnotit:

zkusme zjistit, realizace — první logická věc udělat, je použít unfix ExpressionF a pak třeba předat jej na evaluator:

Samozřejmě to nefunguje, evaluator očekává, že ExpressionF Int a ne ExpressionF (Fix ExpressionF). Mimochodem, nezapomeňte, že ExpressionF je Functor? To je místo, kde to bude užitečné — můžeme použít fmap použít stejný postup na vnitřní úrovni našeho stromu výraz:

udělejte Si chvilku a přemýšlet o tom, co se děje: jsme kolem rekurzivní funkce almostCata evaluator do fmap. Pokud je aktuální výraz AddF nebo MultF, bude tato funkce předána o jednu úroveň hlouběji a fmap bude znovu vyvolána. To se stane, dokud nedosáhneme ValueF, fmapping přes ValueF vrátí hodnotu typu ExpressionF Int a to je přesně to, co naše funkce evaluator přijímá.

při pohledu na almostCata můžeme vidět, že to opravdu nemá nic konkrétního, ExpressionF nebo Int typ a teoreticky lze zobecnit, že s nějakým parametrem f. Jediným omezením by měla být instance Functor pro f, protože používáme fmap:

a to je konečná verze cata. Zde je úplná implementace s několika příklady použití:

myslím, že je to v pohodě. Ale proč tho?

mnoho pojmů v teorii kategorií a funkcionálním programování je docela abstraktní a někdy je těžké najít okamžité praktické uplatnění pro určitou myšlenku. Hledání abstrakcí a zobecnění je však užitečné pro hledání vzorů a elegantních řešení problémů, které jinak vyžadují ad-hoc implementaci.

mimochodem, zobecněním naší funkce ExpressionF -> Int na Functor f => (f a -> a) jsme objevili další důležitý koncept zvaný F-Algebra. V podstatě F-Algebra je trojnásobek funktoru f, nějaký typ a a funkce hodnotitele f a -> a. Všimněte si, že a zde není polymorfní – musí to být konkrétní typ, jako Int nebo Bool a nazývá se to typ nosiče. Pro jakýkoli endo-funktor f můžete na něm vytvořit více F-algebry. Vzít naše výrazy příklad — endo-funktor f ExpressionF, a Int a hodnotitel je evalExprF. Ale můžeme změnit dopravce, typ a produkují více algebry:

to je jen jiný hodnotitele, který může být předán do cata, ne?

Ano, vybíráme různé typy nosičů a volíme naši implementaci. Ale je tu trik-existuje matka všech hodnotitelů, kterou můžeme vytvořit výběrem našeho typu dopravce … Fix ExprF.

hodnocení na Int nebo Bool má zcela smysl, ale co by to initialAlgebra vyhodnotilo? Kdy potřebuji mít Fix něco jako výsledek mého hodnotitele?

samozřejmě, že něco takového sami nenapíšete, jen vám chci ukázat hlubší význam f-algeber a cata. Ve skutečnosti již máme implementaci pro takového hodnotitele a to je přesně Fx Konstruktor:

počkat, Fx je hodnotitel? To je šílené.

Ano a dělá to nejjednodušší, co můžete udělat-uložit expession do datové struktury. Zatímco všechny ostatní hodnotitelé (algebra0, algebra1) produkoval některé hodnoty snížením exprese (jako dělá součet nebo zřetězení) Fx jen zábaly výraz bez jakékoli ztráty dat.

To je důvod, proč jsme zavedli Fix v první řadě — nejprve zhodnotit své původní datové struktury s Fx do původní algebry Fix f a pak pomocí cata “reálné” hodnocení se stane, fmaping konkrétní hodnotitel přes počáteční algebry.

z hlediska teorie kategorií tvoří všechny algebry založené na stejném endo-funktoru kategorii. Tato kategorie má počáteční objekt, který je naší počáteční algebrou vytvořenou výběrem typu nosiče jako Fix f. Tam jsou některé skvělé blogu o Bartosz Milewski, že vřele doporučuji mimo kontrolu, pokud chcete získat hluboké kategorické pochopení.

To je ještě docela těžké pochopit, myslím, že plně pochopit pojem

To je vždy lepší dělat rukou: zkuste re-prováděcí Fix a cata na své vlastní, myslím, že o možné datové struktury a algebry. Například String může být reprezentován rekurzivně (jako Char hlava a ocas String), length řetězce lze vypočítat pomocí cata. Zde je několik skvělých zdrojů pro další čtení:

• Pochopení F-Algebry a mírně odlišné F-Algebry, které Bartosz Milewski
• Catamorphisms do 15 minut od Chris Jones
• Čistě Funkční Databáze Programování s Fixpoint Typy Rob Norris
• Catamorphisms na Haskell wiki
• Praktické rekurze systémy Jared Tobin