annamme Haskell-ohjelmointikielellä joukon esimerkkejä ja sitten kokonaisvaltaisemman lähestymistavan katamorfismeihin.

Iteraatiomedit

Iterointivaiheen määräykset johtavat luonnollisiin lukuihin alkuperäisenä objektina.

harkitse funktoria fmaybe tietotyypin kartoitus b tietotyypille fmaybe b, joka sisältää kopion jokaisesta termistä b sekä yhden ylimääräisen termin Nothing (haskellissa näin tekee Maybe). Tämä voidaan koodata yhden termin ja yhden funktion avulla. Olkoon siis stepalgebran ilmentymä myös funktio fmaybe b to b, joka karttaa Nothing määräaikaiselle nil of b, ja jossa kopioitujen ehtojen toimintaa kutsutaan nimellä next.

listaa foldEdit

kiinteälle tyypille a tarkastellaan functor-kartoitustyyppejä b näiden kahden tyypin tuotetyypille. Lisäksi tähän syntyvään tyyppiin lisätään myös termi Nil. F-algebran on nyt kartoitettava Nil jollekin erikoistermille nil of b tai ”yhdistettävä” pari (mikä tahansa muu konstruoidun tyypin termi) termiksi b. Tämä parin yhdistäminen voidaan koodata tyypin a -> b -> bfunktiona.

puun foldEdit

kiinteälle tyypille a tarkastellaan functor-kartoitustyyppejä b tyypille, joka sisältää kopion jokaisesta termistä a sekä kaikki parit b’s (kahden tuotetyypin termit b). Algebra koostuu funktiosta b, joka toimii joko a termillä tai kahdella b termillä. Tämä parin yhdistäminen voidaan koodata kahdeksi tyypiksi a -> b resp. b -> b -> b.

yleinen caseEdit

syvempien kategorioiden teoreettiset tutkimukset alkualgebrasta paljastavat, että funktorin soveltamisesta omaan alkualgebraansa saatu F-algebra on sen kanssa isomorfinen.

vahvojen tyyppijärjestelmien avulla voidaan abstraktisti määritellä funktorin alkuperäinen algebra f sen kiinteäksi pisteeksi a = f a. Rekursiivisesti määritellyt katamorfismit voidaan nyt koodata yksirivisiksi, jolloin tapausanalyysi (kuten yllä olevissa eri esimerkeissä) kapseloidaan fmap: n avulla. Koska viimeksi mainittujen domeenit ovat objekteja kuvan f, katamorfismien arviointi hyppii edestakaisin välillä a ja f a.

nyt taas ensimmäinen esimerkki, mutta nyt kautta kulkee ehkä functor korjata. Ehkä funktorin toistuva soveltaminen synnyttää tyyppiketjun, joka voidaan kuitenkin yhdistää kiintopistelauseen isomorfismilla. Otamme käyttöön termin zero, joka syntyy Maybesin Nothing ja tunnistamme seuraajafunktion, jossa käytetään toistuvasti Just. Näin syntyy luonnollisia lukuja.

ja nyt taas puuesimerkki. Tätä varten meidän on annettava puukontin tietotyyppi, jotta voimme määrittää fmap (meidän ei tarvinnut tehdä sitä Maybe functor, koska se on osa standardin 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

seuraavat arvioivat 4:cata treeDepth $ meet (end "X") (meet (meet (end "YXX") (end "YXY")) (end "YY"))