Katamorfismer og F-Algebraer

Så jeg hører ofte ordene “katamorfisme” og “rekursjonsordninger”. Hva handler det om?

Katamorfismer (eller cata) er generaliseringer av begrepet en fold i funksjonell programmering. Gitt En F-Algebra og en rekursiv datastruktur vil en katamorfisme produsere en verdi ved rekursivt å evaluere datastrukturen.

Hva er En F-Algebra? Kanskje du kan vise noen kodeeksempler først?

oppsettet er ikke så greit, så la oss starte enkelt. La oss si at du har følgende datastruktur for å representere et uttrykk:

og et enkelt uttrykk kan se slik ut:

Å ha bare en uttrykksdatastruktur er ubrukelig, selvfølgelig trenger du en funksjon for å evaluere og få resultatet:

det er her catamorphism generalisering kommer inn:

🤨, men hva er poenget? Bruker du bare et argument til en funksjon?

Det er fordi det er notReallyCata. Den virkelige cata – funksjonen er generisk og er ikke avhengig av noen bestemt datastruktur eller evaluatorfunksjon. Se, opprettelse av en rekursiv datastruktur og deretter folding over den er et vanlig mønster som cata forsøker å generalisere.

Ok, så hvordan ser den virkelige cata ut?

🤯

Det er derfor vi startet med notReallyCata. Vi bryter ned implementeringen senere til den klikker. Men la oss nå fortsette med vårt Expression eksempel. Først må vi bli kvitt rekursjon ved å introdusere en typeparameter:

alle referanser til Expression erstattes med a typeparameter, slik at datastrukturen ikke lenger er rekursiv.

Hvorfor er det en F på slutten av type konstruktører?

Glad du spurte — det er et hint at ExpressionF kan være en Functor:

Ingenting fancy, bare å bruke noen funksjon til innpakket verdi bevare stucture.

Ikke sikker på hvorfor vi trenger det 🤔

det er ikke fornuftig nå, men det vil litt senere. Nå, måten vi lager vårt uttrykk på, har ikke endret seg (unntatt konstruktørnavn):

Men den resulterende typen er forskjellig:

expr kollapser alt i en enkelt Expression mens exprF koder informasjon om nesting nivået av vårt uttrykk treet. Snakker om evaluering, dette er hvordan vi kan gå om å implementere eval for ExpressionF:

hovedforskjellen med original evalExpr er at vi ikke har rekursiv kall til evalExprF(ExpressionF er ikke rekursiv, husk?). Det betyr også at vår evaluator kan arbeide bare med et enkelt nivå uttrykk:

og vil ikke kompilere på dette:

Bare fordi exprF expepects ExpressionF Int og vi skyver ExpressionF (ExpressionF Int).

for å få det til å fungere kunne vi definere en annen evaluator:

Ser ganske ad hoc, hva om du har dypt nestede uttrykk?

ja, for vilkårlig nestet uttrykk er denne tilnærmingen ikke skalerbar.

det er en måte å generalisere denne nestingen med en ny type:

Fikse? Ser ut som en rekursiv datastruktur som ikke gjør mye. Hvordan er det nyttig?

La oss først se på uttrykket før likhetstegnet: faktisk Fix er en rekursiv datastruktur som har en typeparameter f. Denne parameteren har type * -> * f. eks det tar også en type parameter. For eksempel kan du ikke konstruere Fix som gir Int eller Bool , det må være noe som Maybe, List eller… ExpressionF. Dette er grunnen til at vi introduserte type parameter for ExpressionF. Etter likhetstegnet har vi en enkelt type konstruktør Fx og tar et enkelt argument av typen f (Fix f) som i utgangspunktet er et uttrykk som konstruerer f ‘ s verdi. I tilfelle Maybe ville det være Maybe (Fix Maybe) og så er hele greia pakket med Fx til type Fix Maybe.

typesignaturen er forvirrende å lese først på grunn av type constructor kan ha samme navn som selve typen pluss selvreferanse. Men det er ikke mye mer til det enn bare å pakke inn en høyere ordretype i en datastruktur. Btw, unfix er motsatt til Fx og alt det gjør er mønstermatching på Fx og returnerer innpakket verdi, ingen big deal.

nå vil vi erstatte hver ExpressionF av vårt uttrykkstre med Fix ExpressionF. Legg merke til forskjellen i å bygge uttrykk med og uten Fx – de er i utgangspunktet de samme, bortsett fra at vi må prepend Fx $:

den resulterende typen av en ‘fast’ versjon er Fix ExpressionF, så vi er tilbake til en rekursiv representasjon, men nå må vi bruke unfix – funksjonen for å få vår ikke-rekursive datastruktur tilbake.

hva er fordelene med å ha Fix? Ser ut som det er samme tilnærming som original Expression type, men nå har vi denne rare Fix og unfix nonsens?

Ja, men Vi prøver å generalisere prosessen med folding, det krever innføring av flere abstraksjoner, som Fix og Algebra som vi diskuterer senere. Bær med meg, det burde være mer fornuftig senere.

Så vi har vår ‘faste’ datastruktur, hvordan vil evalueringsfunksjonen se ut?

Gitt en Fix ExpressionF det eneste vi kan gjøre med det, er å ringe unfix som produserer ExpressionF (Fix ExpressionF):

