Anamorphism - Anamorphism

V počítačovém programování je anamorphism funkce, která generuje sekvenci opakovaným použitím funkce na její předchozí výsledek. Začnete nějakou hodnotou A a použijete na ni funkci f, abyste získali B. Poté použijete f na B, abyste získali C, a tak dále, dokud nebude dosaženo nějaké ukončovací podmínky. Anamorphism je funkce, která generuje seznam A, B, C atd. Anamorfismus si můžete představit jako rozvinutí počáteční hodnoty do sekvence.

Výše uvedený laickou popis lze konstatovat, více formálně teorie kategorií : anamorphism z coinductive typu označuje přiřazení coalgebra svému jedinečnému morfismu ke konečnému coalgebra části s endofunctor . Tyto objekty se používají ve funkčním programování jako rozvinutí .

Kategorické dual (aka opak) v anamorphism je catamorphism .

Anamorfismy ve funkcionálním programování

Ve funkčním programování , An anamorphism je zobecněním pojmu se odehrává na coinductive seznamech . Formálně jsou anamorfismy generické funkce, které mohou jádrově konstruovat výsledek určitého typu a které jsou parametrizovány funkcemi, které určují další jednotlivý krok konstrukce.

Dotyčný datový typ je definován jako největší pevný bod ν X. FX z funktoru F . Podle univerzální vlastnosti konečných cobrgebras existuje jedinečný morfismus cogegebra A → ν X. FX pro jakýkoli jiný F -coalgebra a: A → FA . Tak, jeden může definovat funkce z typu A _into_ s coinductive datový zadáním coalgebra strukturu A na A .

Příklad: Potenciálně nekonečné seznamy

Jako příklad je jako potenciální bod [hodnota] = ν X uveden typ potenciálně nekonečných seznamů (s prvky pevné hodnoty typu ) . hodnota × X + 1 , tj. seznam se skládá buď z hodnoty a dalšího seznamu, nebo je prázdný. A (pseudo) Haskell -Definition může vypadat takto:

data [value] = (value:[value]) | []

Je to pevný bod funktoru F value, kde:

data Maybe a = Just a | Nothing
data F value x = Maybe (value, x)

Lze snadno zkontrolovat, že typ [value]je skutečně izomorfní F value [value], a tedy [value]je pevným bodem. (Všimněte si také, že v Haskellu se shodují nejmenší a největší pevné body funktorů, proto jsou indukční seznamy stejné jako koinduktivní, potenciálně nekonečné seznamy.)

Anamorphism pro seznamy (pak obvykle známý jako Unfold ) postaví (potenciálně nekonečný) seznam z hodnoty stavu. Typicky rozvinutí přebírá hodnotu stavu xa funkci, fkterá poskytuje buď dvojici hodnoty a nový stav, nebo singleton k označení konce seznamu. Anamorfismus by pak začal prvním semenem, vypočítal, zda seznam pokračuje nebo končí, a v případě neprázdného seznamu přepočítal vypočítanou hodnotu do rekurzivního volání anamorfismu.

Haskellova definice rozvinutí neboli anamorfismu pro seznamy, nazývaná ana, je následující:

ana :: (state -> Maybe (value, state)) -> state -> [value]
ana f stateOld = case f stateOld of
            Nothing                -> []
            Just (value, stateNew) -> value : ana f stateNew

Nyní můžeme implementovat docela obecné funkce pomocí ana , například odpočítávání:

f :: Int -> Maybe (Int, Int)
f current = let oneSmaller = current - 1
            in   if oneSmaller < 0
                   then Nothing
                   else Just (oneSmaller, oneSmaller)

Tato funkce sníží celé číslo a současně jej vydá, dokud nebude záporné, a v tomto okamžiku označí konec seznamu. V souladu s ana f 3tím vypočítá seznam [2,1,0].

Anamorfismy na jiných datových strukturách

Anamorfismus lze definovat pro jakýkoli rekurzivní typ podle obecného vzorce generalizujícího druhou verzi ana pro seznamy.

Například rozvinutí stromové datové struktury

 data Tree a = Leaf a | Branch (Tree a) a (Tree a)

je následující

 ana :: (b -> Either a (b, a, b)) -> b -> Tree a
 ana unspool x = case unspool x of
                   Left a          -> Leaf a
                   Right (l, x, r) -> Branch (ana unspool l) x (ana unspool r)

