Fonction qui détecte une circularité

Bonjour,

j'ai du mal à trouver la réponse de cette exercice,

2 - Fonction qui détecte une circularité
Écrire la fonction récursive circulaire qui détecte qu'une liste plate (sans sous-listes) est circulaire par son début.

Code:

---

1 2 3 4

(setq liste '(a b c)) (rplacd (cddr liste) liste) (circulaire liste) => t (circulaire '(a b c a b c)) => nil

---

Astuce : utilisez la fonction eq, qui compare deux adresses.

mon essai :

Code:

---

1 2 3 4 5

(defun circulaire (liste) (cond ((atom liste) nil) # si la liste est vide ((eq (cdr liste) (car liste) t) ((circulaire (cdr liste) (car liste)) ) )

---

mais ça ne marche pas :s

de l'aide svp

Bonjour,

Astuce : utilisez la fonction eq, qui compare deux adresses.

mon essai :

Code:

---

1 2 3 4 5

(defun circulaire (liste) (cond ((atom liste) nil) # si la liste est vide ((eq (cdr liste) (car liste) t) ((circulaire (cdr liste) (car liste)) ) )

---

mais sa ne marche pas :s

de l'aide svp[/QUOTE]

C'était bien parti!

Plutôt que de te donner la solution, je te donne quelques pistes...

Le premier test ((atom liste) nil) et son résultat associé sont bons!

Remarque: le test (eq (cdr liste) (car liste) vérifie si le reste de la liste (c'est-à-dire la liste sans le premier élément) est égal au premier élément de la liste. Comme on te dit que c'est une liste plate, son premier élément ne peut PAS être une liste.

Remarque: à la fin, dans (circulaire (cdr liste) (car liste)), tu appelles (récursivement (ce qui est bien!)) circulaire, mais avec 2 arguments, ce qui, d'un certain point de vue, est une bonne idée, mais, d'un autre, comme la fonction n'a qu'un paramètre... ça marche pô!
De plus (même remarque que précédemment), tu lui passes (car liste). Or, à aucun moment, on n'a besoin de s'interroger sur le contenu des éléments de la liste pour déterminer si elle est circulaire.

bonjour,

je tente ce code,

Code:

---

1 2 3 4 5

(defun circulaire (liste &optional (origine liste)) *(cond **((atom liste) nil) **((eq (cdr liste) origine)t) **((circulaire (cdr liste) origine)) ) )

---

par contre quand je met

Code:

---

1 2	[12]> (circulaire '(a b c a b c) (setq liste '(a b c))) NIL

---

pourtant c une liste circulaire :s

Bravo!
Pour moi, c'est bon (sous réserve que &optional (origine liste) mette bien la valeur de liste dans origine lors d'un appel avec un argument (ça peut dépendre de la version de lisp utilisée))!

Citation:

---

par contre quand je met

Code:

---

1 2	[12]> (circulaire '(a b c a b c) (setq liste '(a b c))) NIL

---

pourtant c une liste circulaire :s

---

Non non non! Y a pas de liste circulaire dans cet exemple!

Si on appelle circulaire avec plus d'un argument, on fausse tout:

Code:

---

1 2	(setq liste '(b c d)) (circulaire (cons 'a liste) liste) => t ; c'est de la triche...

---

Dans ce cas, circulaire teste que son 2ème argument est une sous-liste de son premier argument.


Pour avoir une vraie liste circulaire, reprends l'exemple de l'énoncé!

Qu'obtiens-tu avec:

Code:

---

1 2 3

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

---

bonjour,

quand j'essaye ces trois ligne, le deuxième m'envoie

Code:

---

1 2 3 4 5

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

---

Code:

---

1 2 3 4 5

(rplacd (cddr liste) liste) *** - Il n'y a plus de place pour des objets LISP. *** - Il n'y a plus de place pour des objets LISP. *** - Il n'y a plus de place pour des objets LISP.

---

Hum... Il semblerait que ton interprète lisp ait du mal à afficher la liste circulaire ainsi créée!

Quel lisp utilises-tu et sur quel OS ?

Si c'est bien un problème d'affichage, tu peux remplacer la ligne par:

Code:

---

(prog1 "tout va bien" (rplacd (cddr liste) liste)))

---

ou bien par:

Code:

---

(progn "Jusqu'ici, tout allait bien" (rplacd (cddr liste) liste)) "tout va bien")

---

Tu peux aussi remplacer tout le bloc par:

Code:

---

1 2 3

