Corecursion - Corecursion

Ve vědě o počítačích , corecursion je druh operace, která je dvojí k rekurze . Zatímco rekurze funguje analyticky, začíná na datech dále od základního případu a rozděluje je na menší data a opakuje se, dokud jeden nedosáhne základního případu, corecursion funguje synteticky, vychází ze základního případu a vytváří jej, iterativně produkuje data dále odstraněná z základní případ. Jednoduše řečeno, korekční algoritmy používají data, která sami produkují, kousek po kousku, jakmile jsou k dispozici a potřebují, k výrobě dalších bitů dat. Podobným, ale odlišným konceptem je generativní rekurze, které může postrádat určitý „směr“, který je vlastní korekci a rekurzi.

Tam, kde rekurze umožňuje programům pracovat s libovolně složitými daty, pokud je lze redukovat na jednoduchá data (základní případy), umožňuje rekurze programům vytvářet libovolně složité a potenciálně nekonečné datové struktury, jako jsou proudy , pokud je lze vytvořit z jednoduchých dat (základních případů) v posloupnosti konečných kroků. Kde rekurze nemusí skončit, nikdy nedosáhne základního stavu, korekce začíná od základního stavu, a tak produkuje další kroky deterministicky, i když může probíhat neomezeně (a tudíž nemusí být ukončena pod přísným hodnocením), nebo může spotřebovat více, než produkuje a se tak stávají non- produktivní . Mnoho funkcí, které jsou tradičně analyzovány jako rekurzivní, lze alternativně a pravděpodobně přirozeněji interpretovat jako jádrové funkce, které jsou v dané fázi ukončeny, například relace opakování , jako je faktoriál.

Corecursion může produkovat konečné i nekonečné datové struktury jako výsledky a může využívat datové struktury s vlastním odkazem . Corecursion se často používá ve spojení s líným hodnocením , aby se vytvořila pouze konečná podmnožina potenciálně nekonečné struktury (spíše než pokus o vytvoření celé nekonečné struktury najednou). Corecursion je obzvláště důležitý koncept ve funkčním programování , kde corecursion a codata umožňují celkovým jazykům pracovat s nekonečnými datovými strukturami.

Příklady

Corecursion lze chápat na rozdíl od rekurze, která je známější. Zatímco corecursion je primárně zajímavý ve funkčním programování, lze jej ilustrovat pomocí imperativního programování, které se provádí níže pomocí generátoru v Pythonu. V těchto příkladech jsou použity lokální proměnné a přiřazené hodnoty imperativně (destruktivně), i když to není nutné v korekci v čistém funkčním programování. V čistém funkčním programování, místo přiřazování k lokálním proměnným, tyto vypočítané hodnoty tvoří neměnnou sekvenci a k ​​předchozím hodnotám se přistupuje pomocí vlastního odkazu (pozdější hodnoty v sekvenci odkazují na dřívější hodnoty v posloupnosti, která se má vypočítat). Přiřazení to jednoduše vyjadřují v imperativním paradigmatu a výslovně určují, kde k výpočtům dochází, což slouží k objasnění výkladu.

Faktoriální

Klasickým příkladem rekurze je výpočet faktoriálu , který je definován rekurzivně 0! : = 1 a n! : = n × (n - 1)! .

Aby rekurzivně vypočítal svůj výsledek na daném vstupu, volá rekurzivní funkce (kopii) sama s jiným (nějakým způsobem "menším") vstupem a použije výsledek tohoto volání ke konstrukci svého výsledku. Rekurzivní volání dělá totéž, pokud nebylo dosaženo základního případu . V procesu se tak vyvíjí zásobník volání . Například pro výpočet Fac (3) , toto rekurzivně volá postupně Fac (2) , Fac (1) , Fac (0) ("navíjení" zásobníku), kdy rekurze končí s Fac (0) = 1 a pak se zásobník odvíjí v obráceném pořadí a výsledky se počítají na zpáteční cestě podél zásobníku volání do počátečního rámce volání fac (3), který používá výsledek Fac (2) = 2 k výpočtu konečného výsledku jako 3 × 2 = 3 × fac (2) =: fac (3) a nakonec vrátit fac (3) = 6 . V tomto příkladu funkce vrací jednu hodnotu.

