Katamorphismus - Catamorphism

In der Kategorientheorie bezeichnet das Konzept des Katamorphismus (aus dem Altgriechischen : κατά „nach unten“ und μορφή „Form, Gestalt“) den einzigartigen Homomorphismus von einer anfänglichen Algebra in eine andere Algebra.

In funktionaler Programmierung bieten catamorphisms Verallgemeinerungen von Faltungen von Listen auf beliebige algebraische Datentypen , die wie folgt beschrieben werden können anfängliche algebras . Das duale Konzept ist das des Anamorphismus , der sich verallgemeinert entfaltet . Ein Hylomorphismus ist die Zusammensetzung eines Anamorphismus gefolgt von einem Katamorphismus.

Definition

Betrachten Sie eine anfängliche -Algebra für einen Endofunktor einer bestimmten Kategorie in sich. Hier ist ein Morphismus von bis . Da sie initial ist, wissen wir, dass immer dann, wenn eine andere -Algebra ist, dh ein Morphismus von bis ist , es einen eindeutigen Homomorphismus von bis gibt . Nach der Definition der Kategorie der -Algebra entspricht dies einem Morphismus von bis , konventionell auch mit bezeichnet , so dass . Im Kontext der -Algebra wird der eindeutig spezifizierte Morphismus vom Ausgangsobjekt durch die folgende Beziehung bezeichnet und damit charakterisiert: ${\displaystyle F}$ ${\displaystyle (A,in)}$ ${\displaystyle F}$${\displaystyle in}$${\displaystyle FA}$${\displaystyle A}$${\displaystyle (X,f)}$${\displaystyle F}$${\displaystyle f}$${\displaystyle FX}$${\displaystyle X}$ ${\displaystyle h}$${\displaystyle (A,in)}$${\displaystyle (X,f)}$${\displaystyle F}$${\displaystyle h}$${\displaystyle A}$${\displaystyle X}$${\displaystyle h}$${\displaystyle h\circ in=f\circ Fh}$${\displaystyle F}$${\displaystyle\mathrm{cata}\f}$

• ${\displaystyle h=\mathrm{cata}\f}$
• ${\displaystyle h\circ in=f\circ Fh}$

Terminologie und Geschichte

Eine weitere in der Literatur gefundene Schreibweise ist . Die verwendeten offenen Klammern sind als Bananenklammern bekannt , nach denen Katamorphismen manchmal als Bananen bezeichnet werden , wie in Erik Meijer et al . Eine der ersten Veröffentlichungen, die den Begriff des Katamorphismus in den Kontext der Programmierung einführte, war das Paper „Functional Programming with Bananas, Lenses, Envelopes and Stacheldraht“ von Erik Meijer et al. , die im Kontext des Squiggol- Formalismus stand. Die allgemeine kategoriale Definition wurde von Grant Malcolm gegeben . ${\displaystyle (\!|f|\!)}$

Beispiele

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

Wiederholung

Iterationsschritt-Vorgaben führen zu natürlichen Zahlen als Ausgangsobjekt.

Betrachten Sie den Funktor, der fmaybeeinen Datentyp beinem Datentyp fmaybe bzuordnet, der eine Kopie jedes Terms von bsowie einen zusätzlichen Term enthält Nothing(in Haskell ist dies der MaybeFall). Dies kann mit einem Begriff und einer Funktion kodiert werden. Lassen Sie also eine Instanz einer StepAlgebra auch eine Funktion from fmaybe bto enthalten b, die Nothingeinem festen Term nilvon zugeordnet bwird und wo die Aktionen auf die kopierten Terme aufgerufen werden next.

type StepAlgebra b = (b, b->b) -- the algebras, which we encode as pairs (nil, next)

data Nat = Zero | Succ Nat -- which is the initial algebra for the functor described above

foldSteps :: StepAlgebra b -> (Nat -> b) -- the catamorphisms map from Nat to b
foldSteps (nil, next) Zero       = nil
foldSteps (nil, next) (Succ nat) = next $ foldSteps (nil, next) nat

Betrachten Sie als dummes Beispiel die Algebra für Zeichenfolgen, die als codiert sind ("go!", \s -> "wait.. " ++ s), für die zugeordnet Nothingwird "go!"und andernfalls "wait.. "vorangestellt wird. Wie (Succ . Succ . Succ . Succ $ Zero)die Zahl vier in anzeigt Nat, wird das Folgende zu "wait.. wait.. wait.. wait.. go!" ausgewertet: . Wir können den Code leicht in eine nützlichere Operation ändern, beispielsweise eine wiederholte Operation einer algebraischen Operation auf Zahlen, indem wir einfach die F-Algebra ändern , die an übergeben wirdfoldSteps ("go!", \s -> "wait.. " ++ s) (Succ . Succ . Succ . Succ $ Zero)(nil, next)foldSteps

Listenfalte

aBetrachten Sie für einen festen Typ die Funktor-Mapping-Typen bauf den Produkttyp dieser beiden Typen. Außerdem fügen wir Nildiesem resultierenden Typ noch einen Term hinzu . Eine f-Algebra soll nun Nilauf einen speziellen Term nilvon abbilden boder ein Paar (jeden anderen Term des konstruierten Typs) zu einem Term von "verschmelzen" b. Diese Verschmelzung eines Paares kann als Funktion des Typs kodiert werden a -> b -> b.

type ContainerAlgebra a b = (b, a -> b -> b) -- f-algebra encoded as (nil, merge)

data List a = Nil | Cons a (List a) -- which turns out to be the initial algebra

