Discussion :

[l1informatique]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[jack-ft]

Bonjour,

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

mon essai :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[l1informatique]

bonjour,

je tente ce code,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

pourtant c une liste circulaire :s

[jack-ft]

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))!

par contre quand je met

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
(setq liste '(a b c))
(rplacd (cddr liste) liste) 
(circulaire liste)

[l1informatique]

bonjour,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
(setq liste '(a b c))

(rplacd (cddr liste) liste) 

(circulaire liste)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[jack-ft]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

ou bien par:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Tu peux aussi remplacer tout le bloc par:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
(let ((liste '(a b c)))
  (rplacd (cddr liste) liste) 
  (circulaire liste))

[byjav]

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?

[byjav]

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

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).

[jack-ft]

Ç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...

Je pensais à des lisps plus exotiques:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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...

[jack-ft]

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...).

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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...

[byjav]

> ((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é.

[jack-ft]

> ((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

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)!

[byjav]

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