Anamorfismus - Anamorphism

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

Výše uvedený laický popis lze formálně uvést v teorie kategorií: anamorfismus a koindukční typ označuje přiřazení a uhlígebra k jeho jedinečnému morfismus do závěrečná uhlí z endofunctor. Tyto objekty se používají v Funkcionální programování tak jako se odvíjí.

The kategorický duální (aka opak) anamorfismu je katamorfismus.

Anamorfismy ve funkčním programování

v Funkcionální programování, an anamorfismus je zobecněním pojmu se odvíjí na koinduktivní seznamy. Formálně jsou to anamorfózy generické funkce to může korekčně konstruovat výsledek určitého typ a který je parametrizován funkcemi, které určují další jednotlivý krok konstrukce.

Dotčený datový typ je definován jako největší pevný bod ν X. F X funktora F. Díky univerzálnímu majetku konečných uhelníků existuje jedinečný morfismus uhelnice A → ν X. F X pro jakékoli jiné F-coalgebra a: A → F A. Lze tedy definovat funkce z typu A _into_ koinduktivní datový typ zadáním struktury uhlíkové uhlí A na A.

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

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

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

Je to pevný bod funktoru Hodnota F., kde:

data Možná A = Prostě A | Nicdata F hodnota X = Možná (hodnota, X)

Dá se snadno zkontrolovat, zda skutečně typ [hodnota] je izomorfní s Hodnota F [hodnota], a tudíž [hodnota] je pevný bod. (Všimněte si také, že v Haskellu se shodují nejmenší a největší fixní body funktorů, proto jsou indukční seznamy stejné jako koinduktivní, potenciálně nekonečné seznamy.)

The anamorfismus pro seznamy (obvykle známé jako rozvinout) by vytvořil (potenciálně nekonečný) seznam z hodnoty stavu. Typicky rozvinutí přebírá hodnotu stavu X a funkce F která získá buď dvojici hodnoty a nový stav, nebo jednočetné označení konce seznamu. Anamorfismus by pak začínal prvním semínkem, spočítal, zda seznam pokračuje nebo by skončil, a v případě neprázdného seznamu přidal vypočítanou hodnotu k rekurzivnímu volání anamorfózy.

Haskellova definice rozvinutí neboli anamorfismus pro seznamy ana, je následující:

ana :: (Stát -> Možná (hodnota, Stát)) -> Stát -> [hodnota]ana F státStarý = případ F státStarý z            Nic                -> []            Prostě (hodnota, státNový) -> hodnota : ana F státNový

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

F :: Int -> Možná (Int, Int)F proud = nechat jeden Menší = proud - 1            v   -li jeden Menší < 0                   pak Nic                   jiný Prostě (jeden Menší, jeden Menší)

Tato funkce dekrementuje celé číslo a současně jej vygeneruje, dokud nebude záporné, a v tom okamžiku označí konec seznamu. Odpovídajícím způsobem, ana f 3 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 vzoru, zobecňujícího druhou verzi ana pro seznamy.

Například rozvinutí pro stromovou datovou strukturu

 data Strom A = List A | Větev (Strom A) A (Strom A)

je následující

 ana :: (b -> Buď A (b, A, b)) -> b -> Strom A ana uvolnit X = případ uvolnit X z                   Vlevo, odjet A          -> List A                   Že jo (l, X, r) -> Větev (ana uvolnit l) X (ana uvolnit r)

Chcete-li lépe vidět vztah mezi rekurzivním typem a jeho anamorfismem, nezapomeňte Strom a Seznam lze definovat takto:

 nový typ Seznam A = Seznam {unCons :: Možná (A, Seznam A)} nový typ Strom A = Strom {zrušit uzel :: Buď A (Strom A, A, Strom A))}

Analogie s ana se zobrazí přejmenováním b ve svém typu:

 nový typ Seznam A = Seznam {unCons :: Možná (A, Seznam A)} anaList ::       (seznam_a       -> Možná (A, seznam_a)) -> (seznam_a -> Seznam A) nový typ Strom A = Strom {zrušit uzel :: Buď A (Strom A, A, Strom A))} anaTree ::       (strom_a       -> Buď A (strom_a, A, strom_a)) -> (strom_a -> Strom A)

S těmito definicemi má argument konstruktoru typu stejný typ jako návratový typ prvního argumentu ana, s rekurzivními zmínkami typu nahrazenými b.

Dějiny

Jednou z prvních publikací představujících pojem anamorfismu v kontextu programování byla práce Funkční programování s banány, čočkami, obálkami a ostnatým drátem,^[1] podle Erik Meijer et al., který byl v kontextu Squiggol programovací jazyk.

Aplikace

Funkce jako zip a opakovat jsou příklady anamorfismů. zip vezme pár seznamů, řekněme ['a', 'b', 'c'] a [1,2,3] a vrátí seznam párů [('a', 1), ('b', 2) , („c“, 3)]. Opakovat vezme 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:tak jako) (b:bs) = -li (tak jako==[]) || (bs ==[])   - || znamená „nebo“                      pak [(A,b)]                      jiný (A,b):(zip tak jako bs)   opakovat F X = X:(opakovat F (F X))

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

 zip2 = ana unsp ploutev    kde    ploutev (tak jako,bs) = (tak jako==[]) || (bs ==[])     unsp ((A:tak jako), (b:bs)) = ((A,b),(tak jako,bs)) iterovat2 F = ana (\A->(A,F A)) (\X->Nepravdivé)

V jazyce, jako je Haskell, funguje dokonce i abstraktní složit, rozvinout a ana jsou pouze definované termíny, jak jsme viděli z výše uvedených definic.

Anamorfismy v teorii kategorií

v teorie kategorií, anamorfózy jsou kategorický duální z katamorfózy (a katamorfózy jsou kategorickým duálem anamorfismů).

To znamená následující. Předpokládejme (A, ploutev) je finále F-coalgebra pro některé endofunctor F některých kategorie do sebe. ploutev je morfismus z A na FA, a protože se předpokládá, že je konečný, víme, že kdykoli (X, F) Je další F-coalgebra (morfismus F z X na FX), bude existovat jedinečný homomorfismus h z (X, F) do (A, ploutev), to je morfismus h z X na A takhle ploutev . h = Fh . FPak pro každého takového F označujeme ana F ten jedinečně specifikovaný morfismus h.

Jinými slovy, máme následující definující vztah, který je dán pevným F, A, a ploutev 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 ${ displaystyle [! (f) !]}$. Použité závorky jsou známé jako držáky objektivu, po kterém jsou anamorfózy někdy označovány jako čočky.

Viz také

• Morfismus
• Morfismy z F-algebry
  • Od počáteční algebry k algebře: Katamorfismus
  • Anamorfismus následovaný katamorfismem: Hylomorfismus
  • Rozšíření myšlenky katamorfismů: Paramorfismus
  • Rozšíření myšlenky anamorfózy: Apomorfismus

Reference

externí odkazy

• Anamorfismy v Haskellu