den returnerte ExpressionF kan være en av våre ValueF, AddF eller MultF med en Fix ExpressionF som deres typeparameter. Det er fornuftig å gjøre mønstermatching og bestemme hva du skal gjøre neste:

Ja, det ser ut som vår aller første rekursive evaluator for Expression med tillegg av å måtte pakke ut uttrykket med unfix. Så hvorfor bry seg med Fix uansett?

her er nøkkelen: vi vil gjenbruke vår opprinnelige ‘fix-less’ evaluator for ExpressionF og på en eller annen måte distribuere den over Fix ExpressionF stucture. Så dette bør være en funksjon som tar to argumenter-evaluatoren og strukturen for å evaluere:

la oss prøve å finne ut implementeringen — den første logiske tingen å gjøre er å bruke unfix for å få ExpressionF og så kanskje sende den til evaluator:

Tydeligvis virker dette Ikke, evaluator forventer ExpressionF Int og ikke ExpressionF (Fix ExpressionF). Forresten, husk at ExpressionF er en Functor? Det er her det blir praktisk-vi kan bruke fmap for å bruke samme prosess på det indre nivået av uttrykkstreet:

Ta et øyeblikk og tenk på hva som skjer: vi sender en rekursiv funksjon almostCata evaluator inn i fmap. Hvis det nåværende uttrykket er AddF eller MultF, vil denne funksjonen bli sendt ett nivå dypere og fmap vil bli kalt igjen. Dette vil skje til vi når ValueF, fmapping over ValueF returnerer verdien av typen ExpressionF Int og det er akkurat hva vår evaluator funksjon aksepterer.

ved å se på almostCata kan vi se at det egentlig ikke har noe spesifikt for ExpressionF eller Int type og teoretisk kan generaliseres med noen typeparameter f. Den eneste begrensningen skal ha en Functor forekomst for f, fordi vi bruker fmap:

Og det er den endelige versjonen av cata. Her er full implementering med noen eksempler på bruk:

jeg antar det er kult. Men hvorfor tho?

mange begreper i kategoriteori og funksjonell programmering er ganske abstrakte, og noen ganger er det vanskelig å finne umiddelbar praktisk anvendelse for visse ideer. Men å lete etter abstraksjoner og generaliseringer er nyttig for å finne mønstre og elegante løsninger på problemer som ellers krever ad hoc-implementering.

forresten, ved å generalisere vår ExpressionF -> Int funksjon til Functor f => (f a -> a) oppdaget vi et annet viktig konsept kalt F-Algebra. I utgangspunktet Er F-Algebra en trippel functor f, noen type a og evaluatorfunksjon f a -> a. Merk at a her ikke polymorf — det må være en konkret type, som Int eller Bool og det kalles en bærertype. For noen endo-functor f kan du opprette flere F-Algebra er basert på den. Ta vårt uttrykk eksempel — endo-functor f er ExpressionF, a er Intog evaluator er evalExprF. Men vi kan endre bærertype og produsere flere algebraer:

Det er bare forskjellige evaluatorer som kan sendes inn cata, ikke sant?

ja, vi velger forskjellige transportørtyper og velger vår implementering. Men det trikset-det er en mor til alle evaluatorer som vi kan lage ved å plukke vår transportør type å være … Fix ExprF.

Evaluering til Int eller Bool helt fornuftig, men hva ville dette initialAlgebra evaluere? Når må jeg ha Fix av noe som følge av evaluatoren min?

selvfølgelig vil du ikke skrive noe sånt selv, vil bare vise deg den dypere meningen bak f-algebraer og cata. Faktisk har vi allerede en implementering for en slik evaluator og det er akkurat Fx konstruktør:

Vent, Fx er en evaluator? Det er sprøtt.

ja, og Det gjør det enkleste du kan gjøre-lagre ekspesjonen i en datastruktur. Mens alle andre evaluatorer (algebra0, algebra1) produserte noen verdi ved å redusere uttrykket (som å gjøre sum eller sammenkobling) Fx bare bryter uttrykket uten å miste data.

dette er grunnen til at vi introduserte Fix i utgangspunktet-du evaluerer først din opprinnelige datastruktur med Fx i innledende algebra Fix f og deretter bruker cata den ‘virkelige’ evalueringen skjer ved fmap ing din konkrete evaluator over inital algebra.

fra kategori teori synspunkt, alle algebraer basert på samme endo-functor danne en kategori. Denne kategorien har et innledende objekt som er vår første algebra opprettet ved å plukke bærertypen som Fix f. Det er noen gode blogginnlegg Av Bartosz Milewski som jeg anbefaler å sjekke ut om du ønsker å få dyp kategorisk forståelse.

det er fortsatt ganske vanskelig å forstå, jeg tror ikke jeg forstår konseptet

det er alltid bedre å gjøre hendene på: prøv å implementere Fix og cata på egen hånd, tenk på mulige datastrukturer og algebraer. For eksempel kan en String representeres rekursivt (som et Char hode og hale på String), length av en streng kan beregnes med cata. Her er noen gode ressurser for videre lesing:

• Forstå F-Algebraer og litt forskjellige F-Algebraer Av Bartosz Milewski
• Katamorfismer på 15 minutter Av Chris Jones
• Ren Funksjonell Databaseprogrammering Med Fikseringspunkttyper Av Rob Norris
• Katamorfismer På haskell wiki
• Praktiske rekursjonsordninger Av Jared tobin