Tento odvíjení zásobníku lze vysvětlit definováním faktoriálu korekčně , jako iterátor , kde jeden začíná případem , pak z této počáteční hodnoty konstruuje faktoriální hodnoty pro zvyšování čísel 1, 2, 3 ... jako ve výše uvedené rekurzivní definici s „time šíp“ obrátil, jak to bylo tím, že čte to dozadu as . Corecursive algoritmus tak definována vytváří proud o všech faktoriálů. To může být konkrétně implementováno jako generátor . Symbolicky, když si všimneme, že výpočet další faktoriální hodnoty vyžaduje sledování obou n a f (předchozí faktoriální hodnota), může to být reprezentováno jako: ${\ displaystyle 1 =: 0!}$${\ displaystyle n! \ times (n + 1) = :( n + 1)!}$

${\ displaystyle n, f = (0,1) :( n + 1, f \ krát (n + 1))}$

nebo v Haskellu ,

  (\(n,f) -> (n+1, f*(n+1))) `iterate` (0,1)

což znamená „počínaje od , v každém kroku se další hodnoty počítají jako “. To je matematicky ekvivalentní a téměř identické s rekurzivní definicí, ale zdůrazňuje se, že faktoriální hodnoty se vytvářejí , přecházejí od počátečního případu dopředu, spíše než se počítají po prvním přechodu dozadu, dolů k základnímu případu, s poklesem . Přímý výstup korekční funkce neobsahuje pouze hodnoty faktoriálu , ale zahrnuje také pro každou hodnotu pomocná data jejího indexu n v pořadí, takže lze mezi nimi podle potřeby vybrat jakýkoli konkrétní výsledek. ${\ displaystyle n, f = 0,1}$${\ displaystyle n + 1, f \ krát (n + 1)}$${\ displaystyle +1}$${\ displaystyle -1}$${\ displaystyle n!}$

Existuje spojení s denotační sémantikou , kde se takto značně budují denotace rekurzivních programů .

V Pythonu lze rekurzivní faktoriální funkci definovat jako:

def factorial(n):
    """Recursive factorial function."""
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

To by se dalo nazvat například jako factorial(5) výpočet 5! .

Odpovídající korekční generátor lze definovat jako:

def factorials():
    """Corecursive generator."""
    n, f = 0, 1
    while True:
        yield f
        n, f = n + 1, f * (n + 1)

To generuje nekonečný proud faktoriálů v pořadí; jeho konečná část může být vyrobena:

def n_factorials(k):
    n, f = 0, 1
    while n <= k:
        yield f
        n, f = n + 1, f * (n + 1)

To by pak mohlo být voláno k výrobě faktoriálů až 5! přes:

for f in n_factorials(5):
    print(f)

Pokud nás zajímá pouze určitý faktoriál, můžeme vzít pouze poslední hodnotu, nebo můžeme sloučit produkci a přístup do jedné funkce,

def nth_factorial(k):
    n, f = 0, 1
    while n < k:
        n, f = n + 1, f * (n + 1)
    yield f

Jak lze snadno vidět zde, je to prakticky ekvivalentní (pouhým nahrazením return jediného yield tam) technice argumentu akumulátoru pro rekurzi ocasu , odvinutou do explicitní smyčky. Dá se tedy říci, že koncept korekurze je vysvětlením ztělesnění iterativních výpočetních procesů pomocí rekurzivních definic, je-li to relevantní.

Fibonacciho sekvence

Stejným způsobem lze Fibonacciho sekvenci reprezentovat jako:

${\ displaystyle a, b = (0,1) :( b, a + b)}$

Protože Fibonacciho sekvence je relací opakování řádu 2, korekční relace musí sledovat dva po sobě jdoucí termíny, přičemž odpovídající posunutí vpřed o jeden krok, a odpovídající výpočtu dalšího termínu. To pak může být implementováno následovně (pomocí paralelního přiřazení ): ${\ displaystyle (b, -)}$${\ displaystyle (-, a + b)}$

def fibonacci_sequence():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

V Haskellu,

 map fst ( (\(a,b) -> (b,a+b)) `iterate` (0,1) )

Traverz stromu

Traverz stromů pomocí přístupu založeného na hloubce je klasickým příkladem rekurze. Duálně lze průchod na šířku velmi přirozeně implementovat pomocí corecursion.

