vi gir en rekke eksempler ,og deretter en mer global tilnærming til katamorphisms, I programmeringsspråket Haskell.

IterationEdit

iterasjon-trinn resepter føre til naturlige tall som første objekt.

Tenk på functor fmaybe tilordne en datatype b til en datatype fmaybe b, som inneholder en kopi av hver term fra b samt en ekstra term Nothing (i haskell er dette hva Maybe gjør). Dette kan kodes ved hjelp av en term og en funksjon. Så la en forekomst Av En StepAlgebra også inkludere en funksjon fra fmaybe b til b, som kartlegger Nothing til et fast begrep nil av b, og hvor handlingene på de kopierte vilkårene vil bli kalt next.

liste foldEdit

for en fast type a, vurder functor kartleggingstypene b til produkttypen for disse to typene. Vi legger også til et begrep Nil til denne resulterende typen. En f-algebra skal nå kartlegge Niltil et spesielt begrep nilav beller» slå sammen»et par (et hvilket som helst annet begrep av den konstruerte typen) til et begrep av b. Denne sammenslåingen av et par kan kodes som en funksjon av typen a -> b -> b.

tre foldEdit

for en fast type a, vurder functor kartleggingstypene b til en type som inneholder en kopi av hvert begrep av a samt alle par av b‘s (Vilkår for produkttype av to forekomster av typen b). En algebra består av en funksjon til b, som enten virker på en a term eller to b vilkår. Denne sammenslåingen av et par kan kodes som to funksjoner av typena -> b resp. b -> b -> b.

Generell caseEdit

Dypere kategori teoretiske studier av innledende algebraer viser At F-algebra oppnådd ved å bruke funktoren til sin egen innledende algebra er isomorf til den.

Sterke typesystemer gjør det mulig for oss å abstrakt angi den første algebraen til en functorf som sitt faste punkt a = f a. De rekursivt definerte katamorfismene kan nå kodes i enkeltlinje, hvor saksanalysen (som i de forskjellige eksemplene ovenfor) er innkapslet av fmap. Siden domenet til sistnevnte er objekter i bildet av f, hopper evalueringen av katamorfismene frem og tilbake mellom a og f a.

nå igjen det første eksemplet, men nå via passerer kanskje functor Å Fikse. Gjentatt bruk Av kanskje-funktoren genererer en kjede av typer, som imidlertid kan forenes av isomorfismen fra fastpunktsteoremet. Vi introduserer begrepet zero, som oppstår fra Maybes Nothing og identifiserer en etterfølger funksjon med gjentatt bruk av Just. På denne måten oppstår de naturlige tallene.

og nå igjen treet eksempel. For dette må vi gi datatypen tree container slik at vi kan sette oppfmap (vi måtte ikke gjøre det forMaybe functor, som det er en del av standard prelude).

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

cata treeDepth $ meet (end "X") (meet (meet (end "YXX") (end "YXY")) (end "YY"))