Corecursion - Corecursion

En informática , la correcursión es un tipo de operación que es dual a la recursividad . Mientras que la recursividad funciona analíticamente, comenzando con datos más alejados de un caso base y dividiéndolos en datos más pequeños y repitiéndolos hasta que uno llega a un caso base, corecursion funciona sintéticamente, comenzando desde un caso base y construyéndolo, produciendo iterativamente datos extraídos de un caso base. En pocas palabras, los algoritmos corecursivos utilizan los datos que ellos mismos producen, bit a bit, a medida que están disponibles y son necesarios para producir más bits de datos. Un concepto similar pero distinto es la recursividad generativa, que puede carecer de una "dirección" definida inherente a la recursividad y la recursividad.

Cuando la recursividad permite que los programas operen con datos arbitrariamente complejos, siempre que puedan reducirse a datos simples (casos base), corecursion permite a los programas producir estructuras de datos arbitrariamente complejas y potencialmente infinitas, como flujos , siempre que se puedan producir a partir de datos simples (casos base) en una secuencia de pasos finitos . Donde la recursividad no puede terminar, sin alcanzar nunca un estado base, la correcursión comienza desde un estado base y, por lo tanto, produce pasos posteriores de manera determinista, aunque puede continuar indefinidamente (y por lo tanto no terminar bajo una evaluación estricta), o puede consumir más de lo que produce y por lo tanto se vuelven no productivos . Muchas funciones que tradicionalmente se analizan como recursivas pueden alternativamente, y posiblemente de manera más natural, ser interpretadas como funciones corecursivas que terminan en una etapa determinada, por ejemplo, relaciones de recurrencia como la factorial.

Corecursion puede producir estructuras de datos tanto finitas como infinitas como resultados, y puede emplear estructuras de datos autorreferenciales . Corecursion se usa a menudo junto con la evaluación perezosa , para producir solo un subconjunto finito de una estructura potencialmente infinita (en lugar de intentar producir una estructura infinita completa a la vez). Corecursion es un concepto particularmente importante en la programación funcional , donde corecursion y codata permiten que los lenguajes totales funcionen con estructuras de datos infinitas.

Ejemplos

Corecursion se puede entender en contraste con la recursividad, que es más familiar. Si bien corecursion es de interés principalmente en la programación funcional, se puede ilustrar utilizando la programación imperativa, que se realiza a continuación utilizando la función del generador en Python. En estos ejemplos se utilizan variables locales y se les asignan valores imperativamente (destructivamente), aunque estos no son necesarios en la correcursión en la programación funcional pura. En la programación funcional pura, en lugar de asignar a variables locales, estos valores calculados forman una secuencia invariable, y se accede a los valores anteriores mediante autoreferencia (los valores posteriores en la secuencia hacen referencia a valores anteriores en la secuencia que se va a calcular). Las asignaciones simplemente expresan esto en el paradigma imperativo y especifican explícitamente dónde ocurren los cálculos, lo que sirve para aclarar la exposición.

Factorial

Un ejemplo clásico de recursividad es calcular el factorial , que se define recursivamente por 0. : = 1 y n! : = n × (n - 1)! .

Para calcular recursivamente su resultado en una entrada dada, una función recursiva llama (una copia de) a sí misma con una entrada diferente ("más pequeña" de alguna manera) y usa el resultado de esta llamada para construir su resultado. La llamada recursiva hace lo mismo, a menos que se haya alcanzado el caso base . Por tanto, se desarrolla una pila de llamadas en el proceso. Por ejemplo, para calcular fac (3) , esto llama recursivamente a su vez fac (2) , fac (1) , fac (0) ("liquidación" de la pila), en cuyo punto la recursión termina con fac (0) = 1 , y luego la pila se desenrolla en orden inverso y los resultados se calculan en el camino de regreso a lo largo de la pila de llamadas al marco de llamada inicial fac (3) que usa el resultado de fac (2) = 2 para calcular el resultado final como 3 × 2 = 3 × fac (2) =: fac (3) y finalmente devuelve fac (3) = 6 . En este ejemplo, una función devuelve un solo valor.

