De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
No confundir con recursividad mutua .

En ciencias de la computación , la correcursión es un tipo de operación que es dual a la recursividad . Mientras que la recursividad funciona analíticamente, partiendo de datos más alejados de un caso base y dividiéndolos en datos más pequeños y repitiéndolos hasta que se llega a un caso base, la recursividad funciona sintéticamente, comenzando desde un caso base y desarrollándolo, produciendo iterativamente datos más extraídos de un caso base. caso base. En pocas palabras, los algoritmos corecursivos 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 la recursividad generativa que puede carecer de una "dirección" definida inherente a la recursividad y la recursividad correlativas.

Cuando la recursividad permite que los programas operen con datos arbitrariamente complejos, siempre que puedan reducirse a datos simples (casos base), corecursion permite que los programas produzcan 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 . Donde la recursividad no puede terminar, sin llegar nunca a un estado base, la correcursión comienza desde un estado base y, por lo tanto, produce pasos subsiguientes 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 así convertirse en no productivo. 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 [ editar ]

Corecursion se puede entender en contraste con la recursividad, que es más familiar. Si bien corecursion es principalmente de interés 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 asignan valoresimperativamente (destructivamente), aunque estos no son necesarios en corecursion en 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 por referencia propia (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 [ editar ]

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 lo 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 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 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 un generador . Simbólicamente, observar que calcular el siguiente valor factorial requiere realizar un seguimiento de n y f (un valor factorial anterior), esto se puede representar como:

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.

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: [a]

def  factorial ( n ):  "" "Función factorial recursiva." ""  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 :  rendimiento  f  n ,  f  =  n  +  1 ,  f  *  ( n  +  1 )

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

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

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

para  f  en  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 )  produce  f

Como se puede ver fácilmente aquí, esto es prácticamente equivalente (simplemente sustituyendo returnel único yieldallí) 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 de Fibonacci [ editar ]

De la misma manera, 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 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 ):

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

En Haskell, 

 mapa  FST  (  ( \ ( un , b )  ->  ( b , un + b ))  ` iterate `  ( 0 , 1 )  )