(let ((liste '(a b c))) (rplacd (cddr liste) liste) (circulaire liste))

---

Il faudrait affecter T à la variable *print-circle* ou lui attacher (bind) cette valeur avant d'afficher des listes circulaires.

Il me semble aussi que quelque chose manque dans la dernière clause de COND: peut-être, un T?

Citation:

---

Pour moi, c'est bon (sous réserve que &optional (origine liste) mette bien la valeur de liste dans origine lors d'un appel avec un argument (ça peut dépendre de la version de lisp utilisée))!

---

Ça ne doit pas en dépendre:
http://clhs.lisp.se/Body/03_da.htm

Citation:

---

An init-form can be any form. Whenever any init-form is evaluated for any parameter specifier, that form may refer to any parameter variable to the left of the specifier in which the init-form appears, including any supplied-p-parameter variables, and may rely on the fact that no other parameter variable has yet been bound (including its own parameter variable).

---

Citation:

---

Envoyé par byjav

Ça ne doit pas en dépendre:
http://clhs.lisp.se/Body/03_da.htm

---

Globalement, je suis assez d'accord avec toi... au moins pour tous les Common Lisps...

Cependant, le forum n'est pas censé être limité aux Common Lisps... :mrgreen:

Je pensais à des lisps plus exotiques:

Code:

---

1 2 3 4 5

*** Welcome to IELM *** Type (describe-mode) for help. ELISP> (defun foo (x &optional (y x)) (list x y)) foo ELISP> (foo 3) *** Eval error *** Invalid function: (lambda (x &optional (y x)) (list x y))

---

Conclusion irréfutable: il existe donc bien des lisps (un peu non common, j'avoue) qui ne le supportent pas!
CQFD :mouarf:

En fait, avant de (beaucoup) faire du Common Lisp, j'ai eu (aussi beaucoup) fait du Le_Lisp qui ne gère pas les arguments optionnels de la même façon (il me semble que Vlisp faisait aussi du déréférencement d'arbre).

Quant à Scheme, c'est encore différent...

Bon, d'accord, pour emacs-lisp: il peut le faire (n'est-ce pas formidable?)... à condition qu'on lui demande gentiment mais explicitement de faire comme si c'était du CL:

Code:

---

1 2 3 4

ELISP> (cl-defun foo (x &optional (y x)) (list x y)) foo ELISP> (foo 3) (3 3)

---

Dans le cas du PO, il y a un autre problème un peu plus délicat que j'ai déjà évoqué. Le fait d'introduire un argument optionnel fait qu'on autorise l'utilisateur à appeler la fonction avec 2 arguments. Du coup, la sémantique de la fonction change et devient:

Code:

---

1 2 3

(defun circulaire (l1 &optional (l2 l1)) "Retourne T si une partie stricte de la liste l1 est égale à la liste l2, si elle est fournie ou sinon à l1" ...)

---

Si on veut garder la définition stricte proposée dans l'exercice, on peut recourir à une fonction auxiliaire (globale ou imbriquée (à la scheme)):

Code:

---

1 2 3 4 5 6 7 8 9 10

(defun circulaire (l) "Retourne T si une partie stricte de la liste l1 est égale à l1" (and (consp l) (circulaire-aux (cdr l) l)))   (defun circulaire-aux (l1 l2) "Retourne T si l1 ou une partie de la liste l1 est égale à l2" (cond ((eq l1 l2) t) ((atom l1) ()) (t (circulaire-aux (cdr l1) l2))))

---

PS: merci pour le bouton "restaurer le contenu auto-enregistré" après plantage firefox...

Citation:

---

Envoyé par byjav

Il faudrait affecter T à la variable *print-circle* ou lui attacher (bind) cette valeur avant d'afficher des listes circulaires.

---

Effectivement, ça devrait pouvoir aider (au moins pour certains lisps...).

Citation:

---

Il me semble aussi que quelque chose manque dans la dernière clause de COND: peut-être, un T?

---

Globalement, je suis assez d'accord avec toi...

Pour la clarté du code, j'aime bien commencer la dernière clause d'un COND par T...

Toutefois et néanmoins, en cas de vacuité du body d'une clause (pas nécessairement la dernière) dont le test retourne une valeur différente de NIL, certains lisps (mais pas tous (pour autant que je me souvienne, Le_Lisp évalue le body qui, vide, retourne nil (et non le test de la clause))) rendent la valeur du test de la clause, ainsi qu'en atteste l'exemple suivant:

Code:

---

1 2 3 4

ELISP> (let ((x 'a)) (cond (x) ('b))) a ELISP> (let ((x ())) (cond (x) ('b))) b

---

Mais je préfère sans nul doute l'écriture sans ambiguïté et plus traditionnelle avec T et body de clause non vide:

Code:

---

1 2 3 4

ELISP> (let ((x 'a)) (cond (x x) (t 'b))) a ELISP> (let ((x ())) (cond (x x) (t 'b))) b

---

Bon... tout ça, c'est un peu du chipotage... :P

> ((circulaire (cdr liste) origine)) ) )

(circulaire (cdr liste) origine) est la condition et si elle n'est pas égale à NIL, la clause renvoie NIL. Ça a un air un peu bizarre, mais je n'ai pas examiné l'algorithme et c'est peut-être le comportement désiré.

Citation:

---

Envoyé par byjav

> ((circulaire (cdr liste) origine)) ) )

(circulaire (cdr liste) origine) est la condition et si elle n'est pas égale à NIL, la clause renvoie NIL.

---

Ben justement non! Voir http://clhs.lisp.se/Body/m_cond.htm

Citation:

---

If there are no forms in that clause, the primary value of the test-form is returned by the cond form.

---

Apparemment (comme je disais naguère et d'après les mêmes sources que toi), CL retourne bien le résultat du test lorsque celui-ci est non-nil et que le body de la clause est vide.

Mais je préfère quand même mettre quelque chose dans le body, ce qui évite de se poser des questions (auxquelles on a maintenant la réponse)!

Merci bien, jack-ft, je ne le savais pas !