Bez konkrétního použití rekurze nebo korekce lze procházet strom tak, že začnete v kořenovém uzlu, umístíte jeho podřízené uzly do datové struktury a poté iterujete odstraněním uzlu za uzlem z datové struktury, zatímco do každé datové struktury umístíte podřízené uzly každého potomka. . Pokud je datovou strukturou zásobník (LIFO), získá se tak průchod hloubkou první a pokud je datovou strukturou fronta (FIFO), získá se průchod první šířkou.

Pomocí rekurze lze provést (post-order) průchod hloubky první spuštěním v kořenovém uzlu a rekurzivním procházením každého podřízeného podstromu (podstrom založený na každém podřízeném uzlu) - druhý podřízený podstrom nezačne zpracovávat, dokud první podstrom je dokončen. Jakmile je dosaženo listového uzlu nebo jsou vyčerpány podřízené větve uzlu, je navštíven samotný uzel (např. Je odeslána hodnota samotného uzlu). V tomto případě zásobník volání (rekurzivních funkcí) funguje jako zásobník, který je iterován.

Pomocí corecursion lze provést průchod na šířku nejprve spuštěním v kořenovém uzlu, výstupem jeho hodnoty a následným průchodem podstromů - tj. Předáním celého seznamu podstromů k dalšímu kroku (nikoli jedinému podstromu, protože v dalším rekurzivním přístupu) - v dalším kroku se vydá hodnota všech jejich kořenových uzlů, poté se předají jejich podřízené podstromy atd. V tomto případě funguje jako fronta funkce generátoru, vlastně samotná výstupní sekvence. Stejně jako v příkladu faktoriálu (výše), kde byla pomocná informace indexu (ve kterém kroku byl jeden, n ) posunuta dopředu, kromě skutečného výstupu n ! V tomto případě je pomocná informace zbývajících podstromů tlačil dopředu, kromě skutečného výstupu. Symbolicky:

${\ displaystyle v, t = ([], [FullTree]) :( RootValues ​​(v, t), ChildTrees (t))}$

což znamená, že v každém kroku jeden vydá seznam hodnot kořenových uzlů a poté pokračuje do podřízených podstromů. Generování pouze hodnot uzlů z této sekvence jednoduše vyžaduje vyřazení dat pomocného podřízeného stromu a potom sloučení seznamu seznamů (hodnoty jsou zpočátku seskupeny podle úrovně (hloubky); sloučení (rozdělení) poskytuje plochý lineární seznam). V Haskellu,

 concatMap fst ( (\(v, t) -> (rootValues v t, childTrees t)) `iterate` ([], fullTree) )

Mohou být porovnány následovně. Rekurzivní průchod zpracovává listový uzel ( dole ) jako základní případ (pokud nejsou žádné děti, stačí zadat hodnotu) a analyzuje strom do podstromů, přičemž každý z nich prochází postupně, což nakonec vede pouze k listovým uzlům - skutečný list uzly a uzly větví, jejichž děti již byly řešeny (oříznuto níže ). Naproti tomu korekční traverz zpracovává kořenový uzel ( nahoře ) jako základní případ (daný uzel, nejprve vygeneruje hodnotu), považuje strom za syntetizovaný z kořenového uzlu a jeho podřízených, poté vytvoří jako pomocný výstup a seznam podstromů v každém kroku, které jsou potom vstupem pro další krok - podřízené uzly původního kořene jsou kořenovými uzly v dalším kroku, protože jejich rodiče již byli vypořádáni ( výše odříznuto ). V rekurzivním procházení existuje rozdíl mezi listovými uzly a uzly větví, zatímco v jádrovém procházení není žádný rozdíl, protože každý uzel je považován za kořenový uzel podstromu, který definuje.

Je pozoruhodné, že vzhledem k nekonečnému stromu bude korekční průchod první šířkou procházet všemi uzly, stejně jako pro konečný strom, zatímco rekurzivní průchod hloubkou první půjde dolů o jednu větev a nebude procházet všemi uzly, a skutečně, pokud bude procházet po objednávce , jako v tomto příkladu (nebo v pořadí), nenavštíví vůbec žádné uzly, protože nikdy nedosáhne listu. To ukazuje užitečnost korekcí spíše než rekurze pro práci s nekonečnými datovými strukturami.

V Pythonu to lze implementovat následovně. Obvyklý přechod po objednávce do hloubky lze definovat jako:

def df(node):
    """Post-order depth-first traversal."""
    if node is not None:
        df(node.left)
        df(node.right)
        print(node.value)