Recorrido del árbol [ editar ]

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. . [b] 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 (post-orden) [c] en profundidad primero 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 procesamiento hasta que finalice el primer subárbol secundario. Una vez que se alcanza un nodo hoja o se han agotado los hijos de un nodo de rama, se visita el nodo en sí (por ejemplo, se muestra el valor del nodo en sí). 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 en amplitud comenzando en el nodo raíz, dando salida a su valor, [d] luego atravesando primero en amplitud los subárboles, es decir, pasando la lista completa de subárboles al siguiente paso (ni uno 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. [e] En este caso, la función generadora, de hecho la secuencia de salida en sí, actúa como la cola. Como en el ejemplo factorial (arriba), donde la información auxiliar del índice (en qué paso uno estaba, n ) se empujó hacia adelante, además de la salida real de n!, en este caso, la información auxiliar de los subárboles restantes se empuja hacia adelante, además de la salida real. Simbólicamente:

lo que significa que en cada paso, se genera la lista de valores de los nodos raíz, luego se procede a los subárboles secundarios. Generar solo los valores de nodo 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 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 eventualmente resulta en solo nodos de hoja: hoja real nodos y nodos de rama cuyos hijos ya han sido tratados (cortados 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 muestra el valor), trata un árbol como sintetizadode un nodo raíz y sus hijos, luego produce como salida auxiliar una 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, como sus padres ya se han tratado (cortado 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.

Notablemente, dado un árbol infinito, [f] 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-order, 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. [g] El recorrido habitual en profundidad después del pedido se puede definir como: [h]

def  df ( nodo ):  "" "Travesía en profundidad posterior al orden." ""  si el  nodo  no es  Ninguno : df ( nodo . izquierda ) df ( nodo . derecha ) imprimir ( nodo . valor )

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 primer ancho se puede definir como: [i]

def  bf ( árbol ):  "" "Generador de corecursivo primero en amplitud." ""  tree_list  =  [ árbol ]  while  tree_list :  new_tree_list  =  []  para  árbol  en  tree_list :  si el  árbol  no es  None : rendimiento del árbol . valor new_tree_list . añadir ( árbol . izquierda ) new_tree_list . añadir ( árbol . derecha ) lista_árbol       =  new_tree_list

A continuación, 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 [ editar ]

Los tipos de datos iniciales se pueden definir como el punto de referencia 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 de referencia 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. [1] [2] 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 correspondiente y el álgebra inicial forma un isomorfismo. [3]

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

La discusión a continuación proporciona varios ejemplos en Haskell que distinguen corecursion. 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. [5] Los ejemplos utilizados en este artículo son anteriores a los intentos de definir corecursion y explicar qué es.

Discusión [ editar ]

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 codatos (potencialmente infinitos), mientras que la recursividad ordinaria analizadatos (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" [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 )  =  primes  ( tamiz  ( 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

o en Haskell, 

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

Los autores discuten cómo sieveno 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: [7]

desde  itertools  import  tee ,  chain ,  islice ,  imapdef  add ( x ,  y ):  return  x  +  ydef  fibonacci ():  def  salida_deferida ():  para  i  en  salida :  rendimiento  i  resultado ,  c1 ,  c2  =  tee ( salida_deferida (),  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:

fibs  =  0  :  1  :  siguientes  fibs  donde  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 acomoda 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 [8] 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:

 Árbol de  datos a  b  =  Hoja  a  |  Rama  b  ( Árbol  a  b )  ( Árbol  a  b )bftrav  ::  Árbol  a  b  ->  [ Árbol  a  b ] bftrav  árbol  =  cola  donde  cola  =  árbol  :  cola gen  1  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 pproduce sus lenmuescas 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. [9] La función labelvisita todos los nodos de un árbol binario primero en amplitud y reemplaza cada etiqueta con un número entero, cada número entero subsiguiente 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.

etiqueta  ::  Árbol  a  b  ->  Árbol  Int  Int  etiqueta  t  =  t ′  donde  ( 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 )  =  ( Rama  n  l ′  r′  ,  N + 1  :  ns ′ ′ )  donde  ( l ′ ,  ns ′  )  =  go  l  ns  ( r ′ ,  ns ′ ′ )  =  go  r  ns ′

Un apomorfismo (como un anamorfismo , como un desdoblamiento ) es una forma de correcursión de la misma forma 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 [ editar ]

Corecursion, conocida 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.

Ver también [ editar ]

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

Notas [ editar ]

  1. ^ No valida los datos de entrada.
  2. ^ De manera más elegante, se puede comenzar colocando el nodo raíz en la estructura de datos y luego iniciar el proceso.
  3. ^ El pedido posterior es hacer explícito el "nodo hoja es el caso base" para la exposición, pero el mismo análisis funciona para pedidos anticipados o en pedidos.
  4. ^ El recorrido primero en amplitud, a diferencia de lo primero en profundidad, no es ambiguo y visita un valor de nodo antes de procesar los elementos secundarios.
  5. ^ Técnicamente, se puede definir un recorrido en amplitud en un conjunto ordenado y desconectado de árboles: primero el nodo raíz de cada árbol, luego los hijos de cada árbol por turno, luego los nietos por turno, etc.
  6. ^ Suponga un factor de ramificación fijo(p. Ej., Binario), o al menos acotado y equilibrado (infinito en todas las direcciones).
  7. ^ Primero, definiendo una clase de árbol, digamos a través de:
     árbol de clases :  def  __init__ ( self ,  value ,  left = None ,  right = None ):  self . valor  =  valor  propio . izquierda  =  yo izquierdo  . derecha = derecha   def  __str__ ( auto ):  retorno  str ( auto . 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
  8. ^ Intuitivamente, la función itera sobre subárboles (posiblemente vacíos), luego, una vez que estos están terminados, todo lo que queda es el nodo en sí, cuyo valor luego se devuelve; esto corresponde a tratar un nodo hoja como básico.
  9. ^ 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 [ editar ]

  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.
  • Bird, Richard Simpson (1984). "Utilización de programas circulares para eliminar múltiples recorridos de datos". Acta Informatica . 21 (3): 239–250. doi : 10.1007 / BF00264249 .
  • Lloyd Allison (abril de 1989). "Programas circulares y estructuras autorreferenciales" . Práctica y experiencia en software . 19 (2): 99–109. doi : 10.1002 / spe.4380190202 .
  • Geraint Jones y Jeremy Gibbons (1992). Algoritmos de árbol de amplitud primero en tiempo lineal: un ejercicio de aritmética de pliegues y cremalleras (Informe técnico). Departamento de Ciencias de la Computación, Universidad de Auckland.
  • Jon Barwise ; Lawrence S Moss (junio de 1996). Círculos viciosos . Centro de Estudios del Lenguaje y la Información. ISBN 978-1-57586-009-1. Archivado desde el original el 21 de junio de 2010 . Consultado el 24 de enero de 2011 .
  • Lawrence S Moss; Norman Danner (1997). "Sobre las bases de Corecursion". Revista Lógica de la IGPL . 5 (2): 231-257. CiteSeerX  10.1.1.40.4243 . doi : 10.1093 / jigpal / 5.2.231 .
  • Kees Doets; Jan van Eijck (mayo de 2004). El camino de Haskell hacia la lógica, las matemáticas y la programación . Publicaciones de King's College. ISBN 978-0-9543006-9-2.
  • David Turner (28 de julio de 2004). "Programación funcional total" . Revista de Ciencias de la Computación Universal . 10 (7): 751–768. doi : 10.3217 / jucs-010-07-0751 .
  • Jeremy Gibbons; Graham Hutton (abril de 2005). "Métodos de prueba para programas corecursivos" . Fundamenta Informaticae . 66 (4): 353–366.
  • Leon P Smith (2009-07-29), "Colas corecursivas de Lloyd Allison: por qué importan las continuaciones" , The Monad Reader (14): 37–68
  • Raymond Hettinger (19 de noviembre de 2009). "Receta 576961: técnica de iteración cíclica" .
  • MB Smyth y GD Plotkin (1982). "La solución teórica de categorías de ecuaciones de dominio recursivo" (PDF) . Revista SIAM de Computación . 11 (4): 761–783. doi : 10.1137 / 0211062 .
  • Leclerc, Francois; Paulin-Mohring, Christine (1993). Programación con arroyos en Coq: un estudio de caso: el tamiz de Eratóstenes . Tipos de Pruebas y Programas: Taller Internacional TIPOS '93. Springer-Verlag New York, Inc. págs. 191–212. ISBN 978-3-540-58085-0.