vi ger en serie exempel, och sedan en mer global strategi för katamorfismer, i programmeringsspråket Haskell.

IterationEdit

Iterationsstegsrecept leder till naturliga tal som initialt objekt.

Tänk på funktorn fmaybe kartlägga en datatyp b till en datatyp fmaybe b, som innehåller en kopia av varje term från b samt en ytterligare term Nothing (I Haskell är detta vad Maybe gör). Detta kan kodas med en term och en funktion. Så låt en instans av en StepAlgebra också inkludera en funktion från fmaybe b till b, som kartlägger Nothing till en fast term nil av b, och där åtgärderna på de kopierade termerna kommer att kallas next.

List foldEdit

för en fast typ a, överväga functor mapping typer b till produkttypen för dessa två typer. Vi lägger dessutom till en term Nil till denna resulterande typ. En f-algebra ska nu kartlägga Nil till någon speciell term nil av b eller” slå samman”ett par (någon annan term av den konstruerade typen) till en term av b. Denna sammanslagning av ett par kan kodas som en funktion av typen a -> b -> b.

träd foldEdit

för en fast typ a, överväga functor mapping typer b till en typ som innehåller en kopia av varje term av a samt alla par av b’s (termer av produkttypen för två instanser av typen b). En algebra består av en funktion till b, som antingen verkar på en a term eller två b termer. Denna sammanslagning av ett par kan kodas som två funktioner av typen a -> b resp. b -> b -> b.

allmänt falledit

djupare kategori teoretiska studier av initiala algebror avslöjar att F-algebra erhållen genom att applicera funktorn på sin egen initiala algebra är isomorf för den.

starka typsystem gör det möjligt för oss att Abstrakt specificera den initiala algebraen för en funktor f som dess fasta punkt a = f A. De rekursivt definierade katamorfismerna kan nu kodas i en enda rad, där fallanalysen (som i de olika exemplen ovan) inkapslas av fmap. Eftersom domänen för den senare är objekt i bilden av f, hoppar utvärderingen av katamorfismerna fram och tillbaka mellan a och f a.

nu igen det första exemplet, men nu via passerar kanske functor att fixa. Upprepad tillämpning av Maybe functor genererar en kedja av typer, som emellertid kan förenas av isomorfismen från fastpunktssatsen. Vi introducerar termen zero, som härrör från Maybes Nothing och identifierar en efterföljande funktion med upprepad tillämpning av Just. På så sätt uppstår de naturliga siffrorna.

och nu igen trädexemplet. För detta måste vi tillhandahålla trädbehållardatatypen så att vi kan ställa in fmap (vi behövde inte göra det för Maybe functor, eftersom det är en del av standardförspelet).

data Tcon a b = TconL a | TconR b binstance Functor (Tcon a) where fmap f (TconL x) = TconL x fmap f (TconR y z) = TconR (f y) (f z)

type Tree a = Fix (Tcon a) -- the initial algebraend :: a -> Tree aend = Iso . TconLmeet :: Tree a -> Tree a -> Tree ameet l r = Iso $ TconR l r

treeDepth :: Algebra (Tcon a) Integer -- again, the treeDepth f-algebra exampletreeDepth (TconL x) = 1treeDepth (TconR y z) = 1 + max y z