Comment fonctionne la définition (co) récursive dans Haskell?

Question

Je joue avec la langue pour commencer à apprendre et je suis perplexe au-delà de mes esprits sur la façon dont une définition récursive fonctionne.

Par exemple, nous allons prendre la séquence des nombres (Triangular TN n = sum [1..n])

La solution proposée était:

triangularNumbers = scanl1 (+) [1..] 

Jusqu'à présent, si bon.

Mais la solution que je ne viens avec était:

triangularNumbers = zipWith (+) [1..] $ 0 : triangularNumbers 

Ce qui est correct. Maintenant, ma question est: comment cela se traduit par une implémentation de niveau inférieur? Que se passe-t-il exactement derrière la scène quand une telle définition récursive est satisfaite?

Answer 1

Voici une fonction récursive simple qui vous donne le nième nombre Triangulaire:

triag 0 = 0 
triag n = n + triag (n-1) 

Votre solution triag' = zipWith (+) [1..] $ 0 : triag' est quelque chose de plus de fantaisie: Il est corecursive (click, click). Au lieu de calculer le nième nombre en le réduisant à la valeur de plus petites entrées, vous définissez la séquence infinie entière des nombres triangulaires en spécifiant récursivement la prochaine valeur, étant donné un segment initial.

Comment Haskell gère-t-il cette corecursion? Quand il rencontre votre définition, aucun calcul n'est réellement effectué, il est différé jusqu'à ce que les résultats sont nécessaires pour d'autres calculs. Lorsque vous accédez à un élément particulier de votre liste triag', Haskell commence à calculer les éléments de la liste en fonction de la définition, jusqu'à l'élément accédé. Pour plus de détails, j'ai trouvé this article sur l'évaluation paresseux utile. En résumé, l'évaluation paresseuse est géniale, sauf si vous avez besoin de prévoir l'utilisation de la mémoire.

Here est une question SO similaire, avec une explication étape par étape de l'évaluation de fibs = 0 : 1 : zipWith (+) fibs (tail fibs), une définition corécursive de la séquence de Fibonacci.