We geven een reeks voorbeelden, en dan een meer globale benadering van catamorfismen, in de programmeertaal Haskell.

Iteratiedit

Iteratiestappen leiden tot natuurlijke getallen als initiële object.

Overweeg de functor fmaybe toewijzen van een gegevenstype b om een gegevenstype fmaybe b, bevat een exemplaar van elke term uit b evenals een extra term Nothing (in Haskell, dit is wat Maybe doet). Dit kan worden gecodeerd met behulp van een term en een functie. Dus laat een instantie van een Stapalgebra ook een functie opnemen van fmaybe b naar b, die Nothing naar een vaste termijn nil van b, en waar de acties op de gekopieerde termen worden nextgenoemd.

List foldEdit

voor een vast type a, overweeg dan de functor mapping types b naar het producttype van deze twee typen. Bovendien voegen we ook een term Nil toe aan dit resulterende type. Een F-algebra moet nu Nil toewijzen aan een speciale term nil van b of een paar (een andere term van het geconstrueerde type) samenvoegen tot een term van b. Dit samenvoegen van een paar kan worden gecodeerd als functie van het type a -> b -> b.

Boom foldEdit

Voor een vast type a, overweeg de functor mapping types b naar een type dat een kopie bevat van elke term van a alsmede alle paren b’s (termen van het type product van twee exemplaren van het type b). Een algebra bestaat uit een functie tot b, die ofwel werkt op een a term of twee b term. Dit samenvoegen van een paar kan worden gecodeerd als twee functies van het type a -> b resp. b -> b -> b.

Algemeen caseEdit

diepere categorietheoretische studies van initiële algebra ‘ s tonen aan dat de F-algebra die wordt verkregen door de functor op zijn eigen initiële algebra toe te passen, daarmee isomorf is.

Strong type systems stellen ons in staat om de initiële algebra van een functor f abstract te specificeren als het vaste punt a = f a. De recursief gedefinieerde catamorfismen kunnen nu worden gecodeerd in enkele regel, waarbij de case analyse (zoals in de verschillende voorbeelden hierboven) wordt ingekapseld door de fmap. Aangezien het domein van deze laatste objecten zijn in de afbeelding van f, springt de evaluatie van de catamorfismen heen en weer tussen a en f a.

nu weer het eerste voorbeeld, maar nu via het doorgeven van de Misschien functor te repareren. Herhaalde toepassing van de Misschien functor genereert een keten van types, die echter kan worden verenigd door het isomorfisme van de vaste puntstelling. We introduceren de term zero, die voortkomt uit Maybes ‘ Nothing en identificeren een opvolgfunctie met herhaalde toepassing van de Just. Zo ontstaan de natuurlijke getallen.

en nu weer het tree voorbeeld. Hiervoor moeten we het tree container data type opgeven zodat we de fmap kunnen instellen (we hoefden dit niet te doen voor de Maybe functor, omdat het deel uitmaakt van de standaard 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