Discussion :

[l1informatique]

bonjour,

je bloque sur cette exercice que j'ai du mal à comprendre, :s

C. Définir une fonction qui ramène tous les atomes d'un arbre dans une unique liste plate. Nil n'est pas à considérer comme un atome, mais comme une liste. Réfléchissez au cas de l'atome en cdr.
(atomes '(a (b (c) (d)) (e f) (g (h)) nil)) => (a b c d e f g h)
(atomes '(a . d)) => (a d)

[jack-ft]

Comme il a été maintes fois répété dans ces forums, nous ne souhaitons pas donner la solution des exercices proposés, notamment parce que cela ne rend pas vraiment service à ceux qui n'arrivent pas à les résoudre.
Nous préférons donner des pistes, des indications et des explications afin que le PO trouve par lui-même et en tire un réel bénéfice.

Peux-tu nous dire ce que tu as du mal à comprendre dans cet exercice?
Peux-tu nous montrer ce que tu as essayé (que ça marche ou pas ou partiellement)?

[jack-ft]

Élémentaire!

Code :

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

1
2
3
4
Pour faire atomes de LISTE
  si LISTE est NIL, alors retourner NIL
  si LISTE est un atome, alors retourner une liste contenant l'unique élément LISTE
  si LISTE est un CONS, alors retourner les atomes contenus dans (CAR LISTE) et les atomes contenus dans (CDR LISTE)

ça ressemble énormément à get-cons!

[Kurodiam]

Bon , comme l'exercice m’intéresse mais je suis débutante (j'ai pas encore vu la fonction atom), j'ai essayé de réfléchir mais pas de résultats concrets :

Code :

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

1
2
3
4
5
6
7
8
(defun atomes (x)    # fonction permettant d’aplatir les atomes d'un arbre en une unique liste plate. 
  (cond
    ((null x) ())
    ((atom (car x ))   # test si l'argument est un atome ,et la méthode append pour extraire les atomes un par un ex: (y (t c)) et (d e i)
     (append (list (car x)) (atomes (cdr x)))
        (append (atomes (car x)) (atomes (cdr x ))))  # il faudrait tenir compte de la taille de la liste et faire une incrémentation petit à petit.
    ((not (listp x)) 'x)        # pour détecter s'il y'a le pointeur de droite pointe sur le doublet gauche (a . b) et retourner juste l'atome .
    (t (list (atomes (car x)) (atomes (cdr x)))))    # le hic , je pensais à faire (list 'cons (atomes ...) mais il faut déjà séparer les atomes dans le cas (a . b)

Je me suis basée sur la fonction get-cons crée dans le topic.

[jack-ft]

Hmmm... Y a plein de choses intéressantes dans ce que tu proposes... mais c'est beaucoup plus simple que ça!

Attention! 'x est juste le symbole x lui-même et non son contenu!
x est une variable. La fonction doit forcément retourner quelque chose dépendant de son contenu et non de son nom!
C'est une des difficultés des langages symboliques (où on peut manipuler des symboles).
Cela vient aussi des abus de langages que l'on fait souvent.
Par exemple, lorsque je dis que (null x) est une instruction qui teste si x est NIL, c'est un abus de langage!
Je devrais plutôt dire que (null x) teste si la valeur contenue dans la variable x est NIL (ou si le contenu de la variable x est NIL)!
Donc, par abus de langage ou dit souvent x à la place de la valeur de x ou la valeur contenue dans la variable x.
Si tu relis ce que j'ai écrit, tu verras que, généralement, je dis le symbole x ou le symbole 'x lorsque je veux parler du symbole lui-même et non de son contenu en tant que variable.

En gros (pour cet exercice), ATOM est juste le contraire de CONS. Donc recommence avec le pseudo-code suivant (en t'inspirant encore plus de get-cons):

Code :

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

1
2
3
4
Pour faire la liste d'atomes contenus dans X
  si X est NIL, alors retourner une liste vide
  si X est n'est pas un CONS, alors retourner une liste contenant l'unique élément X (sa valeur en tant que variable!)
  si X est un CONS, alors retourner la liste d'atomes contenus dans (CAR X) et la liste d'atomes contenus dans (CDR X)

La petite difficulté est de faire le "et"... (mais tu l'as quasiment résolue dans ce que tu proposes)

[Kurodiam]

Merci pour l'explication!
Je n'ai pas encore fait le cours sur les atomes , donc je vais attendre encore un peu avant de me précipiter à répondre

[jack-ft]

Euh... comme indiqué dans mon message précédent, ATOM est le contraire de CONS.
C'est-à-dire: est ATOM tout ce qui n'est pas CONS et réciproquement.
Plus précisément, d'un côté, il y a les CONS (paire de cellules) et, de l'autre, il y a les atomes, c'est-à-dire tout le reste (les nombres, les chaînes de caractères, les symboles, etc.).

Mais, en fait, tu n'as pas besoin de savoir ce qu'est un atome! Tu as déjà toutes les connaissances pour juste suivre l'algorithme proposé:

Code :

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

1
2
3
4
Pour les-atomes-de X
  si X est NIL, alors retourner une liste vide
  si X est n'est pas un CONS, alors retourner une liste contenant l'unique élément X (sa valeur en tant que variable!)
  si X est un CONS, alors retourner une liste qui contient les-atomes-de (CAR X) ainsi que les-atomes-de (CDR X)

[Kurodiam]

Euh... comme indiqué dans mon message précédent, ATOM est le contraire de CONS.
C'est-à-dire: est ATOM tout ce qui n'est pas CONS et réciproquement.
Plus précisément, d'un côté, il y a les CONS (paire de cellules) et, de l'autre, il y a les atomes, c'est-à-dire tout le reste (les nombres, les chaînes de caractères, les symboles, etc.).

Mais, en fait, tu n'as pas besoin de savoir ce qu'est un atome! Tu as déjà toutes les connaissances pour juste suivre l'algorithme proposé:

Code :

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

1
2
3
4
Pour les-atomes-de X
  si X est NIL, alors retourner une liste vide
  si X est n'est pas un CONS, alors retourner une liste contenant l'unique élément X (sa valeur en tant que variable!)
  si X est un CONS, alors retourner une liste qui contient les-atomes-de (CAR X) ainsi que les-atomes-de (CDR X)

Bon, voilà je pense avoir réussi et çà marche avec toutes les exceptions , merci pour ton aide

Code :

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

1
2
3
4
5
(defun atomes (x)
   (cond
      ((null x) nil)
      ((atom x (list x)) 
      (t (not (listp x)) (append (atomes (car x) (and (append (atomes (cdr x)) )) )) ))

[jack-ft]

Bon, voilà je pense avoir réussi et çà marche avec toutes les exceptions

Bravo! Si ça marche vraiment (je te fais confiance!), c'est que tu as probablement oublié de recopier (dans ton post sur ce forum) une parenthèse à la 4ème ligne pour fermer "(atom x" de cette manière:

Code :

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

1
2
3
4
5
(defun atomes (x)
   (cond
      ((null x) nil)
      ((atom x) (list x)) 
      (t (not (listp x)) (append (atomes (car x) (and (append (atomes (cdr x)) )) )) ))

Ensuite 3 (petites) remarques:
1. Dans ce code, lorsque x n'est ni NIL ni un atom, le COND passe à la 3ème et dernière clause.
Il évalue le test T qui est toujours vrai. Il évalue alors TOUT le reste qui est considéré comme une suite d'instructions (on appelle ça un progn implicite):

Code :

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

1
2
(not (listp x))
(append (atomes (car x) (and (append (atomes (cdr x)) )) ))

La 1ère instruction effectue un test qui ne sert à rien, puisqu'il passe de toute façon à la seconde instruction de la liste pour retourner son résultat.

2. Le 2ème APPEND n'a qu'un argument. Or, (append y) est rigoureusement la même chose que y (dans tous les cas).

3. De même, le AND n'a qu'un argument. Or (and z) est rigoureusement la même chose que z (dans tous les cas).

Je crois donc que tu peux simplifier encore un peu ton code...

Mais bravo quand même!

[Kurodiam]

Merci , mais je suis loin de connaitre tout en Common lisp .

Code :

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

1
2
3
4
5
(defun atomes (x)
   (cond
      ((null x) nil)
      ((atom x) (list x)) 
      (t (append (atomes (car x) (and append (atomes (cdr x)) )) ))  # on pourrait se passer du "and" ici , non ? et lorsque tu dis (append y) , tu veux dire aussi que l'on peut faire direct (append atomes(cdr))..... J'ai tendance à préférer mettre les parenthèses en cas de doutes pour que mon code ne plante pas .

[jack-ft]

Si tôt le matin?

Code :

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

      (t (append (atomes (car x) (and append (atomes (cdr x)) )) ))

Pour le point 1, c'est bon: tu as bien supprimé le test inutile (not (listp x)).

Par contre, atomes est une fonction avec 1 seul argument: or, le premier argument du premier appel de atomes est (car x). Il faut donc fermer la parenthèse juste après pour obtenir (atomes (car x)), comme tu l'avais d'ailleurs dans la version précédente de ton code.

# on pourrait se passer du "and" ici , non ?

Oui, c'est ce que j'ai dit dans le point 3: remplacer (and un_truc) par un_truc, quel que soit un_truc.

et lorsque tu dis (append y) , tu veux dire aussi que l'on peut faire direct (append atomes(cdr)).....

Non, un nom de fonction doit toujours être précédé d'une parenthèse!

J'ai tendance à préférer mettre les parenthèses en cas de doutes pour que mon code ne plante pas .

Oui. On ne peut pas supprimer les parenthèses comme ça, sans raison!

Par contre, on peut supprimer des appels de fonctions inutiles!
Par exemple, dans (* 1 (+ x y)), la multiplication par 1 n'est pas indispensable! On peut simplifier en (+ x y), non?

De même, lorsque je dis que (append y) est la même chose que y, je veux dire que ceci est vrai quel que soit y.
Dans le bout de code (append (atomes (cdr x))), ce qui joue le rôle de y (le premier et seul argument de append), c'est (atomes (cdr x)).
On peut donc en déduire que (append (atomes (cdr x))) est la même chose que (atomes (cdr x)) et ainsi simplifier le code.

[Kurodiam]

En effet , la multiplication par 1 est un élément neutre .

Sinon pour la correction de la dernière ligne , voilà :

Code :

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

(t (append (atomes (car x)) (atomes (cdr x)) )) ))

[jack-ft]

Sinon pour la correction de la dernière ligne , voilà :

Ben oui! Bravo!

Pour résumer:

Code :

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

1
2
3
4
5
(defun atomes (x)
   (cond
      ((null x) nil)
      ((not (consp x)) (list x))
      (t (append (atomes (car x)) (atomes (cdr x))))))

[Bruno-Vdh]

Oui bravo personnellement, je préfère cette écriture (bien que tu n’aies pas vu la fonction atom) :

Code :

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

1
2
3
4
5
6
7
(defun atomes (x)
  (cond
    ((null x) nil)
    ((atom x) (list x))
    (t (append (atomes (car x)) (atomes (cdr x))))
  )
)

Ce code consiste à « aplatir » une liste imbriqué, le car d’une liste peut être vu comme sa profondeur et le cdr comme largeur.
Bien que ce soit la façon la plus usuel pour parcourir ce type de liste, juste pour le jeu, je voulais signaler l’existence d’une variante au moyen de la fonction mapcar, qui trouve peut-être un intérêt dans le cas de listes beaucoup plus large que profonde..

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
(defun atomes (l)
  (apply 'append
         (mapcar '(lambda (x)
                    (if (atom x)
                      (list x)
                      (atomes x)
                    )
                  )
                 l
         )
  )
)

L’appel à la fonction mapcar effectuant le parcours sur la largueur, l’appel récursif ne sert plus qu’à descendre dans les imbrications de liste.

[Kurodiam]

Merci pour le complément

En effet , c'est plus court avec atom : (atom x) ==> (not (consp x))

Je suis encore au tout début en lisp !La fonction lambda , on l'a vu un peu en cours mais pas tout à fait comme cela ...