Wir geben eine Reihe von Beispielen und dann einen globaleren Ansatz für Katamorphismen in der Programmiersprache Haskell.

IterationEdit

Iterationsschrittvorgaben führen zu natürlichen Zahlen als Anfangsobjekt.

Betrachten Sie den Funktor fmaybe, der einen Datentyp b einem Datentyp fmaybe b zuordnet, der eine Kopie jedes Terms von b sowie einen zusätzlichen Term Nothing (in Haskell ist dies das, was Maybe tut). Dies kann mit einem Term und einer Funktion codiert werden. Lassen Sie also eine Instanz einer StepAlgebra auch eine Funktion von fmaybe b bis b enthalten, die Nothing einem festen Term nil von b wobei die Aktionen für die kopierten Begriffe next .

List foldEdit

Betrachten Sie für einen festen Typ a die Funktorzuordnungstypen b zum Produkttyp dieser beiden Typen. Außerdem fügen wir diesem resultierenden Typ einen Term Nil hinzu. Eine f-Algebra soll nun Nil einem speziellen Term nil von b zuordnen oder ein Paar (einen beliebigen anderen Term des konstruierten Typs) zu einem Term von b „zusammenführen“. Dieses Zusammenführen eines Paares kann als Funktion vom Typ a -> b -> b codiert werden.

Tree foldEdit

Betrachten Sie für einen festen Typ a die Funktorzuordnungstypen b zu einem Typ, der eine Kopie jedes Terms von a sowie alle Paare von b’s (Begriffe des Produkttyps von zwei Instanzen des Typs b). Eine Algebra besteht aus einer Funktion zu b, die entweder auf einen a Term oder zwei b Term wirkt. Dieses Zusammenführen eines Paares kann als zwei Funktionen vom Typ a -> b bzw. b -> b -> b.

Allgemeiner Fallbearbeiten

Tiefergehende theoretische Untersuchungen der Anfangsalgebren zeigen, dass die F-Algebra, die durch Anwenden des Funktors auf seine eigene Anfangsalgebra erhalten wird, isomorph zu ihr ist.

Starke Typensysteme ermöglichen es uns, die Anfangsalgebra eines Funktors f abstrakt als seinen Fixpunkt a = fa anzugeben. Die rekursiv definierten Katamorphismen können jetzt in einer Zeile codiert werden, wobei die Fallanalyse (wie in den verschiedenen obigen Beispielen) von der fmap gekapselt wird. Da die Domäne der letzteren Objekte im Bild von f sind, springt die Auswertung der Katamorphismen zwischen a und f a hin und her.

Nun wieder das erste Beispiel, aber jetzt über das Übergeben des Maybe Funktors zu beheben. Die wiederholte Anwendung des Maybe Funktors erzeugt eine Kette von Typen, die jedoch durch den Isomorphismus aus dem Fixpunktsatz vereint werden können. Wir führen den Begriff zero ein, der sich aus Maybes‘ Nothing ergibt und identifizieren eine Nachfolgefunktion mit wiederholter Anwendung des Just. So entstehen die natürlichen Zahlen.

Und nun wieder das Baumbeispiel. Dazu müssen wir den tree container Datentyp angeben, damit wir den fmap (wir mussten es nicht für den Maybe Funktor tun, da er Teil des 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

Folgendes wird zu 4 ausgewertet: cata treeDepth $ meet (end "X") (meet (meet (end "YXX") (end "YXY")) (end "YY"))