Este desenrollamiento de la pila se puede explicar, definiendo el núcleo factorial cursivamente , como un iterador , donde uno comienza con el caso de , luego a partir de este valor inicial se construyen valores factoriales para los números crecientes 1, 2, 3 ... como en la definición recursiva anterior con "flecha del tiempo" invertida, por así decirlo, al leerla al revés como . El algoritmo corecursivo así definido produce un flujo de todos los factoriales. Esto puede implementarse concretamente como generador . Simbólicamente, teniendo en cuenta que calcular el siguiente valor factorial requiere realizar un seguimiento de n y f (un valor factorial anterior), esto se puede representar como: ${\ Displaystyle 1 =: 0!}$${\ Displaystyle n! \ times (n + 1) = :( n + 1)!}$

${\ Displaystyle n, f = (0,1) :( n + 1, f \ times (n + 1))}$

o en Haskell ,

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

es decir, "a partir de , en cada paso, los siguientes valores se calculan como ". Esto es matemáticamente equivalente y casi idéntica a la definición recursiva, pero la hace hincapié en que los valores factoriales se están construyendo arriba , yendo hacia delante desde el caso de partida, en lugar de ser calculada después de la primera yendo hacia atrás, hacia abajo con el caso base, con un decremento. La salida directa de la función corecursiva no solo contiene los valores factoriales , sino que también incluye para cada valor los datos auxiliares de su índice n en la secuencia, de modo que cualquier resultado específico puede seleccionarse entre todos ellos, como y cuando sea necesario. ${\ Displaystyle n, f = 0,1}$${\ Displaystyle n + 1, f \ times (n + 1)}$${\ displaystyle +1}$${\ Displaystyle -1}$${\ Displaystyle n!}$

Existe una conexión con la semántica denotacional , donde las denotaciones de programas recursivos se construyen corecursivamente de esta manera.

En Python, una función factorial recursiva se puede definir como:

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

¡Esto podría entonces llamarse, por ejemplo, factorial(5) para calcular 5! .

Un generador corecursivo correspondiente se puede definir como:

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

Esto genera un flujo infinito de factoriales en orden; una porción finita puede ser producida por:

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

¡Esto podría entonces ser llamado para producir los factoriales hasta 5! vía:

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

Si solo estamos interesados ​​en un determinado factorial, solo se puede tomar el último valor, o podemos fusionar la producción y el acceso en una función,

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

Como se puede ver fácilmente aquí, esto es prácticamente equivalente (simplemente sustituyendo return el único yield allí) a la técnica del argumento acumulador para la recursividad de la cola , desenrollada en un bucle explícito. Por lo tanto, se puede decir que el concepto de correcursión es una explicación de la encarnación de los procesos de cálculo iterativo mediante definiciones recursivas, cuando corresponda.

secuencia Fibonacci

De la misma manera, la secuencia de Fibonacci se puede representar como:

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

Debido a que la secuencia de Fibonacci es una relación de recurrencia de orden 2, la relación corecursiva debe rastrear dos términos sucesivos, con el correspondiente para avanzar un paso y el correspondiente para calcular el siguiente término. Luego, esto se puede implementar de la siguiente manera (usando asignación en paralelo ): ${\ Displaystyle (b, -)}$${\ Displaystyle (-, a + b)}$

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

En Haskell,

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

Cruce de árboles

El recorrido del árbol a través de un enfoque de profundidad es un ejemplo clásico de recursividad. Doblemente, el recorrido en amplitud primero se puede implementar de forma muy natural a través de corecursion.

Sin usar recursividad o correcursión específicamente, uno puede atravesar un árbol comenzando en el nodo raíz, colocando sus nodos secundarios en una estructura de datos, luego iterando eliminando nodo tras nodo de la estructura de datos mientras coloca a los hijos de cada nodo eliminado nuevamente en esa estructura de datos . Si la estructura de datos es una pila (LIFO), esto produce un recorrido de profundidad primero, y si la estructura de datos es una cola (FIFO), esto produce un recorrido de ancho primero.

Usando la recursividad, se puede implementar un recorrido en profundidad (posterior al pedido) comenzando en el nodo raíz y atravesando recursivamente cada subárbol secundario por turno (el subárbol basado en cada nodo secundario); el segundo subárbol secundario no comienza a procesarse hasta que El primer subárbol secundario está terminado. Una vez que se alcanza un nodo de hoja o se han agotado los hijos de un nodo de rama, se visita el propio nodo (por ejemplo, se emite el valor del propio nodo). En este caso, la pila de llamadas (de las funciones recursivas) actúa como la pila sobre la que se itera.