Chcete -li lépe vidět vztah mezi rekurzivním typem a jeho anamorfismem, všimněte si toho Treea Listlze jej definovat takto:

 newtype List a = List {unCons :: Maybe (a, List a)}

 newtype Tree a = Tree {unNode :: Either a (Tree a, a, Tree a))}

Analogie s se anaobjeví přejmenováním bna jeho typ:

 newtype List a = List {unCons :: Maybe (a, List a)}
 anaList ::       (list_a       -> Maybe (a, list_a)) -> (list_a -> List a)

 newtype Tree a = Tree {unNode :: Either a (Tree a, a, Tree a))}
 anaTree ::       (tree_a       -> Either a (tree_a, a, tree_a)) -> (tree_a -> Tree a)

U těchto definic má argument konstruktoru typu stejný typ jako návratový typ prvního argumentu s ana, přičemž rekurzivní zmínky o typu jsou nahrazeny b.

Dějiny

Jednou z prvních publikací, které zavedly pojem anamorfismu v kontextu programování, byl dokument Funkční programování s banány, čočkami, obálkami a ostnatým drátem od Erika Meijera a kol. , což bylo v kontextu programovacího jazyka Squiggol .

Aplikace

Funkce jako zipa iteratejsou příklady anamorfismů. zipvezme pár seznamů, řekněme ['a', 'b', 'c'] a [1,2,3] a vrátí seznam párů [('a', 1), ('b', 2) , ('c', 3)]. Iteratevezme věc, x a funkci, f, z takových věcí na takové věci, a vrátí nekonečný seznam, který pochází z opakované aplikace f, tj. seznam [x, (fx), (f (fx)), ( f (f (fx))), ...].

 zip (a:as) (b:bs) = if (as==[]) || (bs ==[])   -- || means 'or'
                      then [(a,b)]
                      else (a,b):(zip as bs) 
 
 iterate f x = x:(iterate f (f x))

Abychom to dokázali, můžeme implementovat obojí pomocí našeho generického rozvinutí anapomocí jednoduché rekurzivní rutiny:

 zip2 = ana unsp fin
    where
    fin (as,bs) = (as==[]) || (bs ==[]) 
    unsp ((a:as), (b:bs)) = ((a,b),(as,bs))

 iterate2 f = ana (\a->(a,f a)) (\x->False)

V jazyce, jako je Haskell, dokonce i abstraktní funkce fold, unfolda anajsou pouze definovanými termíny, jak jsme viděli z definic uvedených výše.

Anamorphismy v teorii kategorií

V teorii kategorie , anamorphisms jsou kategorické dvojí z catamorphisms (a catamorphisms jsou kategorické dvojí anamorphisms).

To znamená následující. Předpokládejme ( A , fin ) je konečná F -coalgebra pro nějaký endofunktor F nějaké kategorie do sebe. Tak fin je morphism od A do FA , a protože se předpokládá, že konečná víme, že vždy, když ( X , f ) je další F -coalgebra (morfizmus f z X až FX ), bude jedinečný homomorphism h od ( X , f ) do ( A , fin ), to je morfismus h od X do A takový, že fin . h = Fh . f . Pak pro každé takové f označíme analogicky f, že jedinečně specifikovaný morfismus h .

Jinými slovy, máme následující definující vztah, daný určitými pevnými F , A a fin, jak je uvedeno výše:

• ${\ Displaystyle h = \ mathrm {ana} \ f}$
• ${\ Displaystyle \ mathrm {fin} \ circ h = Fh \ circ f}$

Zápis

Zápis pro ana f nalezený v literatuře je . Použité závorky jsou známé jako závorky na čočky , po nichž se anamorfizmy někdy označují jako čočky . ${\ displaystyle [\! (f) \!]}$

Viz také

• Morfismus
• Morfismy F-algeber
  • Od počáteční algebry k algebře: katamorfismus
  • Anamorphism následovaný katamorphism: Hylomorphism
  • Rozšíření myšlenky katamorfismů: Paramorphism
  • Rozšíření myšlenky anamorfismů: apomorfismus

Reference

externí odkazy

• Anamorphismy v Haskellu