To lze poté vyvolat df(t) a vytisknout hodnoty uzlů stromu v pořadí po objednávce hloubka-první.

Šířící první korekční generátor lze definovat jako:

def bf(tree):
    """Breadth-first corecursive generator."""
    tree_list = [tree]
    while tree_list:
        new_tree_list = []
        for tree in tree_list:
            if tree is not None:
                yield tree.value
                new_tree_list.append(tree.left)
                new_tree_list.append(tree.right)
        tree_list = new_tree_list

To pak může být voláno k tisku hodnot uzlů stromu v pořadí nejdříve:

for i in bf(t):
    print(i)

Definice

Počáteční datové typy lze definovat jako nejméně fixní bod ( až do izomorfismu ) nějaké rovnice typu; izomorfismus je pak dán počáteční algebry . Duální, konečné (nebo koncové) datové typy lze definovat jako největší fixní bod rovnice typu; izomorfismus je pak dán závěrečnou uhlím .

Pokud je doménou diskurzu kategorie množin a celkových funkcí, pak konečné datové typy mohou obsahovat nekonečné, nepodložené hodnoty, zatímco počáteční typy nikoli. Na druhou stranu, pokud je doménou diskurzu kategorie úplných dílčích řádů a spojitých funkcí , která zhruba odpovídá programovacímu jazyku Haskell , pak se konečné typy shodují s počátečními typy a odpovídající konečná koalgebra a počáteční algebra tvoří izomorfismus.

Corecursion je pak technika pro rekurzivní definování funkcí, jejichž rozsah (codomain) je konečný datový typ, duální vzhledem k tomu, že běžná rekurze rekurzivně definuje funkce, jejichž doménou je počáteční datový typ.

Níže uvedená diskuse poskytuje několik příkladů v Haskellu, které odlišují jádro. Zhruba řečeno, pokud by se jednalo o přenesení těchto definic do kategorie množin, stále by byly korektivní. Toto neformální použití je v souladu se stávajícími učebnicemi o Haskellovi. Příklady použité v tomto článku předcházejí pokusům definovat korekci a vysvětlit, o co jde.

Diskuse

Pravidlo pro primitivní korekci na codata je dvojí k pravidlu pro primitivní rekurzi na datech. Místo toho, abychom sestupovali po argumentu porovnáváním vzorů na jeho konstruktorech (které byly dříve vyvolány, takže dostáváme hotový údaj a dostaneme se k jeho dílčím částem, tj. „Polím“), vystoupáme na výsledek vyplněním jeho „destruktorů“ (neboli „pozorovatelů“, které se někde budou nazývat později - takže vlastně voláme konstruktor a vytváříme další kousek výsledku, který bude později pozorován). Corecursion tedy vytváří (potenciálně nekonečná) codata, zatímco běžná rekurze analyzuje (nutně konečná) data. Obyčejná rekurze nemusí být použitelná pro codata, protože nemusí být ukončena. Naopak, korekce není nezbytně nutná, pokud jsou výsledným typem data, protože data musí být konečná.

V „Programování s proudy v Coq: případová studie: Eratosthenovo síto“ najdeme

hd (conc a s) = a               
tl (conc a s) = s

(sieve p s) = if div p (hd s) then sieve p (tl s)
              else conc (hd s) (sieve p (tl s))

hd (primes s) = (hd s)          
tl (primes s) = primes (sieve (hd s) (tl s))

kde prvočísla „jsou získána aplikací operace prvočísel na stream (Enu 2)“. V návaznosti na výše uvedenou notaci lze posloupnost prvočísel (s předponou 0 pro vyhodnocení) a číselných proudů, které se postupně prosívají, reprezentovat jako

${\ displaystyle p, s = (0, [2 ..]) :( hd (s), síto (hd (s), tl (s)))}$

nebo v Haskellu,

(\(p, s@(h:t)) -> (h, sieve h t)) `iterate` (0, [2..])

Autoři diskutují o tom, že sieve není zaručeno, že definice produktu bude vždy produktivní , a mohla by se zaseknout, např. Pokud bude vyvolána [5,10..] jako počáteční proud.

