Katamorfismer och F-algebror

så jag hör ofta orden “katamorfism”och ” rekursionsscheman”. Vad handlar det om?

Katamorfismer (eller cata) är generaliseringar av begreppet en vikning i funktionell programmering. Med tanke på en F-Algebra och en rekursiv datastruktur kommer en katamorfism att producera ett värde genom att rekursivt utvärdera din datastruktur.

Vad är en F-Algebra? Kanske kan du visa några kodexempel först?

installationen är inte så enkel så låt oss börja enkelt. Låt oss säga att du har följande datastruktur för att representera ett uttryck:

och ett enkelt uttryck kan se ut så här:

att bara ha en uttrycksdatastruktur är värdelös, naturligtvis behöver du en funktion för att utvärdera och få resultatet:

det är här generalisering av katamorfism kommer in:

🤨, men vad är poängen? Använder du bara ett argument till en funktion?

det beror på att det är notReallyCata. Den verkliga cata – funktionen är generisk och beror inte på någon speciell datastruktur eller utvärderingsfunktion. Se, skapandet av en rekursiv datastruktur och sedan vikning över det är ett vanligt mönster som cata försöker generalisera.

Ok, hur ser den riktiga cata ut?

🤯

det är därför vi började med notReallyCata. Vi bryter ner implementeringen senare tills den klickar. Men nu ska vi fortsätta med vårt Expression exempel. Först måste vi bli av med rekursion genom att införa en typparameter:

alla referenser till Expression ersätts med a typparameter så att datastrukturen inte längre är rekursiv.

Varför finns det en F i slutet av typkonstruktörer?

Glad att du frågade — det är en ledtråd som ExpressionF kan vara en Functor:

inget fancy, bara tillämpa någon funktion på den inslagna värde bevara stucture.

inte säker på varför vi behöver det 🤔

det är inte meningsfullt nu men det kommer lite senare. Nu har sättet vi skapar vårt uttryck inte förändrats (förutom konstruktörnamn):

men den resulterande typen är annorlunda:

expr kollapsar allt till en enda Expression medan exprF kodar information om häckningsnivån för vårt uttrycksträd. På tal om utvärdering, Det är så vi kan gå om att genomföra eval för ExpressionF:

huvudskillnaden med original evalExpr är att vi inte har rekursivt samtal till evalExprF(ExpressionF är inte rekursivt, kom ihåg?). Det betyder också att vår utvärderare bara kan arbeta med ett enda nivåuttryck:

och kommer inte att kompilera på detta:

helt enkelt för att exprF förväntar sig ExpressionF Intoch vi skjuter ExpressionF (ExpressionF Int).

för att få det att fungera kunde vi definiera en annan utvärderare:

ser ganska ad hoc, vad händer om du har djupt kapslade uttryck?

Ja, för godtyckliga kapslade uttryck är detta tillvägagångssätt inte skalbart-varje ytterligare nestningsnivå kräver att du skriver specialiserad funktion.

det finns ett sätt att generalisera denna nestning med en ny typ:

Fix? Ser ut som en rekursiv datastruktur som inte gör mycket. Hur är det användbart?

Låt oss först titta på uttrycket före likhetstecknet: faktiskt Fix är en rekursiv datastruktur som har en typparameter f. Denna parameter har typ * -> * t.ex. det tar också en typparameter. Du kan till exempel inte konstruera Fix med Int eller Bool, det måste vara något som Maybe, List eller… ExpressionF. Det är därför vi introducerade typparameter för ExpressionF. Därefter har vi efter likhetstecknet en enda typkonstruktör Fx med ett enda argument av typen f (Fix f)vilket i grunden är ett uttryck som konstruerar f värde. I fallet med Maybe skulle det vara Maybe (Fix Maybe) och sedan är det hela inslaget med Fxi typ Fix Maybe.

typsignaturen är förvirrande att läsa först på grund av att typkonstruktören kan ha samma namn som typen själv plus självreferens. Men det finns inte mycket mer än att bara förpacka en högre ordertyp i en datastruktur. Btw, unfix är en motsats till Fx och allt det gör är mönstermatchning på Fx och returnerar inslaget värde, ingen stor sak.

nu kommer vi att ersätta varje ExpressionF i vårt uttrycksträd med Fix ExpressionF. Lägg märke till skillnaden i att konstruera uttryck med och utan Fx — de är i princip samma, förutom att vi måste förbereda oss Fx $:

den resulterande typen av en ‘fast’ version är Fix ExpressionF så vi är tillbaka till en rekursiv representation, men nu måste vi använda funktionen unfix för att få vår icke rekursiva datastruktur tillbaka.

vilka är fördelarna med att ha Fix? Ser ut som det är samma tillvägagångssätt som original Expression typ men nu har vi det här konstiga Fix och unfix nonsens?

Ja, men vi försöker generalisera vikningsprocessen, det kräver införande av ytterligare abstraktioner, som Fix och Algebra som vi kommer att diskutera senare. Bär med mig, det borde vara mer meningsfullt senare.

så vi har vår ‘fasta’ datastruktur, hur skulle utvärderingsfunktionen se ut?

med tanke på en Fix ExpressionF är det enda vi kan göra med det att ringa unfix som producerar ExpressionF (Fix ExpressionF):

