Katamorfismit ja F-Algebrat

niinpä kuulen usein sanat “katamorfismi”ja” rekursion järjestelmät”. Mistä on kyse?

Katamorfismit (tai cata) ovat funktionaalisessa ohjelmoinnissa yleistyksiä taitoksen käsitteestä. Koska F-Algebra ja rekursiivinen tietorakenne katamorfismi tuottaa arvon rekursiivisesti arvioimalla tietorakennetta.

mikä on F-Algebra? Ehkä voit näyttää joitakin koodiesimerkkejä ensin?

asetelma ei ole niin suoraviivainen, joten aloitetaan yksinkertaisena. Oletetaan, että sinulla on seuraava tietorakenne edustamaan lauseke:

ja yksinkertainen lauseke voi näyttää tältä:

ottaa vain lauseke tietorakenne on hyödytön, tietenkin sinun täytyy funktio arvioida ja saada tulos:

tässä katamorfismin yleistys tulee:

🤨, mutta mitä järkeä siinä on? Sovellatko argumenttia funktioon?

se johtuu siitä, että se on notReallyCata. Reaalinen cata funktio on geneerinen eikä riipu mistään tietorakenteesta tai arvioijafunktiosta. Katso, rekursiivisen tietorakenteen luominen ja sen päälle taittaminen on yleinen kuvio, jota cata yrittää yleistää.

Ok, miltä sitten näyttää oikea cata?

🤯

siksi aloitimme notReallyCata. Puramme toteutusta myöhemmin, kunnes se naksahtaa. Mutta nyt jatketaan meidän Expression esimerkillä. Ensinnäkin meidän täytyy päästä eroon rekursio ottamalla käyttöön tyyppi parametri:

kaikki viittaukset Expression korvataan a tyyppiparametrilla, joten tietorakenne ei ole enää rekursiivinen.

miksi tyyppirakentajien lopussa on F?

Glad You asked – se on vihje siitä, että ExpressionF voi olla Functor:

Ei mitään fancy, vain soveltamalla joitakin toiminto kääritty arvo säilyttää stukture.

ei ole varma, miksi tarvitsemme sitä 🤔

se ei käy järkeen nyt, mutta myöhemmin. Nyt tapa, jolla luomme ilmaisumme, ei ole muuttunut (paitsi rakentajan nimet):

mutta tuloksena oleva tyyppi on erilainen:

expr romahduttaa kaiken yhdeksi Expression samalla kun exprF koodaa tietoa ilmaisupuumme pesimätasosta. Evaluoinnista puheen ollen, näin voimme toteuttaa eval: n ExpressionF:

suurin ero alkuperäiseen evalExpr on, että meillä ei ole rekursiivista kutsua evalExprF (ExpressionF ei ole rekursiivinen, Muistatko?). Se tarkoittaa myös, että arvioijamme voi työskennellä vain yhden tason lauseke:

ja ei käännä tästä:

yksinkertaisesti siksi, että exprF expepects ExpressionF Int ja me tönimme ExpressionF (ExpressionF Int).

jotta se toimisi, voisimme määritellä toisen arvioijan:

näyttää vähän tapauskohtaiselta, mitä jos sinulla on syvälle sisäkkäisiä ilmaisuja?

Kyllä, mielivaltaiselle sisäkkäiselle lausekkeelle tämä lähestymistapa ei ole skaalautuva — jokainen ylimääräinen sisäkkäinen taso edellyttää erikoistuneen funktion kirjoittamista.

on olemassa tapa yleistää tämä pesintä uudella tyypillä:

korjata? Näyttää rekursiiviselta tietorakenteelta, joka ei paljoa auta. Miten se on hyödyllinen?