Usando corecursion, se puede implementar un recorrido de amplitud primero comenzando en el nodo raíz, dando salida a su valor, luego atravesando primero los subárboles en amplitud, es decir, pasando la lista completa de subárboles al siguiente paso (no un solo subárbol, como en el enfoque recursivo) - en el siguiente paso, emitir el valor de todos sus nodos raíz, luego pasar sus subárboles secundarios, etc. En este caso, la función generadora, de hecho la secuencia de salida, actúa como la cola. Como en el ejemplo factorial (arriba), donde la información auxiliar del índice (en cuál paso uno estaba, n ) fue empujada hacia adelante, además de la salida real de n !, En este caso la información auxiliar de los subárboles restantes es empujado hacia adelante, además de la salida real. Simbólicamente:

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

lo que significa que en cada paso, se genera la lista de valores de los nodos raíz y luego se procede a los subárboles secundarios. Generar solo los valores de los nodos a partir de esta secuencia simplemente requiere descartar los datos auxiliares del árbol secundario y luego aplanar la lista de listas (los valores se agrupan inicialmente por nivel (profundidad); aplanar (desagrupar) produce una lista lineal plana). En Haskell,

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

Estos se pueden comparar de la siguiente manera. El recorrido recursivo maneja un nodo de hoja (en la parte inferior ) como el caso base (cuando no hay hijos, simplemente genere el valor) y analiza un árbol en subárboles, atravesando cada uno a su vez, lo que finalmente resulta en solo nodos de hoja: hoja real nodos y nodos de rama cuyos hijos ya se han tratado (corte a continuación ). Por el contrario, el recorrido corecursivo maneja un nodo raíz (en la parte superior ) como el caso base (dado un nodo, primero genera el valor), trata un árbol como sintetizado de un nodo raíz y sus hijos, luego produce como salida auxiliar un lista de subárboles en cada paso, que luego son la entrada para el siguiente paso: los nodos secundarios de la raíz original son los nodos raíz en el siguiente paso, ya que sus padres ya han sido tratados (cortados arriba ). En el recorrido recursivo hay una distinción entre los nodos hoja y los nodos de rama, mientras que en el recorrido corecursivo no hay distinción, ya que cada nodo se trata como el nodo raíz del subárbol que define.

En particular, dado un árbol infinito, el recorrido corecursivo primero en amplitud atravesará todos los nodos, al igual que para un árbol finito, mientras que el recorrido recursivo en profundidad primero bajará una rama y no atravesará todos los nodos, y de hecho si atraviesa post-orden , como en este ejemplo (o en orden), no visitará ningún nodo, porque nunca llega a una hoja. Esto muestra la utilidad de la recursividad en lugar de la recursividad para tratar con estructuras de datos infinitas.

En Python, esto se puede implementar de la siguiente manera. El recorrido habitual en profundidad posterior al pedido se puede definir como:

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

Esto puede ser llamado por df(t) para imprimir los valores de los nodos del árbol en orden de profundidad de orden posterior.

El generador corecursivo de amplitud primero se puede definir como:

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

Luego se puede llamar a esto para imprimir los valores de los nodos del árbol en orden de amplitud:

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

Definición

Los tipos de datos iniciales se pueden definir como el punto fijo mínimo ( hasta el isomorfismo ) de algún tipo de ecuación; el isomorfismo viene dado por un álgebra inicial . Doblemente, los tipos de datos finales (o terminales) pueden definirse como el punto fijo más grande de una ecuación de tipo; el isomorfismo viene dado por una coalgebra final .

Si el dominio del discurso es la categoría de conjuntos y funciones totales, entonces los tipos de datos finales pueden contener valores infinitos, no bien fundamentados, mientras que los tipos iniciales no. Por otro lado, si el dominio del discurso es la categoría de órdenes parciales completos y funciones continuas , que corresponde aproximadamente al lenguaje de programación Haskell , entonces los tipos finales coinciden con los tipos iniciales, y la coalgebra final y el álgebra inicial correspondientes forman un isomorfismo.

Corecursion es entonces una técnica para definir de forma recursiva funciones cuyo rango (codominio) es un tipo de datos final, dual de la forma en que la recursividad ordinaria define de forma recursiva funciones cuyo dominio es un tipo de datos inicial.

La discusión a continuación proporciona varios ejemplos en Haskell que distinguen la correcursión. En términos generales, si uno trasladara estas definiciones a la categoría de conjuntos, seguirían siendo corecursivas. Este uso informal es consistente con los libros de texto existentes sobre Haskell. Los ejemplos utilizados en este artículo son anteriores a los intentos de definir la correcursión y explicar qué es.

Discusión