Zde je další příklad v Haskellu. Následující definice vytvoří seznam Fibonacciho čísel v lineárním čase:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Tento nekonečný seznam závisí na líném vyhodnocení; prvky jsou počítány podle potřeby a v paměti jsou vždy explicitně zastoupeny pouze konečné předpony. Tato funkce umožňuje ukončit algoritmy na částech codata; takové techniky jsou důležitou součástí programování Haskell.

To lze provést také v Pythonu:

from itertools import tee, chain, islice, imap

def add(x, y):
    return x + y

def fibonacci():
    def deferred_output():
        for i in output:
            yield i
    result, c1, c2 = tee(deferred_output(), 3)
    paired = imap(add, c1, islice(c2, 1, None))
    output = chain([0, 1], paired)
    return result

for i in islice(fibonacci(), 20):
    print(i)

Definici zipWith lze podtrhnout, což vede k tomuto:

fibs = 0 : 1 : next fibs
  where
    next (a: t@(b:_)) = (a+b):next t

Tento příklad využívá datovou strukturu s vlastním odkazem . Obyčejná rekurze využívá samoreferenční funkce , ale nepřijímá samoreferenční data. To však není pro příklad Fibonacciho zásadní. Lze jej přepsat takto:

fibs = fibgen (0,1)
fibgen (x,y) = x : fibgen (y,x+y)

To využívá pouze samoreferenční funkci k vytvoření výsledku. Pokud by byl použit s konstruktorem přísného seznamu, byl by příkladem rekurze uprchlíka, ale s konstruktorem nestriktního seznamu tato střežená rekurze postupně vytváří neurčitě definovaný seznam.

Corecursion nemusí vytvářet nekonečný objekt; obzvláště dobrým příkladem tohoto jevu je korekční fronta. Následující definice vytváří průchod binárního stromu v šířce jako první v lineárním čase:

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

bftrav :: Tree a b -> [Tree a b]
bftrav tree = queue
  where
    queue = tree : gen 1 queue

    gen  0   p                 =         []           
    gen len (Leaf   _     : s) =         gen (len-1) s 
    gen len (Branch _ l r : s) = l : r : gen (len+1) s

Tato definice vezme počáteční strom a vytvoří seznam podstromů. Tento seznam slouží dvojímu účelu jako fronta i výsledek ( gen len p vytváří jeho výstupní len zářezy po jeho zadním zpětném ukazateli p , podél queue ). Je konečný právě tehdy, pokud je počáteční strom konečný. Délka fronty musí být výslovně sledována, aby bylo zajištěno ukončení; toto lze bezpečně vyloučit, pokud se tato definice použije pouze na nekonečné stromy.

Další obzvláště dobrý příklad poskytuje řešení problému šíření štítků první. Funkce label navštíví každý uzel v binárním stromu nejdříve v šíři a nahradí každý štítek celým číslem, každé následující celé číslo je větší než poslední o jedno. Toto řešení využívá datovou strukturu s vlastním odkazem a binární strom může být konečný nebo nekonečný.

label :: Tree a b -> Tree Int Int 
label t = t′
    where
    (t′, ns) = go t (1:ns)

    go :: Tree a b    -> [Int]  -> (Tree Int Int, [Int])
    go   (Leaf   _    ) (n:ns) = (Leaf   n       , n+1 : ns  )
    go   (Branch _ l r) (n:ns) = (Branch n l′ r′ , n+1 : ns′′)
                                where
                                  (l′, ns′ ) = go l ns
                                  (r′, ns′′) = go r ns′

Apomorphism (například anamorphism , jako Unfold ) je forma corecursion stejným způsobem, že paramorphism (jako je catamorphism , jako je například lom ) je forma rekurze.

Coq důkaz asistent podporuje corecursion a coinduction pomocí příkazu CoFixpoint.

Dějiny

Corecursion, označovaný jako kruhové programování, se datuje přinejmenším do ( Bird 1984 ), který připisuje John Hughes a Philip Wadler ; obecnější formy byly vyvinuty v roce ( Allison 1989 ) . Původní motivace zahrnovala produkci efektivnějších algoritmů (v některých případech umožnění 1 předání dat namísto vyžadování více průchodů) a implementaci klasických datových struktur, jako jsou dvojnásobně propojené seznamy a fronty, ve funkčních jazycích. chyba harv: žádný cíl: CITEREFAllison1989 ( nápověda )

Viz také

• Bisimulace
• Koindukce
• Rekurze
• Anamorfismus

Poznámky

Reference