Common Lisp, liste de manutention (append etc.)

Question

Je dois gérer cette situation:

(defun make-point (a b) 
(cons a b)) 

Cette fonction crée l'un des points sur l'axe cartésien (I omettent des contrôles génériques pour des raisons pratiques). Comment puis-je implémenter une fonction où, à chaque appel de make-point, il met à jour une liste où tous les points sont ajoutés?

E.g.

'() 
((1.1)) 
((1.1)(2.4)) 
((1.1)(2.4)(4.5)) 

J'ai besoin de la liste en tant que paramètre pour une fonction suivante.

Answer 1

Vous définissez une variable:

(defvar *points* '()) 

Les astérisques autour du nom de la variable (appelée « serre-tête ») est une convention très forte CL pour désigner les variables qui sont déclarées spéciale, ce qui est le cas lorsque en utilisant DEFVAR/DEFPARAMETER. Ici, j'utilise DEFVAR parce que je ne veux pas que la liste des points soit réinitialisée à la liste vide si jamais j'ai besoin de recharger l'unité de compilation dans laquelle réside le code.

Ensuite, vous pouvez fournir une interface pour le programmeur abstraire cette liste de points:

(defun clear-all-points() 
    (setf *points* nil)) 

(defun add-point (point) 
    (push point *points*)) 

Ici vous pouvez voir que je stocker le point donné en face de la liste des points, ce qui est naturel façon de travailler avec des listes; ajouter des choses à la fin, vous oblige à parcourir la liste, ce qui est inutile et la plupart du temps, pas nécessaire. En outre, comment exactement vous ajoutez un nouvel élément pourrait changer la façon dont la liste des points peuvent être utilisés:

• si vous implémentez add-point comme

  (setf *points* (append *points* (list point))) 
  

  ... alors la liste référencée par *points* est un copier, et si vous avez précédemment enregistré *points* dans un autre endroit, vous avez maintenant deux listes de points (je ne dis pas si c'est juste ou faux ici, juste expliquer ce qui se passe);

• si, toutefois, vous muter la liste:

  (setf *points* (nconc *points* (list point))) 
  

  ... vous pouvez partager la liste entre les différents objets, et chaque fois qu'ils lisent la liste, ils auront la mise à jour liste de tous les points.

Vous pourriez également avoir besoin de considérer la quantité de mémoire que vous utiliserez avec les deux approches. Si vous ajoutez en copiant, avec APPEND, la liste précédente sera finalement récupérée par le garbage collector; Si vous ajoutez des points trop fréquemment, vous commencerez à détruire la mémoire de manière à dégrader les performances.

Si vous devez mettre les choses à la fin sans recourir à NCONC pensez à utiliser une file d'attente ou un tableau. Une file d'attente de base peut être simplement mis en œuvre sur une liste, à travers un objet de file d'attente qui est juste une contre-cellule où le car est la première cellule de la liste sous-jacente et la cdr est le dernier contre-cellule la même liste. Lorsque vous ajoutez un élément x à une liste (e0 ... en), vous allez de cet état:

(e0 . (... (en . nil) ...)) 
^first  ^last 

... à celui-ci

(e0 . (... (en . (x . nil)) ...)) 
^first    ^last 

Vous pouvez essayer la mise en œuvre comme un autre exercice. Puis, vous pouvez garder votre fonction intacte (mais indentée); vous aurez probablement à faire des points sans les ajouter dans la liste globale, il est donc logique de garder les choses séparées:

(defun make-point (a b) 
    (cons a b)) 

Si vous en avez besoin, vous pouvez définir une fonction auxiliaire qui combinent les deux actions:

(defun add-new-point (a b) 
    (add-point (make-point a b))) 

Notez également que les espaces sont significatifs: ce que vous avez écrit dans la sortie souhaitée (par exemple (1.1)) sont des listes de nombres à virgule flottante.