La regla para la recursividad primitiva en codatos es dual a la de la recursividad primitiva sobre datos. En lugar de descender sobre el argumento haciendo coincidir patrones en sus constructores (que fueron llamados antes , en algún lugar, por lo que recibimos un dato ya hecho y llegamos a sus subpartes constituyentes, es decir, "campos"), ascendemos en el resultado. completando sus "destructores" (u "observadores", que se llamarán después , en algún lugar, por lo que en realidad estamos llamando a un constructor, creando otra parte del resultado que se observará más adelante). Así, corecursion crea datos codatos (potencialmente infinitos), mientras que la recursividad ordinaria analiza datos (necesariamente finitos). Es posible que la recursividad ordinaria no sea aplicable a los codatos porque es posible que no finalice. Por el contrario, corecursion no es estrictamente necesario si el tipo de resultado son datos, porque los datos deben ser finitos.

En "Programación con arroyos en Coq: un caso de estudio: el tamiz de Eratóstenes" encontramos

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))

donde los primos "se obtienen aplicando la operación de primos al tren (Enu 2)". Siguiendo la notación anterior, la secuencia de números primos (con un 0 desechable como prefijo) y los flujos de números que se tamizan progresivamente, se pueden representar como

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

o en Haskell,

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

Los autores discuten cómo sieve no se garantiza que la definición de siempre sea productiva y podría atascarse, por ejemplo, si se llama con [5,10..] como flujo inicial.

Aquí hay otro ejemplo en Haskell. La siguiente definición produce la lista de números de Fibonacci en tiempo lineal:

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

Esta lista infinita depende de la evaluación perezosa; los elementos se calculan según sea necesario, y solo los prefijos finitos se representan explícitamente en la memoria. Esta característica permite que terminen los algoritmos de partes de los codatos; estas técnicas son una parte importante de la programación de Haskell.

Esto también se puede hacer en Python:

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)

La definición de zipWith se puede insertar, lo que lleva a esto:

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

Este ejemplo emplea una estructura de datos autorreferencial . La recursividad ordinaria hace uso de funciones autorreferenciales , pero no admite datos autorreferenciales. Sin embargo, esto no es esencial para el ejemplo de Fibonacci. Se puede reescribir de la siguiente manera:

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

Esto emplea solo una función autorreferencial para construir el resultado. Si se usara con un constructor de lista estricto, sería un ejemplo de recursividad descontrolada, pero con un constructor de lista no estricto, esta recursión protegida produce gradualmente una lista definida indefinidamente.

Corecursion no necesita producir un objeto infinito; una cola corecursiva es un ejemplo particularmente bueno de este fenómeno. La siguiente definición produce un recorrido en amplitud de un árbol binario en tiempo lineal:

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

Esta definición toma un árbol inicial y produce una lista de subárboles. Esta lista tiene un doble propósito como cola y como resultado ( gen len p produce sus len muescas de salida después de su puntero de retroceso de entrada p , a lo largo de queue ). Es finito si y solo si el árbol inicial es finito. Se debe realizar un seguimiento explícito de la longitud de la cola para garantizar la terminación; esto puede eludirse con seguridad si esta definición se aplica solo a árboles infinitos.

Otro ejemplo particularmente bueno da una solución al problema del etiquetado en amplitud. La función label visita todos los nodos de un árbol binario primero en amplitud y reemplaza cada etiqueta con un número entero, cada número entero posterior es más grande que el anterior en uno. Esta solución emplea una estructura de datos autorreferencial y el árbol binario puede ser finito o infinito.

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′

Un apomorfismo (como un anamorfismo , como desplegar ) es una forma de correcursión de la misma manera que un paramorfismo (como un catamorfismo , como un pliegue ) es una forma de recursividad.

El asistente de prueba de Coq admite correcursión y coinducción mediante el comando CoFixpoint.

Historia

Corecursion, a la que se hace referencia como programación circular, data al menos de ( Bird 1984 ), quien acredita a John Hughes y Philip Wadler ; se desarrollaron formas más generales en ( Allison 1989 ) . Las motivaciones originales incluían producir algoritmos más eficientes (permitiendo 1 paso de datos en algunos casos, en lugar de requerir múltiples pasos) e implementar estructuras de datos clásicas, como listas y colas doblemente enlazadas, en lenguajes funcionales. error de harv: sin destino: CITEREFAllison1989 ( ayuda )

Ver también

• Bisimulación
• Coinducción
• Recursividad
• Anamorfismo

Notas

Referencias