den returnerade ExpressionF kan vara en av våra ValueF, AddF eller MultF med en Fix ExpressionF som typparameter. Det är vettigt att göra mönstermatchning och bestämma vad du ska göra nästa:

Ja, det ser ut som vår allra första rekursiva utvärderare för Expressionmed tillägg av att behöva packa upp uttrycket med unfix. Så varför bry sig om Fix ändå?

här är nyckeln: vi kommer att återanvända vår ursprungliga ‘fix-less’ utvärderare för ExpressionF och på något sätt distribuera den över Fix ExpressionF – strukturen. Så detta borde vara en funktion som tar två argument-utvärderaren och strukturen att utvärdera:

Låt oss försöka räkna ut implementeringen – den första logiska saken att göra är att använda unfix för att få ExpressionF och sedan kanske skicka den till evaluator:

självklart fungerar det inte, evaluator förväntar sig ExpressionF Int och inte ExpressionF (Fix ExpressionF). Förresten, kom ihåg att ExpressionF är en Functor? Det är här det blir praktiskt-vi kan använda fmap för att tillämpa samma process på den inre nivån i vårt uttrycksträd:

ta en stund och tänk på vad som händer: vi skickar en rekursiv funktion almostCata evaluator till fmap. Om det aktuella uttrycket är AddF eller MultF kommer denna funktion att skickas en nivå djupare och fmap kommer att ringas igen. Detta kommer att hända tills vi når ValueF, fmapping över ValueF returnerar värde av typen ExpressionF Int och det är precis vad vår evaluator – funktion accepterar.

genom att titta på almostCata kan vi se att det egentligen inte har något specifikt för ExpressionF eller Inttyp och teoretiskt kan generaliseras med någon typparameter f. Den enda begränsningen bör ha en Functor instans för f , eftersom vi använder fmap:

och det är den slutliga versionen av cata. Här är den fullständiga implementeringen med några användningsexempel:

jag antar att det är coolt. Men varför tho?

många begrepp i kategoriteori och funktionell programmering är ganska abstrakta och ibland är det svårt att hitta omedelbar praktisk tillämpning för viss ide. Men att leta efter abstraktioner och generaliseringar är användbart för att hitta mönster och eleganta lösningar på problem som annars kräver ad hoc-implementering.

förresten, genom att generalisera vår ExpressionF -> Int-funktion till Functor f => (f a -> a) upptäckte vi ett annat viktigt begrepp som heter F-Algebra. I grund och botten är F-Algebra en trippel av functor f, någon typ a och utvärderingsfunktion f a -> a. Observera att a här inte polymorf-det måste vara en konkret typ, som Int eller Bool och det kallas en bärartyp. För alla endo-functor f kan du skapa flera F-Algebra baserat på den. Ta vårt uttryck exempel-endo-functor f är ExpressionF, a är Int och utvärderaren är evalExprF. Men vi kan ändra bärartypen och producera fler algebror:

det är bara olika utvärderare som kan överföras till cata, eller hur?

Ja, Vi väljer olika operatörstyper och väljer vår implementering. Men där tricket – det finns en mamma till alla utvärderare som vi kan skapa genom att välja vår bärartyp för att vara… Fix ExprF.

utvärdering till Int eller Bool är helt meningsfullt men vad skulle detta initialAlgebra utvärdera? När behöver jag ha Fix av något som ett resultat av min utvärderare?

naturligtvis skriver du inte något sådant själv, Vill bara visa dig den djupare betydelsen bakom f-algebror och cata. Faktum är att vi redan har en implementering för en sådan utvärderare och det är exakt Fx konstruktör:

vänta, Fx är en utvärderare? Det är galet.

Ja Och det gör det enklaste du kan göra-spara expeditionen i en datastruktur. Medan alla andra utvärderare (algebra0, algebra1) producerade något värde genom att minska uttrycket (som att göra summa eller sammanfogning) Fx bara sveper uttrycket utan att förlora några data.

det är därför vi introducerade Fix i första hand — du utvärderar först din ursprungliga datastruktur med Fx i initial algebra Fix f och sedan använder cataden ‘verkliga’ utvärderingen sker genom fmap ing din konkreta utvärderare över inital algebra.

ur kategoriteorisynpunkt bildar alla algebror baserade på samma endo-funktor en kategori. Denna kategori har ett initialt objekt som är vår ursprungliga algebra skapad genom att välja bärartypen som Fix f. Det finns några bra blogginlägg av Bartosz Milewski som jag rekommenderar starkt att kolla in om du vill få djup kategorisk förståelse.

det är fortfarande ganska svårt att förstå, Jag tror inte att jag helt förstår konceptet

det är alltid bättre att göra händer på: försök att implementera Fix och cata på egen hand, tänk på möjliga datastrukturer och algebror. Till exempel kan en String representeras rekursivt (som ett Char huvud och svans på String), length för en sträng kan beräknas med cata. Här är några bra resurser för vidare läsning:

• förstå F-algebror och något annorlunda F-algebror av Bartosz Milewski
• Katamorfismer på 15 minuter av Chris Jones
• ren funktionell databasprogrammering med Fixpoint-typer av Rob Norris
• Katamorfismer på Haskell wiki
• praktiska rekursionsscheman av Jared Tobin