tarkastellaan ensin lauseketta ennen yhtäsuuruusmerkkiä: todellakin Fix on rekursiivinen tietorakenne, jolla on yksi tyyppiparametri f. Tällä parametrilla on tyyppi * -> * esim. se ottaa myös tyyppiparametrin. Esimerkiksi Fix ei voi konstruoida Int tai Bool, vaan sen on oltava jotain Maybe, List tai … ExpressionF. Siksi otimme käyttöön tyyppiparametrin ExpressionF. Seuraavaksi, kun yhtäsuuruusmerkki meillä on yhden tyypin konstruktori Fx ottaen yhden argumentin tyyppi f (Fix f), joka on pohjimmiltaan lauseke, joka konstruoi f‘s arvo. Jos Maybe se olisi Maybe (Fix Maybe) ja sitten koko asia kääritään Fx tyypiksi Fix Maybe.

tyyppimerkintä on aluksi hämmentävää luettavaa, koska konstruktorilla voi olla sama nimi kuin itse tyypillä plus itse viittauksella. Mutta ei ole paljon enemmän kuin vain käärimistä korkeamman kertaluvun tyyppi osaksi tietorakenne. Btw, unfix on vastakohta Fx: lle ja se tekee vain kuvion täsmäämisen Fx ja palauttaa käärityn arvon, no big deal.

nyt korvataan jokainen ExpressionF ilmaisupuullamme Fix ExpressionF. Huomaa ero lausekkeiden rakentamisessa Fx kanssa ja ilman-ne ovat periaatteessa samat, paitsi että meidän on Fx $:

tuloksena oleva “kiinteän” version tyyppi on Fix ExpressionF, joten olemme palanneet rekursiiviseen esitykseen, mutta nyt on käytettävä unfix funktiota, jotta ei-rekursiivinen tietorakenne saadaan takaisin.

mitä hyötyä Fix: stä on? Näyttää siltä, että se on sama lähestymistapa kuin alkuperäinen Expression tyyppi, mutta nyt meillä on tämä outo Fix ja unfix hölynpölyä?

Kyllä, mutta yritämme yleistää taitteluprosessia, se vaatii uusien abstraktioiden käyttöönottoa, kuten Fix ja Algebra, joista keskustelemme myöhemmin. Yritä kestää, sen pitäisi olla järkevämpää myöhemmin.

meillä on siis “kiinteä” tietorakenne, miltä evaluaatiofunktio näyttäisi?

koska Fix ExpressionF ainoa asia, mitä voimme tehdä sen kanssa, on soittaa unfix, joka tuottaa ExpressionF (Fix ExpressionF):

palautettu ExpressionF voi olla yksi meidän ValueF, AddF tai MultF joilla on Fix ExpressionF tyyppiparametrina. On järkevää tehdä kuvio matching ja päättää, mitä tehdä seuraavaksi:

kyllä, se näyttää samalta kuin ensimmäinen rekursiivinen arvioijamme Expression, johon on lisätty se, että lauseke on avattava unfix. Joten miksi vaivautua Fix ylipäätään?

tässä avain: Käytämme uudelleen alkuperäistä “fix-less” – arvioijaamme ExpressionF: lle ja jotenkin jaamme sen Fix ExpressionF stuktuurille. Joten tämä olisi tehtävä ottaen kaksi argumenttia-arvioija ja rakenne arvioida:

yritetään selvittää toteutus – ensimmäinen looginen asia on käyttää unfix saada ExpressionF ja sitten ehkä siirtää se evaluator:

ilmeisesti tämä ei toimi, evaluator odottaa ExpressionF Int eikä ExpressionF (Fix ExpressionF). Muista muuten, että ExpressionF on Functor? Tässä kohtaa se käy näppäräksi — voimme käyttää fmap: ää soveltamaan samaa prosessia ilmaisupuumme sisemmälle tasolle:

Mieti hetki, mitä tapahtuu:ohitamme rekursiivisen funktion almostCata evaluator fmap. Jos nykyinen lauseke on AddF tai MultF, tämä funktio ohitetaan yhtä tasoa syvemmälle ja fmap kutsutaan uudelleen. Näin tapahtuu, kunnes saavutamme ValueF, fmapping over ValueF palauttaa arvon tyyppi ExpressionF Int ja juuri sen meidän evaluator funktio hyväksyy.

tarkastelemalla almostCata voidaan nähdä, että sillä ei oikeastaan ole mitään erityistä ExpressionF tai Int tyypille, ja teoreettisesti se voidaan yleistää jollekin tyyppiparametrille f. Ainoa rajoitus pitäisi olla ottaa Functor esimerkiksi f, koska käytämme fmap:

ja se on catalopullinen versio. Tässä on täydellinen toteutus joitakin käyttöesimerkkejä:

se on kai siistiä. Mutta miksi?

monet kategoriateorian ja funktionaalisen ohjelmoinnin käsitteet ovat melko abstrakteja ja joskus on vaikea löytää välitöntä käytännön sovellutusta tietylle idealle. Abstraktioiden ja yleistysten etsiminen on kuitenkin hyödyllistä kaavojen ja eleganttien ratkaisujen löytämiseksi ongelmiin, jotka muuten vaativat ad-hoc-toteutusta.

muuten, yleistämällä meidän ExpressionF -> Int funktio Functor f => (f a -> a) löysimme toisen tärkeän käsitteen nimeltä F-Algebra. Periaatteessa F-Algebra on funktorin f Kolmonen, jokin tyyppi a ja arvioijan funktio f a -> a. Huomaa, että a tässä ei polymorfinen-sen täytyy olla betonityyppi, kuten Int tai Bool ja sitä kutsutaan kantotyypiksi. Mille tahansa endofunktorille f voidaan luoda sen pohjalta useita F-Algebroja. Otetaan lausekkeet esimerkki-endo-functor f is ExpressionF, a is Int ja arvioija on evalExprF. Mutta voimme muuttaa harjoittajan tyyppi ja tuottaa enemmän algebras:

ne ovat vain erilaisia arvioijia, jotka voidaan siirtää cata, eikö?

Kyllä, valitsemme eri kantotyypit ja valitsemme toteutuksemme. Mutta siinä se juju — on kaikkien arvioijien äiti, jonka voimme luoda valitsemalla kantajatyyppimme … Fix ExprF.

arviointi Int tai Bool on täysin järkevää, mutta mitä tämä initialAlgebra arvioisi? Milloin arvioijani pitää saada Fix jotain?

tietenkään et itse kirjoita tuollaista, vaan haluat vain näyttää syvemmän merkityksen f-algebrojen ja Catan takana. Itse asiassa meillä on jo toteutus tällaiselle arvioijalle ja se on täsmälleen Fx rakentaja:

odota, Fx onko arvioija? Hullua.

Kyllä ja se tekee yksinkertaisimman asian mitä voi tehdä-tallentaa expession tietorakenteeksi. Kun taas kaikki muut arvioijat (algebra0, algebra1) tuottivat jonkin verran arvoa vähentämällä lauseketta (kuten tekemällä summaa tai tiivistystä) Fx vain käärii lauseketta menettämättä mitään tietoja.

tämän vuoksi otimme alun perin käyttöön Fix – ensin arvioidaan alkuperäinen tietorakenne Fx initaalialgebraan Fix f ja sitten käytetään cata ‘todellinen’ arviointi tapahtuu fmaping konkreettinen arvioija initaalialgebran yli.

kategoriateorian näkökulmasta kaikki samaan endofunktoriin perustuvat algebrat muodostavat kategorian. Tässä luokassa on alkulohko, joka on meidän alkuperäinen algebra, joka on luotu valitsemalla kantoaallon tyyppi Fix f. On olemassa hienoja blogikirjoituksia Bartosz Milewski että suosittelen tarkkailun, jos haluat saada syvä kategorinen ymmärrystä.

sitä on vielä aika vaikea ymmärtää, en usko täysin ymmärtäväni käsitettä

on aina parempi tehdä kädet: kokeile Fix ja cata uudelleen toteutusta omin päin, mieti mahdollisia tietorakenteita ja algebroja. Esimerkiksi String voidaan esittää rekursiivisesti (Char pää ja häntä String), length jono voidaan laskea cata. Tässä muutamia hienoja resursseja lisää lukemista varten:

• Bartosz Milewskin
• Catamorphisms in 15 minutes by Chris Jones
• Pure Functional Database Programming with Fixpoint Types by Rob Norris
• Catamorphisms on Haskell wiki
• practical recursion schemes by Jared Tobin