foldrList :: ContainerAlgebra a b -> (List a -> b) -- catamorphisms map from (List a) to b
foldrList (nil, merge) Nil         = nil
foldrList (nil, merge) (Cons x xs) = merge x $ foldrList (nil, merge) xs

Betrachten Sie als Beispiel die Algebra auf Zahlentypen, die als codiert sind (3, \x-> \y-> x*y), bei denen die Zahl von aauf die Zahl von bdurch einfache Multiplikation wirkt . Dann wird das Folgende zu 3.000.000 ausgewertet:foldrList (3, \x-> \y-> x*y) (Cons 10 $ Cons 100 $ Cons 1000 Nil)

Baumfalte

aBetrachten Sie für einen festen Typ die Funktor-Mapping-Typen bauf einen Typ, der eine Kopie jedes Terms von asowie aller Paare von b's (Terme des Produkttyps von zwei Instanzen des Typs b) enthält. Eine Algebra besteht aus einer Funktion to b, die entweder auf einen aTerm oder zwei bTerme wirkt . Diese Verschmelzung eines Paares kann als zwei Funktionen vom Typ a -> bbzw. vom Typ kodiert werden . b -> b -> b.

type TreeAlgebra a b = (a -> b, b -> b -> b) -- the "two cases" function is encoded as (f, g)
 
data Tree a = Leaf a | Branch (Tree a) (Tree a) -- which turns out to be the initial algebra
 
foldTree :: TreeAlgebra a b -> (Tree a -> b) -- catamorphisms map from (Tree a) to b
foldTree (f, g) (Leaf x)            = f x
foldTree (f, g) (Branch left right) = g (foldTree (f, g) left) (foldTree (f, g) right)

treeDepth :: TreeAlgebra a Integer -- an f-algebra to numbers, which works for any input type
treeDepth = (const 1, \i j -> 1 + max i j)
 
treeSum :: (Num a) => TreeAlgebra a a -- an f-algebra, which works  for any number type 
treeSum = (id, (+))

Allgemeiner Fall

Tiefere kategorietheoretische Studien der Anfangsalgebren zeigen, dass die F-Algebra, die durch Anwendung des Funktors auf ihre eigene Anfangsalgebra erhalten wird, zu dieser isomorph ist.

Starke Typsysteme ermöglichen es uns, die Anfangsalgebra eines Funktors abstrakt fals seinen Fixpunkt a = fa anzugeben . Die rekursiv definierten Katamorphismen können nun einzeilig kodiert werden, wobei die Fallanalyse (wie in den verschiedenen Beispielen oben) durch die fmap gekapselt wird. Da die Domäne der letzteren Objekte im Bild von sind f, springt die Bewertung der Katamorphismen zwischen aund hin und her f a.

type Algebra f a = f a -> a -- the generic f-algebras

newtype Fix f = Iso { invIso :: f (Fix f) } -- gives us the initial algebra for the functor f

cata :: Functor f => Algebra f a -> (Fix f -> a) -- catamorphism from Fix f to a
cata alg = alg . fmap (cata alg) . invIso -- note that invIso and alg map in opposite directions

Nun wieder das erste Beispiel, aber jetzt über die Übergabe des Maybe-Funktors an Fix. Die wiederholte Anwendung des Maybe-Funktors erzeugt eine Typenkette, die jedoch durch den Isomorphismus aus dem Fixpunktsatz vereint werden kann. Wir führen den zeroaus Maybes abgeleiteten Begriff ein Nothingund identifizieren eine Nachfolgefunktion bei wiederholter Anwendung des Just. Auf diese Weise entstehen die natürlichen Zahlen.

type Nat = Fix Maybe
zero :: Nat
zero = Iso Nothing -- every 'Maybe a' has a term Nothing, and Iso maps it into a
successor :: Nat -> Nat
successor = Iso . Just -- Just maps a to 'Maybe a' and Iso maps back to a new term

pleaseWait :: Algebra Maybe String -- again the silly f-algebra example from above
pleaseWait (Just string) = "wait.. " ++ string
pleaseWait Nothing = "go!"

Auch hier wird das Folgende als "warte.. warte.. warte.. warte.. los!" ausgewertet: cata pleaseWait (successor.successor.successor.successor $ zero)

Und nun wieder das Baumbeispiel. Dazu müssen wir den Baumcontainer-Datentyp bereitstellen, damit wir den einrichten können fmap(wir mussten dies nicht für den MaybeFunktor tun , da es Teil der Standardvorstufe ist).

data Tcon a b = TconL a | TconR b b
instance 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 algebra
end :: a -> Tree a
end = Iso . TconL
meet :: Tree a -> Tree a -> Tree a
meet l r = Iso $ TconR l r

treeDepth :: Algebra (Tcon a) Integer -- again, the treeDepth f-algebra example
treeDepth (TconL x)   = 1
treeDepth (TconR y z) = 1 + max y z

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

Siehe auch

• Morphismus
• Morphismen von F-Algebren
  • Von einer Koalgebra zu einer endgültigen Koalgebra: Anamorphismus
  • Ein Anamorphismus gefolgt von einem Katamorphismus: Hylomorphismus
  • Erweiterung der Idee der Katamorphismen: Paramorphismus
  • Erweiterung der Idee der Anamorphismen: Apomorphism

Verweise

Weiterlesen

Externe Links

• Katamorphismen im HaskellWiki
• Katamorphismen von Edward Kmett
• Katamorphismen in F# (Teil 1 , 2 , 3 , 4 , 5 , 6 , 7 ) von Brian McNamara
• Katamorphismen in Haskell