Quelle est la différence entre récursivité et corecursion?

Quelle est la différence entre ceux-ci?

• Récursion
• Corecursion

Sur Wikipedia, il y a peu d'informations et pas de code clair expliquant ces termes.

Quels sont quelques exemples très simples expliquant ces termes?

Comment la corecursion est-elle le double de la récursion?

Existe-t-il des algorithmes corecusifs classiques?

Il y a un bon nombre de bonnes manières de regarder ceci. La chose la plus facile pour moi est de penser à la relation entre "définitions inductives" et "définitions coinductives"

Une définition inductive d'un ensemble va comme ceci.

L'ensemble "Nat" est défini comme le plus petit ensemble tel que "zéro" soit dans Nat, et si n est dans Nat, "Succ n" est dans Nat.

Ce qui correspond au Ocaml suivant

type nat = Zero | Succ of nat

Une chose à noter à propos de cette définition est qu'un nombre

omega = Succ(omega)

n'est pas un membre de cet ensemble. Pourquoi? Supposons que c’est le cas, considérons maintenant l’ensemble N qui a tous les mêmes éléments que Nat, sauf qu’il n’a pas d’oméga. Clairement, zéro est dans N, et si y est dans N, Succ (y) est dans N, mais N est plus petit que Nat, ce qui est une contradiction. Donc, oméga n'est pas dans Nat.

Ou peut-être plus utile pour un informaticien:

Pour un ensemble "a", l'ensemble "Liste d'un" est défini comme le plus petit ensemble tel que "Nil" figure dans la liste d'un, et que si xs se trouve dans la liste d'un et x se trouve dans un "Cons x xs" est dans la liste de a.

Ce qui correspond à quelque chose comme

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

Le mot clé ici est "le plus petit". Si nous ne disions pas "plus petit", nous n'aurions aucun moyen de savoir si le set Nat contenait une banane!

Encore,

zeros = Cons(Zero,zeros)

n'est pas une définition valide pour une liste de noms, tout comme Omega n'était pas un Nat valide.

Définir les données de manière inductive de cette manière nous permet de définir des fonctions qui fonctionnent avec la récursion

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

nous pouvons alors prouver des faits à ce sujet, comme "plus un zéro = a" en utilisant l' induction (en particulier, l'induction structurelle)

Notre preuve procède par induction structurelle sur un.
Pour le cas de base, laissez-le être zéro. plus Zero Zero = match Zero with |Zero -> Zero | Succ(c) -> let r = plus c b in Succ(r)alors nous savons plus Zero Zero = Zero. Soit aun nat. Supposons l'hypothèse inductive que plus a Zero = a. Nous montrons maintenant que plus (Succ(a)) Zero = Succ(a)cela est évident puisque 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) Ainsi, par induction plus a Zero = apour tous adans nat

Nous pouvons bien sûr prouver des choses plus intéressantes, mais c'est l'idée générale.

Jusqu'ici, nous avons traité des données définies par induction que nous avons obtenues en les laissant le "plus petit" ensemble. Nous voulons donc maintenant travailler avec des codata définies de manière coinductive que nous obtenons en les laissant être le plus grand ensemble.

Alors

Soit un ensemble. L'ensemble "Stream of a" est défini comme le plus grand ensemble tel que, pour chaque x du flux d'un, x se compose de la paire ordonnée (tête, queue) telle que la tête se trouve dans un et que la queue se trouve dans le flux d'un

En Haskell, nous dirions ceci comme

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

En fait, en Haskell, nous utilisons normalement les listes intégrées, qui peuvent être une paire ordonnée ou une liste vide.

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

Banana n'est pas un membre de ce type non plus, puisqu'il ne s'agit ni d'une paire ordonnée ni d'une liste vide. Mais maintenant on peut dire

ones = 1:ones

et c'est une définition parfaitement valable. De plus, nous pouvons effectuer une co-récursion sur ces co-données. En fait, il est possible qu'une fonction soit à la fois co-récursive et récursive. Alors que la récursion était définie par le fait que la fonction avait un domaine composé de données, la co-récursivité signifiait simplement qu'elle avait un co-domaine (également appelé la plage) qui est la co-donnée. La récursion primitive signifiait toujours "s’appeler" sur des données plus petites jusqu’à atteindre des données plus petites. La co-récursivité primitive "s'appelle toujours" sur des données supérieures ou égales à ce que vous aviez auparavant.

ones = 1:ones

est primitivement co-récursif. Alors que la fonction map(un peu comme "foreach" dans les langages impératifs) est à la fois primitivement récursive (en quelque sorte) et primitivement co-récursive.

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

Il en va de même pour la fonction zipWithqui prend une fonction et une paire de listes et les combine en utilisant cette fonction.

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

l'exemple classique des langages fonctionnels est la séquence de Fibonacci

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

qui est primitivement récursif, mais peut être exprimé plus élégamment comme une liste infinie

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

un exemple intéressant d'induction / coinduction prouve que ces deux définitions calculent la même chose. Ceci est laissé comme un exercice pour le lecteur.

Fondamentalement, corecursion est de type accumulateur de récursivité , construisant son résultat sur la voie suivante du cas de départ, tandis que la récursion régulière construit son résultat sur le chemin du retour du cas de base.

(parle maintenant Haskell). C'est pourquoi foldr(avec une fonction de combinaison stricte) exprime la récursion, et foldl'(avec un peigne strict. F.) / scanl/ until/ iterate/ unfoldr/ Etc. etc. corecursion. Corecursion est partout. foldravec peigne non strict. F. exprime la queue récursion modulo contre .

Et la récursion gardée de Haskell est comme la contre-récursion de la queue, modulo .

C'est la récursion:

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]

(lu $comme "de"). C'est 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
      = .....

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

Vérifiez ceci sur le blog de Vitomir Kovanovic . Je l'ai trouvé au point:

Evaluation paresseuse dans une fonctionnalité très intéressante que l'on trouve dans les langages de programmation dotés de capacités de programmation fonctionnelles telles que lisp, haskell, python, etc. L'évaluation de la valeur d'une variable est différée par rapport à l'utilisation réelle de cette variable.

Cela signifie par exemple que si vous voulez créer une liste de millions d'éléments avec quelque chose comme cela, (defn x (range 1000000))elle n'est pas réellement créée, mais elle est simplement spécifiée et lorsque vous utilisez réellement cette variable pour la première fois, par exemple lorsque vous souhaitez utiliser le 10ème élément de cet interpréteur de liste crée uniquement les 10 premiers éléments de cette liste. Ainsi, la première exécution de (prendre 10 x) crée réellement ces éléments et tous les appels ultérieurs à la même fonction utilisent des éléments déjà existants.

Ceci est très utile car vous pouvez créer des listes infinies sans erreurs de mémoire insuffisante. La liste sera longue, tout ce que vous avez demandé. Bien sûr, si votre programme fonctionne avec de grandes collections de données, il peut atteindre la limite de mémoire lors de l'utilisation de ces listes infinies.

D'autre part, la corecursion est double de la récursivité. Qu'est-ce que cela signifie? Tout comme les fonctions récursives, qui sont exprimées dans leurs propres termes, les variables corécursives sont exprimées dans leurs propres termes.

Ceci est mieux exprimé sur l'exemple.

Disons que nous voulons une liste de tous les nombres premiers ...