Explication de «nouer le nœud»

En lisant des choses liées à Haskell, je rencontre parfois l’expression «attacher le nœud», je pense que je comprends ce que ça fait, mais pas comment .

Alors, y a-t-il des explications bonnes, élémentaires et simples pour comprendre ce concept?

    Lier le nœud est une solution au problème des structures de données circulaires. Dans les langages impératifs, vous construisez une structure circulaire en créant d’abord une structure non circulaire, puis en remontant et en fixant les pointeurs pour append la circularité.

    Disons que vous vouliez une liste circulaire à deux éléments avec les éléments “0” et “1”. Cela semblerait impossible à construire car si vous créez le nœud “1” puis créez le nœud “0” pour le pointer, vous ne pouvez pas revenir en arrière et réparer le nœud “1” pour pointer vers le nœud “0” . Donc, vous avez une situation de poule et d’œuf dans laquelle les deux nœuds doivent exister avant de pouvoir être créés.

    Voici comment vous le faites dans Haskell. Considérez la valeur suivante:

    alternates = x where x = 0 : y y = 1 : x 

    Dans un langage non paresseux, ce sera une boucle infinie à cause de la récursion non terminée. Mais dans Haskell, l’évaluation paresseuse fait la bonne chose: elle génère une liste circulaire à deux éléments.

    Pour voir comment cela fonctionne dans la pratique, pensez à ce qui se passe au moment de l’exécution. L’implémentation habituelle de “thunk” d’évaluation paresseuse représente une expression non évaluée en tant que structure de données contenant un pointeur de fonction plus les arguments à transmettre à la fonction. Lorsque cela est évalué, le thunk est remplacé par la valeur réelle, de sorte que les futures références ne doivent plus appeler la fonction.

    Lorsque vous prenez le premier élément de la liste, «x» est évalué à une valeur (0, & y), où le bit «& y» est un pointeur sur la valeur de «y». Puisque «y» n’a pas été évalué, il s’agit actuellement d’un thunk. Lorsque vous prenez le deuxième élément de la liste, l’ordinateur suit le lien de x vers ce thunk et l’évalue. Il évalue à (1, & x), ou en d’autres termes, un pointeur à la valeur d’origine ‘x’. Vous avez donc maintenant une liste circulaire en mémoire. Le programmeur n’a pas besoin de réparer les pointeurs car le mécanisme d’évaluation paresseux le fait pour vous.

    Ce n’est pas tout à fait ce que vous avez demandé et ce n’est pas directement lié à Haskell, mais l’article de Bruce McAdam intitulé About About Wraps It Up aborde ce sujet en profondeur. L’idée de base de Bruce est d’utiliser un opérateur explicite de nœuds appelé WRAP au lieu du nouage implicite qui est fait automatiquement dans Haskell, OCaml et dans d’autres langages. Le papier a beaucoup d’ exemples amusants , et si vous êtes intéressé par le nouage, je pense que vous vous sentirez mieux avec le processus.