Vérification de la circularité dans Lisp - même variable par la fonction récursive

Question

J'essaye de créer une fonction qui testerait si la liste donnée est circulaire avec un point de redémarrage étant le début de la liste.

Résultats attendus:

(setq liste '(a b c)) 
(rplacd (cddr liste) liste) 

(circular liste) => t 
(circular '(a b c a b c)) => nil 

Comme je veux simplement vérifier si un élément ultérieur est « équivalent » au premier, je ne veux pas construire l'ensemble tortoise and hare algorithm.

Voici mon code:

(defun circular (liste) 
    (let (beginningliste (car liste))) 
    (labels ((circ2 (liste) 
     (cond 
     ((atom liste) nil) 
     ((eq (car liste) beginningliste) t) 
     (t (circ2 (cdr liste))) 
     ))))) 

1. Il ne donne pas le résultat escompté, mais je ne comprends pas où mon erreur est
2. Je ne suis pas sûr que je utilise « étiquettes 'correctement
3. Existe-t-il un moyen de le faire sans utiliser' labels '?

---

Modifier. Je suppose que j'ai répondu à ma troisième question car je pense que j'ai trouvé un moyen plus simple. Cela fonctionnerait-il?

(defun circular (liste) 
    (cond 
     ((atom liste) nil) 
     ((eq (car liste) (cadr liste)) t) 
     (t (circular (rplacd liste (cddr liste)))) 
    ) 
    ) 

Answer 1

Tout d'abord, le comportement est indéfini lorsque vous muter des données constantes: lorsque vous citez quelque chose (ici la liste), l'environnement Lisp a le droit de le traiter comme une constante. Voir également this question pour savoir pourquoi defparameter ou defvar est préféré à setq. Et si ...

(setq list '(a b c)) 
(rplacd (cddr list) list) 

... serait mieux écrire:

(defparameter *list* (copy-list '(a b c))) 
(setf (cdr (last *list*)) *list*) 

Deuxièmement, votre code est mal formaté et a de mauvaises conventions de nommage (s'il vous plaît utiliser des tirets pour séparer les mots); Ici, il est avec une disposition conventionnelle, avec l'aide de emacs:

(defun circularp (list) 
    (let (first (car list))) 
    (labels ((circ2 (list) 
      (cond 
       ((atom list) nil) 
       ((eq (car list) first) t) 
       (t (circ2 (cdr list)))))))) 

Avec cette mise en forme, deux choses doivent être apparents:

• Le let contient aucune forme de corps: vous définissez les variables locales et ne jamais les utiliser; vous pourriez aussi bien supprimer la ligne let.

• De plus, le let manque une paire de parenthèses: ce que vous avez écrit définit un nom de variable first et un autre nom car, lié à list. Je présume que vous voulez définir first comme (car list).

• Vous définissez une fonction locale circ2 mais ne l'utilisez jamais. Je m'attendrais à la fonction circularp (le -p est pour "prédicat", comme numberp, stringp) pour appeler (circ2 (cdr list)). Je préfère renommer circ2 comme visit (ou recurse), parce que cela signifie quelque chose.

Avec les corrections ci-dessus, ce serait:

(defun circularp (list) 
    (let ((first (car list))) 
    (labels ((visit (list) 
       (cond 
       ((atom list) nil) 
       ((eq (car list) first) t) 
       (t (visit (cdr list)))))) 
     (visit (cdr list))))) 

Cependant, si votre liste n'est pas circulaire, mais contient les même élément plusieurs fois (comme '(a a b)), vous relèverez comme circulaire , parce que vous inspectez les données qu'il contient au lieu de la structure seulement ne pas regarder dans le CAR ici.

(defun circularp (list) 
    (let ((first list)) 
    (labels ((visit (list) 
       (cond 
       ((atom list) nil) 
       ((eq list first) t) 
       (t (visit (cdr list)))))) 
     (visit (cdr list))))) 

En outre, la fonction interne est queue récursive mais il n'y a aucune garantie qu'une implémentation Common Lisp élimine automatiquement les appels de queue (vous devez vérifier avec votre implémentation; la plupart peuvent le faire sur demande). Cela signifie que vous risquez d'allouer autant de trames de pile d'appels que vous avez d'éléments dans la liste, ce qui est mauvais. Mieux utiliser une boucle directement:

(defun circularp (list) 
    (loop 
    for cursor on (cdr list) 
    while (consp cursor) 
    thereis (eq cursor list))) 

dernier, mais non le moindre: votre approche est très commun, mais échoue lorsque la liste n'est pas une grande chaîne circulaire de cellules, mais simplement contient une boucle quelque part. Considérons par exemple:

CL-USER> *list* 
#1=(A B C . #1#) 
CL-USER> (push 10 *list*) 
(10 . #1=(A B C . #1#)) 
CL-USER> (push 20 *list*) 
(20 10 . #1=(A B C . #1#)) 

(voir that answer où j'expliquer ce que #1= et #1# moyenne)

Les listes avec des numéros en circularité avant d'exposition, mais vous ne pouvez pas utiliser la première cellule de contre comme marqueur, parce que vous serez en boucle pour toujours dans la sous-liste qui est circulaire. C'est le genre de problèmes que l'algorithme Tortoise et Hare résout (il pourrait y avoir d'autres techniques, la plus courante étant le stockage des éléments visités dans une table de hachage).

---

Après votre dernière modification, voici ce que je ferais si je voulais vérifier circularité, de façon récurrente, sans labels:

(defun circularp (list &optional seen) 
    (and (consp list) 
     (or (if (member list seen) t nil) 
      (circularp (cdr list) (cons list seen))))) 

Nous gardons une trace de toutes les visitées cellules cons dans seen, qui est optionnel et initialisé à NIL (vous pouvez passer une autre valeur, mais cela peut être vu comme une fonctionnalité). Ensuite, nous disons qu'une liste est circulaire par rapport à vu si c'est une contre-cellule qui soit: (i) existe déjà dans vu, soit (ii) est telle que sa CDR est circulaire par rapport à (cons list seen).

Le seul truc supplémentaire est là pour assurer le résultat est un booléen, et non la valeur de retour de member (qui est la sous-liste où l'élément recherchée est le premier élément): si votre environnement a *PRINT-CIRCLE* ensemble à NIL et la liste est réellement circulaire, vous ne voulez pas qu'elle essaie d'imprimer le résultat.

Au lieu de (if (member list seen) t nil), vous pouvez aussi utiliser:

• (when (member list seen))
• (position list seen)
• et bien sûr (not (not (member list seen)))