¿Cuál es la diferencia entre recursion y corecursion?

¿Cuál es la diferencia entre estos?

• Recursividad
• Corecursion

En Wikipedia, hay poca información y ningún código claro que explique estos términos.

¿Cuáles son algunos ejemplos muy simples que explican estos términos?

¿Cómo es corecursion el dual de recursión?

¿Hay algún algoritmo corecusive clásico?

Hay varias maneras buenas de ver esto. Lo más fácil para mí es pensar en la relación entre "Definiciones inductivas" y "Coinductivas"

Una definición inductiva de un conjunto es así.

El conjunto "Nat" se define como el conjunto más pequeño, de modo que "Zero" está en Nat, y si n está en Nat, "Succ n" está en Nat.

Que corresponde al siguiente Ocaml

type nat = Zero | Succ of nat

Una cosa a tener en cuenta sobre esta definición es que un número

omega = Succ(omega)

NO es miembro de este conjunto. ¿Por qué? Suponga que sí, ahora considere el conjunto N que tiene todos los mismos elementos que Nat, excepto que no tiene omega. Claramente, Zero está en N, y si y está en N, Succ (y) está en N, pero N es más pequeño que Nat, lo cual es una contradicción. Entonces, omega no está en Nat.

O, quizás más útil para un informático:

Dado un conjunto "a", el conjunto "Lista de a" se define como el conjunto más pequeño de modo que "Nil" está en la Lista de a, y que si xs está en la Lista de a y x está en un "Cons x xs" está en la lista de a.

Que corresponde a algo como

type 'a list = Nil | Cons of 'a * 'a list

La palabra operativa aquí es "más pequeña". ¡Si no dijéramos "el más pequeño" no tendríamos ninguna forma de saber si el conjunto Nat contenía un plátano!

De nuevo,

zeros = Cons(Zero,zeros)

no es una definición válida para una lista de nats, al igual que omega no era un Nat válido.

Definir datos inductivamente de esta manera nos permite definir funciones que funcionan en ellos utilizando la recursividad

let rec plus a b = match a with
                   | Zero    -> b
                   | Succ(c) -> let r = plus c b in Succ(r)

entonces podemos probar hechos sobre esto, como "más un cero = a" usando inducción (específicamente, inducción estructural)

Nuestra prueba procede por inducción estructural en a.
Para el caso base, sea un cero. plus Zero Zero = match Zero with |Zero -> Zero | Succ(c) -> let r = plus c b in Succ(r)por lo que sabemos plus Zero Zero = Zero. Deja que asea ​​un nat. Suponga la hipótesis inductiva de que plus a Zero = a. Ahora mostramos que plus (Succ(a)) Zero = Succ(a)esto es obvio ya que plus (Succ(a)) Zero = match a with |Zero -> Zero | Succ(a) -> let r = plus a Zero in Succ(r) = let r = a in Succ(r) = Succ(a) , por inducción, plus a Zero = apara todos aen nat

Por supuesto, podemos probar cosas más interesantes, pero esta es la idea general.

Hasta ahora hemos tratado con datos inductivamente definidos que obtuvimos al dejar que sea el conjunto "más pequeño". Entonces, ahora queremos trabajar con codatos definidos de forma coductiva que obtenemos al dejar que sea el conjunto más grande.

Entonces

Deja que sea un conjunto. El conjunto "Flujo de a" se define como el conjunto más grande de tal manera que para cada x en el flujo de a, x consiste en el par ordenado (cabeza, cola) de modo que la cabeza está en ay la cola está en Flujo de un

En Haskell expresaríamos esto como

data Stream a = Stream a (Stream a) --"data" not "newtype"

En realidad, en Haskell usamos las listas integradas normalmente, que pueden ser un par ordenado o una lista vacía.

data [a] = [] | a:[a]

Banana tampoco es miembro de este tipo, ya que no es un par ordenado o la lista vacía. Pero ahora podemos decir

ones = 1:ones

y esta es una definición perfectamente válida. Además, podemos realizar la co-recursividad en estos datos conjuntos. En realidad, es posible que una función sea co-recursiva y recursiva. Si bien la recursión se definió por la función que tiene un dominio que consiste en datos, la co-recursión solo significa que tiene un co-dominio (también llamado rango) que es co-datos. La recursividad primitiva significaba siempre "llamarse a uno mismo" en datos más pequeños hasta alcanzar algunos datos más pequeños. La co-recursividad primitiva siempre "se llama a sí misma" en datos mayores o iguales a los que tenía antes.

ones = 1:ones

