stringtranslate.com

Corecursión

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

Mientras que la recursividad permite a los programas operar con datos arbitrariamente complejos, siempre que puedan reducirse a datos simples (casos base), la corecursión permite a los programas producir estructuras de datos arbitrariamente complejas y potencialmente infinitas, como flujos , siempre que puedan producirse. a partir de datos simples (casos base) en una secuencia de pasos finitos . Cuando la recursión puede no terminar y nunca alcanzar 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 interpretarse alternativamente, y posiblemente de manera más natural, como funciones correcursivas que terminan en una etapa determinada, por ejemplo, relaciones de recurrencia como el factorial.

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

Ejemplos

La corecursión puede entenderse en contraste con la recursividad, que es más familiar. Si bien la corecursión es de interés principalmente en la programación funcional, se puede ilustrar mediante 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 de forma imperativa (destructiva), aunque estos no son necesarios en la corecursión en programación funcional pura. En la programación funcional pura, en lugar de asignar variables locales, estos valores calculados forman una secuencia invariable, y se accede a los valores anteriores mediante autorreferencia (los valores posteriores en la secuencia hacen referencia a los 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! := norte × (norte - 1)! .

Para calcular recursivamente su resultado en una entrada determinada, una función recursiva se llama (una copia de) 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 . De este modo se desarrolla una pila de llamadas en el proceso. Por ejemplo, para calcular fac(3) , esto llama recursivamente a fac(2) , fac(1) , fac(0) ("liquidando" 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 hasta el 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 valor único.

Este desenrollamiento de la pila se puede explicar definiendo el factorial corecursivamente , como un iterador , donde se 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 La "flecha del tiempo" se invierte, por así decirlo, leyéndola al revés como . El algoritmo correcursivo así definido produce una secuencia de todos los factoriales. Esto se puede implementar concretamente como generador . Simbólicamente, teniendo en cuenta que calcular el siguiente valor factorial requiere realizar un seguimiento tanto de n como de f (un valor factorial anterior), esto se puede representar como:

o en Haskell , 

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

es decir, "a partir de , en cada paso, los siguientes valores se calculan como ". Esto es matemáticamente equivalente y casi idéntico a la definición recursiva, pero enfatiza que los valores factoriales se están construyendo , avanzando desde el caso inicial, en lugar de calcularse después de retroceder primero, hasta el caso base, con una disminución. La salida directa de la función correcursiva no contiene simplemente los valores factoriales, sino que también incluye para cada valor los datos auxiliares de su índice n en la secuencia, de modo que se puede seleccionar cualquier resultado específico entre todos ellos, cuando sea necesario.

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

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

def  factorial ( n :  int )  ->  int : """Función factorial recursiva.""" si n == 0 : devuelve 1 más : devuelve n * factorial ( n - 1 )

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

Un generador correcursivo correspondiente se puede definir como:

def  factoriales (): """Generador correcursivo.""" n , f = 0 , 1 while True : rendimiento f n , f = n + 1 , f * ( n + 1 )

Esto genera un flujo infinito de factoriales en orden; una porción finita del mismo puede producirse mediante:

def  n_factoriales ( n :  int ):  k ,  f  =  0 ,  1  mientras que  k  <=  n :  rendimiento  f  k ,  f  =  k  +  1 ,  f  *  ( k  +  1 )

¡Esto podría entonces invocarse para producir factoriales hasta 5! a través de:

para  f  en  n_factoriales ( 5 ):  imprimir ( 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 sola función,

def  nth_factorial ( n :  int ):  k ,  f  =  0 ,  1  mientras  k  <  n :  k ,  f  =  k  +  1 ,  f  *  ( k  +  1 )  devuelve  f

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

secuencia Fibonacci

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

Debido a que la secuencia de Fibonacci es una relación de recurrencia de orden 2, la relación correcursiva debe rastrear dos términos sucesivos, siendo el correspondiente un avance de un paso y el correspondiente calcular el siguiente término. Luego, esto se puede implementar de la siguiente manera (usando asignación paralela ):

def  secuencia_fibonacci ():  a ,  b  =  0 ,  1  mientras que  Verdadero :  produce  a  a ,  b  =  b ,  a  +  b

En Haskel,

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

recorrido del árbol

El recorrido del árbol mediante un enfoque de profundidad es un ejemplo clásico de recursividad. De manera dual, el recorrido en amplitud se puede implementar de forma muy natural mediante corecursión.

De manera iterativa, uno puede atravesar un árbol colocando su nodo raíz en una estructura de datos, luego iterando con esa estructura de datos mientras no está vacía, en cada paso eliminando el primer nodo y colocando los nodos secundarios del nodo eliminado nuevamente en esos datos. estructura. Si la estructura de datos es una pila (LIFO), esto produce un recorrido en profundidad, y si la estructura de datos es una cola (FIFO), esto produce un recorrido en amplitud:

Usando la recursividad, un recorrido en profundidad de un árbol se implementa simplemente atravesando recursivamente cada uno de los nodos secundarios del nodo raíz por turno. Por tanto, el segundo subárbol hijo no se procesa hasta que finaliza el primer subárbol hijo. El valor del nodo raíz se maneja por separado, ya sea antes de atravesar el primer nodo secundario (lo que resulta en un recorrido de preorden), después de que finalice el primero y antes del segundo (en orden), o después de que finalice el segundo nodo secundario (posteriormente). orden) - asumiendo que el árbol es binario, para simplificar la exposición. La pila de llamadas (de las invocaciones de funciones transversales recursivas) corresponde a la pila que se repetiría con la manipulación explícita de la estructura LIFO mencionada anteriormente. Simbólicamente,

"Recursión" tiene dos significados aquí. Primero, las invocaciones recursivas de las funciones transversales del árbol . Más pertinentemente, debemos abordar cómo se construye aquí la lista de valores resultante. La creación recursiva de salida de abajo hacia arriba dará como resultado el recorrido del árbol de derecha a izquierda. Para que realmente se realice en el orden previsto de izquierda a derecha, la secuenciación debería imponerse mediante algún medio externo, o se lograría automáticamente si la salida se construyera de arriba hacia abajo, es decir, de forma corecursiva .

También se puede implementar un recorrido en amplitud que crea su salida en orden de arriba hacia abajo, de forma corecursiva, comenzando en el nodo raíz, generando su valor, [b] y luego atravesando en amplitud los subárboles, 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, genera los valores de todos sus nodos raíz, luego pasa sus subárboles secundarios, etc. [c] En este caso, el generador La función, de hecho la secuencia de salida misma, actúa como cola. Como en el ejemplo factorial anterior, donde la información auxiliar del índice (en qué paso se encontraba, n ) se impulsó, además de la salida real de n !, en este caso la información auxiliar de los subárboles restantes se impulsó. , además de la producción real. Simbólicamente,

lo que significa que en cada paso, se genera la lista de valores en los nodos de este nivel y luego se pasa a los nodos del siguiente nivel. Generar solo los valores de los nodos 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). Esto es extensivamente equivalente a la especificación anterior. En Haskel, 

 concatMap fst ( ( \ ( v , ts ) -> ( rootValues ​​ts , childTrees ts )) ` iterar ` ( [] , [ fulTree ]) )

En particular, dado un árbol infinito, [d] el recorrido corecursivo primero en amplitud atravesará todos los nodos, al igual que para un árbol finito, mientras que el recorrido recursivo primero en profundidad descenderá una rama y no atravesará todos los nodos, y de hecho si atraviesa En orden posterior, como en este ejemplo (o en orden), no visitará ningún nodo porque nunca llega a una hoja. Esto muestra la utilidad de la corecursión en lugar de la recursividad para tratar con estructuras de datos infinitas. Aún queda una advertencia para los árboles con un factor de ramificación infinito, que necesitan un entrelazado más atento para explorar mejor el espacio. Ver encajar .

En Python, esto se puede implementar de la siguiente manera. [e] El recorrido habitual en profundidad posterior al orden se puede definir como: [f]

def  df ( nodo ): """Recorrido primero en profundidad posterior al orden.""" si el nodo no es Ninguno : df ( nodo . izquierda ) df ( nodo . derecha ) print ( nodo . valor )

Luego se puede llamar a esto df(t)para imprimir los valores de los nodos del árbol en orden de profundidad posterior al orden.

El generador correcursivo de amplitud primero se puede definir como: [g]

def  bf ( árbol ): """Generador corecursivo de amplitud primero.""" lista_árbol = [ árbol ] while lista_árbol : lista_árbol_nueva = [] para árbol en lista_árbol : si el árbol no es Ninguno : produce árbol . valor new_tree_list . agregar ( árbol . izquierda ) nueva_lista_árbol . agregar ( árbol . derecha ) lista_árbol = nueva_lista_árbol

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

para  i  en  bf ( t ):  imprimir ( i )

Definición

Los tipos de datos iniciales se pueden definir como el punto mínimo de fijación ( hasta el isomorfismo ) de algún tipo de ecuación; el isomorfismo viene dado entonces por un álgebra inicial . De manera dual, los tipos de datos finales (o terminales) se pueden definir como el mayor punto fijo de una ecuación de tipo; el isomorfismo viene dado entonces 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 y no bien fundamentados , mientras que los tipos iniciales no. [1] [2] Por otro lado, si el dominio del discurso es la categoría de órdenes parciales completas 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 correspondiente y El álgebra inicial forma un isomorfismo. [3]

La corecursión es entonces una técnica para definir recursivamente funciones cuyo rango (codominio) es un tipo de datos final, de forma dual a la forma en que la recursividad ordinaria define recursivamente funciones cuyo dominio es un tipo de datos inicial. [4]

La discusión a continuación proporciona varios ejemplos en Haskell que distinguen la corecursión. En términos generales, si se trasladaran estas definiciones a la categoría de conjuntos, seguirían siendo correcursivas. Este uso informal es consistente con los libros de texto existentes sobre Haskell. [5] 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 correcursión primitiva en codata es dual a la de la recursividad primitiva en datos. En lugar de descender sobre el argumento haciendo coincidir patrones en sus constructores (que fueron llamados antes , en algún lugar, de modo que recibimos un dato ya preparado y llegamos a sus subpartes constituyentes, es decir, "campos"), ascendemos sobre el resultado. completando sus "destructores" (u "observadores", que serán llamados 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í, la correcursión crea codatos (potencialmente infinitos), mientras que la recursión ordinaria analiza datos (necesariamente finitos). Es posible que la recursividad ordinaria no sea aplicable a los codata porque es posible que no terminen. Por el contrario, la corecursión no es estrictamente necesaria si el tipo de resultado son datos, porque los datos deben ser finitos.

En “Programación con flujos en Coq: un caso de estudio: la Criba de Eratóstenes” [6] encontramos

hd ( conc a s ) = a tl ( conc a s ) = s           ( tamiz p s ) = si div p ( hd s ) entonces tamiz p ( tl s ) else conc ( hd s ) ( tamiz p ( tl s ))                     hd ( primos s ) = ( hd s ) tl ( primos s ) = primos ( tamiz ( hd s ) ( tl s ))

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

o en Haskell, 

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

Los autores analizan cómo no se garantiza que la definición de sievesea siempre productiva y podría atascarse, por ejemplo, si se la llama [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 : zipCon ( + ) fibs ( fibs de cola )

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

Esto también se puede hacer en Python: [7]

desde  itertools  importar  tee ,  cadena ,  islice ,  imapdef  agregar ( x ,  y ):  devolver  x  +  ydef  fibonacci ():  def  salida_diferida ():  para  i  en  la salida :  rendimiento  i  resultado ,  c1 ,  c2  =  tee ( salida_diferida (),  3 )  emparejado  =  imap ( agregar ,  c1 ,  islice ( c2 ,  1 ,  Ninguno ))  salida  =  cadena ([ 0 ,  1 ],  emparejado )  devuelve  resultadopara  i  en  islice ( fibonacci (),  20 ):  imprimir ( i )

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

mentiras = 0 : 1 : siguientes mentiras donde siguiente ( a : t @ ( b : _ )) = ( a + b ) : siguiente 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 en 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 únicamente una función autorreferencial para construir el resultado. Si se usara con un constructor de listas estricto, sería un ejemplo de recursividad descontrolada, pero con un constructor de listas no estricto, esta recursividad protegida produce gradualmente una lista definida indefinidamente.

La corecursión no necesita producir un objeto infinito; una cola correcursiva [8] es un ejemplo particularmente bueno de este fenómeno. La siguiente definición produce un recorrido en amplitud de un árbol binario de arriba hacia abajo , en tiempo lineal (que ya incorpora el aplanamiento mencionado anteriormente):

datos Árbol a b = Hoja a | Rama b ( Árbol a b ) ( Árbol a b )               bftrav :: Árbol a b -> [ Árbol a b ] bftrav árbol = árbol : ts donde ts = gen 1 ( árbol : ts )                      gen 0 p = [] gen len ( Hoja _ : p ) = gen ( len - 1 ) p gen len ( Rama _ l r : p ) = l : r : gen ( len + 1 ) p -- ---- leer---- ----escritura anticipada---                                -- árbol de valores bf = [v | (Rama v _ _) <- árbol bftrav]

Esta definición toma un árbol y produce una lista de sus subárboles (nodos y hojas). Esta lista tiene un doble propósito como cola de entrada y resultado ( gen len pproduce sus lenmuescas de salida delante de su puntero posterior de entrada, pa lo largo de la lista). Es finito si y sólo 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 sólo a infinitos árboles.

Este código de Haskell utiliza una estructura de datos autorreferencial, pero no depende esencialmente de una evaluación diferida. Se puede traducir fácilmente, por ejemplo, a Prolog, que no es un lenguaje perezoso. Lo esencial es la capacidad de crear una lista (utilizada como cola) de arriba hacia abajo . Para eso, Prolog tiene desventajas del módulo de recursión de cola (es decir, listas abiertas). Que también es emulable en Scheme, C, etc. usando listas enlazadas con puntero centinela de cola mutable:

bftrav (  Árbol ,  [ Árbol | TS ])  : -  bfgen (  1 ,  [ Árbol | TS ],  TS ).bfgen (  0 ,  _ ,  [])  :-  !.  % 0 entradas en la cola - detener y cerrar la lista bfgen (  N ,  [ hoja ( _ )  | P ],  TS  )  : -  N2  es  N - 1 ,  bfgen (  N2 ,  P ,  TS ). bfgen (  N ,  [ rama ( _ , L , R )| P ],  [ L , R | TS ])  : -  N2  es  N + 1 ,  bfgen (  N2 ,  P ,  TS ). %% ----leer----- --escritura anticipada--

Otro ejemplo particular ofrece una solución al problema del etiquetado basado en la amplitud. [9] La función labelvisita cada nodo en un árbol binario en amplitud primero, reemplazando cada etiqueta con un número entero, cada entero subsiguiente mayor que el último en 1. Esta solución emplea una estructura de datos autorreferencial, y el árbol binario puede ser finito o infinito.

etiqueta :: Árbol a b -> Árbol Int Int etiqueta t = tn donde ( tn , ns ) = go t ( 1 : ns )                    ir :: Árbol a b -> [ Int ] -> ( Árbol Int Int , [ Int ]) ir ( Hoja _ ) ( i : a ) = ( Hoja i , i + 1 : a ) ir ( Rama _ l r ) ( i : a ) = ( Rama i ln rn , i + 1 : c ) donde ( ln , b ) = go l a ( rn , c ) = go r b

O en Prolog, para comparar,

etiqueta (  Árbol ,  Tn )  : -  etiqueta (  Árbol ,  [ 1 | Ns ],  Tn ,  Ns ).etiqueta (  hoja ( _ ),  [ I | A ],  hoja (  I ),  [ I + 1 | A ]). etiqueta (  rama ( _ , L , R ), [ I | A ],  rama ( I , Ln , Rn ), [ I + 1 | C ])  : -  etiqueta (  L ,  A ,  Ln ,  B ),  etiqueta (  R ,  B ,  Rn ,  C ).

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

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

Historia

La corecursión, denominada programación circular, data al menos de (Bird 1984), quien atribuye el crédito 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 un paso sobre datos en algunos casos, en lugar de requerir múltiples pases) e implementar estructuras de datos clásicas, como listas y colas doblemente enlazadas, en lenguajes funcionales.

Ver también

Notas

  1. ^ No validar los datos de entrada.
  2. ^ El recorrido primero en amplitud, a diferencia del primero en profundidad, no es ambiguo y visita un valor de nodo antes de procesar los elementos secundarios.
  3. ^ Técnicamente, se puede definir un recorrido en amplitud en un conjunto de árboles ordenados y desconectados: primero el nodo raíz de cada árbol, luego los hijos de cada árbol por turno, luego los nietos por turno, etc.
  4. ^ Suponga un factor de ramificación fijo (p. ej., binario), o al menos acotado y equilibrado (infinito en todas las direcciones).
  5. ^ Primero defina una clase de árbol, digamos a través de:
     Árbol de clase :  def  __init__ ( self ,  valor ,  izquierda = Ninguno ,  derecha = Ninguno ):  self . valor  =  valorarse a  uno mismo . izquierda  =  yo izquierdo  . derecha = derecha   def  __str__ ( self ):  devuelve  str ( self . valor )

    e inicializando un árbol, digamos a través de:

    t  =  Árbol ( 1 ,  Árbol ( 2 ,  Árbol ( 4 ),  Árbol ( 5 )),  Árbol ( 3 ,  Árbol ( 6 ),  Árbol ( 7 )))

    En este ejemplo, los nodos están etiquetados en orden de amplitud:

     1 2 34 5 6 7
  6. ^ Intuitivamente, la función itera sobre subárboles (posiblemente vacíos), luego, una vez que finalizan, todo lo que queda es el nodo en sí, cuyo valor luego se devuelve; esto corresponde a tratar un nodo hoja como básico.
  7. ^ Aquí el argumento (y la variable de bucle) se considera como un posible árbol infinito completo, representado por (identificado con) su nodo raíz (árbol = nodo raíz), en lugar de como un nodo hoja potencial, de ahí la elección del nombre de la variable.

Referencias

  1. ^ Barwise y Moss 1996.
  2. ^ Moss y Danner 1997.
  3. ^ Smyth y Plotkin 1982.
  4. ^ Gibbons y Hutton 2005.
  5. ^ Doets y van Eijck 2004.
  6. ^ Leclerc y Paulin-Mohring, 1994
  7. ^ Hettinger 2009.
  8. ^ Allison 1989; Smith 2009.
  9. ^ Jones y Gibbons 1992.