Ajouter! dans le régime?

Question

J'apprends le schéma R5RS en ce moment (à partir de PocketScheme) et je trouve que je pourrais utiliser une fonction qui est intégrée dans certaines variantes de Scheme mais pas toutes: Append! En d'autres termes - changer de manière destructive une liste. Je ne m'intéresse pas tellement au code réel comme réponse que de comprendre le processus par lequel on pourrait passer une liste comme une fonction (ou un vecteur ou une chaîne) et ensuite la muter.

exemple:

(define (append! lst var) 
    (cons (lst var)) 
) 

Lorsque j'utilise l'approche comme ci-dessus, je dois faire quelque chose comme (define list (append! foo (bar)) que je voudrais quelque chose de plus générique.

Answer 1

La mutation, bien que permise, est fortement déconseillée dans Scheme. PLT est même allé jusqu'à supprimer set-car! et set-cdr! (bien qu'ils les "remplacés" par set-mcar! et set-mcdr!). Cependant, une spécification pour append! est apparue dans SRFI-1. Ce append! est un peu différent du vôtre. Dans le SRFI, l'implémentation peut, mais n'est pas requis pour modifier les cellules par défaut pour ajouter les listes.

Si vous voulez avoir un append! qui est garanti de modifier la structure de la liste qui est en cours ajouté à, vous devrez probablement écrire vous-même. Il n'est pas difficile:

(define (my-append! a b) 
    (if (null? (cdr a)) 
     (set-cdr! a b) 
     (my-append! (cdr a) b))) 

Pour que la définition simple, il n'y a pas de contrôle d'erreur, mais il est clair que vous devrez passer dans une liste de longueur au moins 1 a, et (de préférence) une liste (de n'importe quelle longueur) comme b. La raison a doit être au moins la longueur 1 parce que vous ne pouvez pas set-cdr! sur une liste vide.

Puisque vous êtes intéressé par comment cela fonctionne, je verrai si je peux expliquer. Fondamentalement, ce que nous voulons faire est de descendre la liste a jusqu'à ce que nous arrivions à la dernière paire cons, qui est (<last element> . null). Donc, nous voyons d'abord si a est déjà le dernier élément de la liste en vérifiant null dans le cdr. Si c'est le cas, nous utilisons set-cdr! pour le mettre à la liste que nous ajoutons, et nous avons terminé. Sinon, nous devons appeler my-append! sur le cdr de a. Chaque fois que nous faisons cela, nous nous rapprochons de la fin de a. Comme il s'agit d'une opération de mutation, nous n'allons rien retourner, donc nous n'avons pas besoin de nous soucier de former notre liste modifiée comme valeur de retour.

Answer 2

Mieux vaut tard que jamais pour mettre en quelques 2-3 cents sur ce sujet ...

(1) Il n'y a rien de mal à utiliser les procédures destructrices dans le schéma tout il y a une seule référence à la structure en cours de modification. Ainsi, par exemple, construire une grande liste de manière efficace, fragmentaire via une seule référence - et une fois complétée, faire cette liste (maintenant probablement non-à-être-modifiée) connue et référencée par divers référents.

(2) Je pense APPEND! devrait se comporter comme APPEND, seulement (potentiellement) de manière destructive. Et ainsi APPEND! devrait attendre un nombre quelconque de listes comme arguments. Chaque liste, mais la dernière serait probablement SET-CDR! 'D à la prochaine.

(3) La définition ci-dessus de APPEND! est essentiellement NCONC de Mac Lisp et Common Lisp. (Et autres lisps).