es primitivamente co-recursivo. Mientras que la función map(algo así como "foreach" en lenguajes imperativos) es primitivamente recursiva (más o menos) y primitivamente co-recursiva.

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = (f x):map f xs

Lo mismo ocurre con la función zipWithque toma una función y un par de listas y las combina usando esa función.

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (a:as) (b:bs) = (f a b):zipWith f as bs
zipWith _ _ _           = [] --base case

El ejemplo clásico de lenguajes funcionales es la secuencia de Fibonacci

fib 0 = 0
fib 1 = 1
fib n = (fib (n-1)) + (fib (n-2))

que es primitivamente recursivo, pero puede expresarse más elegantemente como una lista infinita

fibs = 0:1:zipWith (+) fibs (tail fibs)
fib' n = fibs !! n --the !! is haskell syntax for index at

Un ejemplo interesante de inducción / coinducción es demostrar que estas dos definiciones calculan lo mismo. Esto se deja como un ejercicio para el lector.

Básicamente, corecursion es un estilo de acumulador de recursión , construyendo su resultado en el camino hacia adelante desde el caso inicial, mientras que la recursión regular construye su resultado en el camino de regreso desde el caso base.

(Hablando Haskell ahora). Es por eso que foldr(con una estricta función de combinación) expresa la recursión y foldl'(con un estricto comb. F.) / scanl/ until/ iterate/ unfoldr/ Etc.expresa corecursion. Corecursion está en todas partes. foldrcon peine no estricto. F. expresa recidiva de cola módulo contras .

Y la recursión protegida de Haskell es como el módulo de recursión de cola .

Esto es recursividad:

fib n | n==0 = 0
      | n==1 = 1
      | n>1  = fib (n-1) + fib (n-2)

fib n = snd $ g n
  where
    g n | n==0 = (1,0)
        | n>0  = let { (b,a) = g (n-1) } in (b+a,b)

fib n = snd $ foldr (\_ (b,a) -> (b+a,b)) (1,0) [n,n-1..1]

(leído $como "de"). Esta es corecursion:

fib n = g (0,1) 0 n where
  g n (a,b) i | i==n      = a 
              | otherwise = g n (b,a+b) (i+1)

fib n = fst.snd $ until ((==n).fst) (\(i,(a,b)) -> (i+1,(b,a+b))) (0,(0,1))
      = fst $ foldl (\(a,b) _ -> (b,a+b)) (0,1) [1..n]
      = fst $ last $ scanl (\(a,b) _ -> (b,a+b)) (0,1) [1..n]
      = fst (fibs!!n)  where  fibs = scanl (\(a,b) _ -> (b,a+b)) (0,1) [1..]
      = fst (fibs!!n)  where  fibs = iterate (\(a,b) -> (b,a+b)) (0,1)
      = (fibs!!n)  where  fibs = unfoldr (\(a,b) -> Just (a, (b,a+b))) (0,1)
      = (fibs!!n)  where  fibs = 0:1:map (\(a,b)->a+b) (zip fibs $ tail fibs)
      = (fibs!!n)  where  fibs = 0:1:zipWith (+) fibs (tail fibs)
      = (fibs!!n)  where  fibs = 0:scanl (+) 1 fibs
      = .....

Pliegues: http://en.wikipedia.org/wiki/Fold_(higher-order_function)

Mira esto en el blog de Vitomir Kovanovic . Lo encontré al punto:

La evaluación diferida en una característica muy agradable que se encuentra en los lenguajes de programación con capacidades de programación funcionales como lisp, haskell, python, etc. Sirve para que la evaluación del valor de la variable se retrase al uso real de esa variable.

Significa que, por ejemplo, si desea crear una lista de millones de elementos con algo como esto, (defn x (range 1000000))en realidad no se crea, pero solo se especifica y cuando realmente usa esa variable por primera vez, por ejemplo, cuando desea el décimo elemento de ese intérprete de listas crea solo los primeros 10 elementos de esa lista. Entonces, la primera ejecución de (tomar 10 x) en realidad crea estos elementos y todas las llamadas posteriores a la misma función están trabajando con elementos ya existentes.

Esto es muy útil porque puede crear listas infinitas sin errores de memoria insuficiente. La lista será grande cuánto solicitó. Por supuesto, si su programa está trabajando con grandes colecciones de datos, puede alcanzar el límite de memoria en el uso de estas listas infinitas.

Por otro lado, corecursion es dual a recursion. ¿Lo que esto significa? Bueno, al igual que las funciones recursivas, que se expresan en términos de sí mismas, las variables corecursivas se expresan en términos de sí mismas.

Esto se expresa mejor en el ejemplo.

Digamos que queremos una lista de todos los números primos ...