Dans la lecture de Haskell liées trucs que j'ai parfois l'expression "d'attacher le noeud", je crois que je comprends ce qu' il fait, mais pas comment.
Donc, il y a de bon, de base, et simple à comprendre les explications de ce concept?
Réponses
Trop de publicités?
D'attacher le noeud est une solution au problème de la circulaire de structures de données. Dans les langages impératifs, de vous construire une structure circulaire en créant d'abord un non-circulaire de la structure, puis de revenir en arrière et réparer les pointeurs pour ajouter de la circularité.
Que vous vouliez un deux-élément circulaire liste avec les éléments "0" et "1". Il semble impossible d'en construire parce que si vous créez le "1 nœud" et ensuite créer le "0" nœud de point à elle, vous ne pouvez pas revenir en arrière et corriger le "1" nœud de point à "0" nœud. Si vous avez un dilemme de la poule et de l'oeuf situation où les deux nœuds doivent exister avant peuvent être créés.
Voici comment vous le faites en Haskell. Considérer la valeur suivante:
alternates = x where
x = 0 : y
y = 1 : x
Dans un non-lazy langue ce sera une boucle infinie en raison de la non récurrence. Mais en Haskell évaluation différée fait la bonne Chose: elle génère un deux-élément circulaire de la liste.
Pour voir comment cela fonctionne dans la pratique, pensez à ce qui se passe au moment de l'exécution. L'habituel "thunk" la mise en œuvre de l'évaluation différée représente non évalué l'expression comme une structure de données contenant un pointeur de fonction, plus les arguments passés à la fonction. Lorsque celui-ci est évalué le thunk est remplacé par la valeur réelle de sorte qu'à l'avenir les références n'avez pas à appeler de nouveau la fonction.
Lorsque vous prenez le premier élément de la liste " x " est évaluée jusqu'à une valeur (0, &y), où la "&y" bit est un pointeur vers la valeur de "y". Depuis le " y " n'a pas été évalués c'est actuellement un thunk. Lorsque vous prenez le deuxième élément de la liste de l'ordinateur suit le lien de x à ce thunk et l'évalue. Il prend la valeur (1, &x), ou en d'autres termes un pointeur vers l'original 'x' valeur. Si vous avez maintenant une liste circulaire assis dans la mémoire. Le programmeur n'a pas besoin de le fixer à l'arrière-pointeurs, car le paresseux mécanisme d'évaluation fait pour vous.
Norman Ramsey
Points
115730
Ce n'est pas tout à fait ce que vous avez demandé, et il n'est pas directement liée à Haskell, mais Bruce McAdam du papier Que Sur l'enveloppe en Haut va dans cette rubrique en substantielle de l'étendue et de la profondeur. Bruce idée de base est d'utiliser un explicite de nouage de l'opérateur appelé ENVELOPPEMENT au lieu de l' implicite de nouage qui est fait automatiquement, en Haskell, OCaml, et quelques autres langues. Le papier a beaucoup de divertissant exemples, et si vous êtes intéressé par nouage je pense que vous repartirez avec une bien meilleure idée pour le processus.
