podajemy serię przykładów, a następnie bardziej globalne podejście do katamorfizmu, w języku programowania Haskell.

Iteracjaedit

iteracja-krok po kroku prowadzi do liczb naturalnych jako obiektu początkowego.

rozważ funktorfmaybe mapowanie typu danychb do typu danychfmaybe b, który zawiera kopię każdego terminu zb, a także jeden dodatkowy terminNothing (w Haskell tak działaMaybe). Można to zakodować za pomocą jednego terminu i jednej funkcji. Niech więc instancja StepAlgebra zawiera również funkcję z fmaybe b do b, która mapuje Nothing do ustalonego terminu nil z b I gdzie akcje na skopiowanych warunkach będą wywoływane next.

lista foldEdit

dla stałego typua, rozważ odwzorowanie typów funkcyjnychb na typ produktu tych dwóch typów. Ponadto dodajemy również wyrażenie Nil do tego typu wynikowego. Algebra f mapuje teraz Nil do jakiegoś specjalnego terminu nil z b lub „Scala” parę (dowolny inny termin skonstruowanego typu) W termin b. To połączenie pary może być zakodowane jako funkcja typu a -> b -> b.

Tree foldEdit

dla stałego typu a, rozważ odwzorowanie typów functora b na typ, który zawiera kopię każdego wyrażenia a, a także wszystkie pary b’s (Warunki typu produktu dwóch wystąpień typu b). Algebra składa się z funkcji b, która działa na a lub dwóch b. To połączenie pary może być zakodowane jako dwie funkcje typu a -> b lub. b -> b -> b.

ogólny przypadek

głębsze badania teoretyczne algebr początkowych ujawniają, że F-algebra uzyskana z zastosowania funktora do własnej algebry początkowej jest dla niej izomorficzna.

Systemy typu Strong pozwalają nam abstrakcyjnie określić początkową algebrę funktora f jako jego stały punkt A = f a. Rekurencyjnie zdefiniowane katamorfizmy mogą być teraz kodowane w jednej linii, gdzie analiza przypadku (jak w różnych przykładach powyżej) jest zamknięta przez fmap. Ponieważ domeną tych ostatnich są obiekty w obrazie f, ocena katamorfizmów przeskakuje tam i z powrotem pomiędzy a I f a.

teraz znowu pierwszy przykład, ale teraz poprzez przekazanie funkcji Maybe Do Naprawy. Wielokrotne zastosowanie funkcji Maybe generuje łańcuch typów, który jednak może być zjednoczony izomorfizmem z twierdzenia o punkcie stałym. Wprowadzamy termin zero, który powstaje z Nothing I identyfikujemy funkcję następcy z wielokrotnym zastosowaniem Just. W ten sposób powstają liczby naturalne.

i znowu przykład drzewa. W tym celu musimy podać typ danych tree container, abyśmy mogli ustawićfmap (nie musieliśmy tego robić dlaMaybe functor, ponieważ jest to część standardowego preludium).

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