Discussion :

[jahol]

Bonjour Tout le monde
Je suis confronté à un problème concernant la double récursion sur une liste.

Je dois créer une fonction qui renvoie la dernière occurence d'une lettre qu'on recherche suivie du reste de la liste.
For example:

(function 'z '((a z)c d))
(Z)


(function 'x '((a (x x)) x c x d e))
(x d e)

La logique de mon développement est la suivante.
Je regarde si l'élément recherché figure dans (last liste), et si c'est le cas je renvoie la bonne réponse;

Mais si c pas le cas que fais je?
Comment parcourir la liste dans l'autre sens(Existe t'il une fonction qui renvoie previous d'un élément d'une liste, ou je dois la créer)?

Voilà j'espère avoir été clair. Je pense que je dois utiliser la double récursion pour résoudre ce problème, mais je suis toujours dans le brouillard.

Merci de votre aide

[Garulfo]

Bonjour Tout le monde[...]

Salut,

Bon avant tout, il y a une balise code à utiliser pour présenter du code.
Ensuite, ton problème est d'ordre algorithmique et non de l'ordre de la mise en pratique en lisp. Car visiblement, tu n'as pas trouvé la réponse.

Je regarde si l'élément recherché figure dans (last liste), et si c'est le cas je renvoie la bonne réponse;

Pas exactement: tu regardes s'il y a une réponse dans la suite de la liste. Pas juste si l'élément y est. Mais il te manque des morceaux (cf. après).

Mais si c pas le cas que fais je?
Comment parcourir la liste dans l'autre sens(Existe t'il une fonction qui renvoie previous d'un élément d'une liste, ou je dois la créer)?

C'est là ton erreur: ta fonction ne commence pas en plein milieu de la liste mais au début.

Il manque un morceau dans l'étape qui tu avais trouvé. Notamment tu sembles ignorer complètement la cellule de tête de ta liste. Comment espères-tu trouver quoique ce soit ?

Il faut donc que tu te demandes quoi faire, en fonction de la cellule de tête. Si elle contient la valeur recherché, que fais-tu ?
Et sinon, que fais-tu ?

Là tu as deux cas exhaustif. Dans le « que fais-tu ? » tu utiliseras la queue de ta liste.

Réfléchis à ça, et reviens nous voir en cas de besoin.

[jack-ft]

Bonjour Tout le monde
Je suis confronté à un problème concernant la double récursion sur une liste.

Je dois créer une fonction qui renvoie la dernière occurence d'une lettre qu'on recherche suivie du reste de la liste.
For example:

Code :

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

1
2
3
4
5
6
(function 'z '((a z)c d))
(Z)
 
 
(function 'x '((a (x x)) x c x d e))
(x d e)

La logique de mon développement est la suivante.
Je regarde si l'élément recherché figure dans (last liste), et si c'est le cas je renvoie la bonne réponse;

Mais si c pas le cas que fais je?
Comment parcourir la liste dans l'autre sens(Existe t'il une fonction qui renvoie previous d'un élément d'une liste, ou je dois la créer)?

Voilà j'espère avoir été clair. Je pense que je dois utiliser la double récursion pour résoudre ce problème, mais je suis toujours dans le brouillard.

Merci de votre aide

Bonjour,

est-ce que tu peux expliciter la logique (ou les spécifications de la fonction)?

Pourquoi est-ce que (x d e) est plus que (x x) la dernière occurrence de x dans ((a (x x)) x c x d e)?
Car on pourrait dire que (x x) est plus en queue, car de longueur 2, que (x d e) qui est de longueur 3 !

Tes exemples semblent indiquer que la "liste" à explorer est en fait plus un arbre qu'une liste. (pour moi, une liste est plutôt une séquence d'éléments (tous plus ou moins du même type), alors qu'un arbre est plutôt un groupe de noeuds, branches et feuilles raccordés ensemble).

Du coup, tu peux t'interroger sur la manière de parcourir cet arbre.


Sinon, une manière "simple" de résoudre un problème par récurrence est la suivante:

imagine que tu possèdes déjà une fonction "foo" qui soit capable de trouver la dernière occurrence d'un élément dans un arbre.
Comment pourrais-tu créer une nouvelle fonction "bar" pour trouver la dernière occurrence d'un élément dans un arbre en te servant de "foo", mais évidemment sans la triviale implémentation:

Code :

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

(defun bar (x arbre) (foo x arbre))

Bonne continuation

)jack(

[jahol]

Salut Garulfo et jack-t et Merci.

J'ai essayé de pousser un tout p'tit peu la réflexion avec votre aide.
J'utilise bien une liste (qui peut etre représentée sous forme d'arbre binaire !).

@Jack-t la spécifications de la fonction est de trouver la dernière occurence d'un élément recherché dans une liste ainsi que le reste de la liste.


J'ai une solution qui (je reconnais) n'est pas optimale:
Je regarde si l'élément recherché est présent en début de liste, si c'est le cas je vérifie sa présence dans le reste de la liste.
Que fais je?
- Si l'élement recherché est trouvé et n'est pas présent dans le reste de la liste , alors je construis la liste finale(résultat).
- Si ce dernier est présent , je rappelle la fonction.

Etant donné que c'est la dernière occurence qui m'interesse, je commence par executer le reste de la liste. Si je n'ai aucun résultat ,j'execute le début de la liste.

Solution non optimale parce qu'il y a une partie du code qui est executée deux fois.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
(defun f1 (x l)
                   (cond 
                      ((endp l) '())
                      ((atom (first l))
                       (if (eq x (first l))
                           (if (member x (rest l))
                               (f1 x (rest l))
                               (cons x (rest l))
                               )
                           (f1 x (rest l))))
                    ((eq (f1 x (rest l)) nil) (f1 x (first l)))
                    (t (f1 x (rest l)))))
 
(defun F2 (x l)
  (let ((rep (f1 x l)))
  (if (eq rep nil) 
      l
      rep)
    )
  )

[dividee]

Vu les exemples du premier post et le code du précédent, il me semble plutôt que la spécification serait:
Renvoyer le plus petit sous-arbre d'un arbre binaire (l) contenant la dernière occurrence d'un atome donné (x) dans un parcours ordonné de cet arbre (ou l'arbre complet si l'atome n'y figure pas (cf. fonction f2)).

Si c'est bien ça, il me semble que le test "member x (rest l)" est non seulement inutile, mais incorrect, car il ne trouverait pas les occurrences de x dans les sous-arbres de gauches de (rest l).

Etant moi-même débutant en LISP, je propose ceci, mais je ne sais pas si cette utilisation assez idiomatique de AND et OR est conseillée en pratique:

Code :

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

1
2
3
4
5
6
7
8
9
(defun f1 (x l)
  (and l
       (or (f1 x (cdr l))
	   (if (atom (car l))
	       (if (eql x (car l)) l)
	       (f1 x (car l))))))
 
(defun f2 (x l)
  (or (f1 x l) l))

[jack-ft]

Salut Garulfo et jack-t et Merci.

J'ai essayé de pousser un tout p'tit peu la réflexion avec votre aide.
J'utilise bien une liste (qui peut etre représentée sous forme d'arbre binaire !).

@Jack-t la spécifications de la fonction est de trouver la dernière occurence d'un élément recherché dans une liste ainsi que le reste de la liste.

Bonjour,

si la spécification est bien de trouver la dernière occurrence d'un élément recherché dans une liste (et non un arbre) ainsi que le reste de la liste,
alors la réponse est vraiment simple:

Code :

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

1
2
3
 
(defun f1 (x l)
  (member x l)

Easy, isn't it?

J'ai une solution qui (je reconnais) n'est pas optimale:
Je regarde si l'élément recherché est présent en début de liste, si c'est le cas je vérifie sa présence dans le reste de la liste.
Que fais je?
- Si l'élement recherché est trouvé et n'est pas présent dans le reste de la liste , alors je construis la liste finale(résultat).
- Si ce dernier est présent , je rappelle la fonction.

Etant donné que c'est la dernière occurence qui m'interesse, je commence par executer le reste de la liste. Si je n'ai aucun résultat ,j'execute le début de la liste.

Je crois que ce serait vraiment plus simple si tu essayais de "penser" et t'exprimer avec un arbre (qui a dit "je préfère un crayon"?).

Code :

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

1
2
3
4
5
Un arbre binaire est 
    ou bien une feuille 
    ou bien un noeud (ou racine) avec 
           un arbre gauche 
        et un arbre droit.

Parfois l'arbre binaire peut être simplifié et ne contient pas vraiment de racine.

Solution non optimale parce qu'il y a une partie du code qui est executée deux fois.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
(defun f1 (x l)
                   (cond 
                      ((endp l) '())
                      ((atom (first l))
                       (if (eq x (first l))
                           (if (member x (rest l))
                               (f1 x (rest l))
                               (cons x (rest l))
                               )
                           (f1 x (rest l))))
                    ((eq (f1 x (rest l)) nil) (f1 x (first l)))
                    (t (f1 x (rest l)))))
 
(defun F2 (x l)
  (let ((rep (f1 x l)))
  (if (eq rep nil) 
      l
      rep)
    )
  )

Pourquoi veux-tu retourner l si f1 ne trouve rien?

Bizarre, cette peur du vide...

et je suis d'accord avec dividee (voir plus loin).

Vu les exemples du premier post et le code du précédent, il me semble plutôt que la spécification serait:
Renvoyer le plus petit sous-arbre d'un arbre binaire (l) contenant la dernière occurrence d'un atome donné (x) dans un parcours ordonné de cet arbre (ou l'arbre complet si l'atome n'y figure pas (cf. fonction f2)).

Ah!!!! OUI!

Je préfère!

encore que:
- j'aimerais savoir ce que tu entends par "le plus petit". S'il y a une occurrence quelque part dans le car et une autre dans le cdr, comment définis-tu le plus petit?
- j'aimerais savoir de quel parcours ordonné il s'agit (j'en connais plusieurs (notamment les 6 classiques: GRD, DRG, RGD, RDG, GDR, DGR (j'ai d'ailleurs un peu de mal à en imaginer d'autres...)))
- je préfèrerais retourner nil plutôt que l'arbre complet si l'atome n'y figure pas (comme fait la fonction "member") sinon on ne distingue pas bien (f2 'x '(x y)) de (f2 'z '(x y)).

Si c'est bien ça, il me semble que le test "member x (rest l)" est non seulement inutile, mais incorrect, car il ne trouverait pas les occurrences de x dans les sous-arbres de gauches de (rest l).

Tout à fait exact, mon cher Watson!

Etant moi-même débutant en LISP, je propose ceci, mais je ne sais pas si cette utilisation assez idiomatique de AND et OR est conseillée en pratique:

Code :

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

1
2
3
4
5
6
7
8
9
(defun f1 (x l)
  (and l
       (or (f1 x (cdr l))
	   (if (atom (car l))
	       (if (eql x (car l)) l)
	       (f1 x (car l))))))
 
(defun f2 (x l)
  (or (f1 x l) l))

C'est beaucoup mieux et l'usage de "or" dans "f1" me convient tout à fait.

L'usage du "and" me convient moins bien. Dans ce cas, je prèfére "cond" "when" "unless" ou "if".

Mais, à mon humble avis, on peut faire encore un petit peu mieux et un peu plus simple...

As-tu essayé ceci:

Code :

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

(f1 'x '(a . b))

Et ceci:

Code :

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

1
2
(let ((x '(a)))
   (f1 x (list x)))

Et que disent les specs pour ceci:

Code :

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

(f1 'x 'x)

et ceci:

Code :

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

(f1 'x '(a . x))

Encore un petit effort...

)jack(

[dividee]

Bonjour jack-ft,

Oui je me suis embrouillé avec la définition d'un arbre. Comme je suis fainéant je vais essayer de changer la spec plutôt que le code
J'avais d'abord pensé à un arbre n-aire, mais comme j'avais un peu de mal à formuler ce que devait être la valeur de retour, je suis passé à un arbre binaire, et j'ai perdu quelques plumes au passage.
En fait, je pensais à l'encodage d'un arbre n-aire en arbre binaire, et à sa représentation sous forme de cons cell, telle qu'indiquée ici.
Pour le parcours, il n'y a que deux ordres possibles: GD ou DG, vu que la racine ne contient pas d'info. J'aurais du préciser qu'il s'agissait de la dernière occurrence dans un parcours GD (ou de façon équivalente, de la première occurrence dans un parcours DG).

Donc la spec devient:

"Rechercher la première occurrence d'un atome donné dans le parcours droite-gauche d'un arbre n-aire de hauteur >=1 donné, et retourner un nouvel arbre n-aire composé d'une racine ayant pour fils l'atome trouvé et ses frères droits (ou NIL si l'atome n'est pas trouvé)."

Du coup:

Code :

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

(f1 'x '(a . b))

et

Code :

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

(f1 'x '(a . x))

sortent de la spec car ne correspondent pas à la représentation d'un arbre n-aire.

Code :

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

1
2
(let ((x '(a)))
   (f1 x (list x)))

Celle-là sortait déjà précédemment de la spec car x n'est pas un atome

Code :

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

(f1 'x 'x)

cf. hauteur >=1 dans la spec (oui je sais c'est petit).

Et voilà, maintenant ce n'est plus le code qui est faux mais l'appelant qui ne respecte pas les préconditions

[dividee]

Ou peut-être même plus simple:
"Rechercher la première occurrence d'un atome donné dans le parcours droite-gauche d'un arbre n-aire de hauteur >=1 donné, et retourner le plus petit sous-arbre de l'arbre initial contenant l'atome trouvé et ses frères droits (ou NIL si l'atome n'est pas trouvé)."

mais je ne suis pas certain de la définition de sous-arbre: pour un noeud du sous-arbre, faut-il inclure tous les fils se trouvant dans l'arbre initial ? Si c'est le cas, alors il faut remplacer "sous-arbre" par "sous-graphe connexe" et là je pense que ça doit être bon.

Hum, finalement c'est pas tellement plus simple...

[Garulfo]

[...]
si la spécification est bien de trouver la dernière occurrence d'un élément recherché dans une liste (et non un arbre) ainsi que le reste de la liste,
alors la réponse est vraiment simple:

Code :

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

1
2
3
 
(defun f1 (x l)
  (member x l)

Easy, isn't it?

Pas vraiment, car tu oublies que si un prof pose cette question, c'est qu'il veut voir le code faisant ça

On apprends à coder les fonctions pour les comprendre et comprendre les principes. Après on utilise celle qui existe (et on évite de les recoder pour rien).

Mais d'après dividee, il semble que la solution soit plutôt une forme de member pour un arbre et non une liste effectivement.

J'interviendrais bien. Mais il me semble que Jack-ft est bien assez locace et plus de blahblah pourrait t'embrouiller

[jack-ft]

Pas vraiment, car tu oublies que si un prof pose cette question, c'est qu'il veut voir le code faisant ça

On apprends à coder les fonctions pour les comprendre et comprendre les principes. Après on utilise celle qui existe (et on évite de les recoder pour rien).

Tu as parfaitement raison!

En plus, j'ai volontairement mis un code archi-faux (qui donne la première et non la dernière occurrence) pour voir si quelqu'un suivait...

Mais d'après dividee, il semble que la solution soit plutôt une forme de member pour un arbre et non une liste effectivement.

J'interviendrais bien. Mais il me semble que Jack-ft est bien assez locace et plus de blahblah pourrait t'embrouiller

Loquaçons, il en restera bien quelque chose...

)jack(

[jack-ft]

Bonjour jack-ft,
Oui je me suis embrouillé avec la définition d'un arbre. Comme je suis fainéant je vais essayer de changer la spec plutôt que le code

Petit canaillou !

J'avais d'abord pensé à un arbre n-aire, mais comme j'avais un peu de mal à formuler ce que devait être la valeur de retour, je suis passé à un arbre binaire, et j'ai perdu quelques plumes au passage.
En fait, je pensais à l'encodage d'un arbre n-aire en arbre binaire, et à sa représentation sous forme de cons cell, telle qu'indiquée ici.
Pour le parcours, il n'y a que deux ordres possibles: GD ou DG, vu que la racine ne contient pas d'info.

ça me paraît sensé!

Je préfère qu'on considère carrément un arbre binaire représenté par un paquet de cons cells attachées entre elles (pour simplifier, on pourrait ajouter "sans circularité").

Je reprends ma définition d'arbre binaire, un peu lispifiée:

Code :

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

1
2
3
4
5
Un arbre binaire est 
    ou bien un atome
    ou bien un cons avec 
           un arbre gauche 
        et un arbre droit.

J'aurais du préciser qu'il s'agissait de la dernière occurrence dans un parcours GD (ou de façon équivalente, de la première occurrence dans un parcours DG).

Je t'invite à méditer sur ce que tu viens d'écrire...

ou, dit autrement: "nous n'avons pas les mêmes valeurs"... surtout en ce qui concerne l'équivalence...

Donc la spec devient:

"Rechercher la première occurrence d'un atome donné dans le parcours droite-gauche d'un arbre n-aire de hauteur >=1 donné, et retourner un nouvel arbre n-aire composé d'une racine ayant pour fils l'atome trouvé et ses frères droits (ou NIL si l'atome n'est pas trouvé)."

Pour être parfaitement précis, il faudrait dire ce qu'on entend par "occurrence"...

Il semblerait bien que c'est le cas lorsque le sous-arbre gauche est égal (ou eq ou eql ou equal, comme on veut) à l'élément recherché.

Du coup:

Code :

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

(f1 'x '(a . b))

et

Code :

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

(f1 'x '(a . x))

sortent de la spec car ne correspondent pas à la représentation d'un arbre n-aire.

Code :

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

1
2
(let ((x '(a)))
   (f1 x (list x)))

Celle-là sortait déjà précédemment de la spec car x n'est pas un atome

Code :

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

(f1 'x 'x)

cf. hauteur >=1 dans la spec (oui je sais c'est petit).

Euh... désolé, je ne suis pas d'accord...

Pour moi, (a . b) est bien un arbre binaire. Petit, je l'accorde, mais il a bien un sous-arbre gauche qui est la feuille "a" et un sous-arbre droit, la feuille "b".

et 'x aussi, c'est juste une feuille d'un arbre...

et member ne s'embarrasse pas de savoir si l'élément recherché est un atome ou autre chose (sauf en ce qui concerne le test d'égalité, bien sûr).

Et voilà, maintenant ce n'est plus le code qui est faux mais l'appelant qui ne respecte pas les préconditions

Puisque tu as déjà donné une solution quasiment parfaite, voici celle que je proposerais:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
(defun f1 (x l)
  (cond ((not (consp l)) nil)
        ((eq x (car l))
         ;; On en a trouvé un ici
         ;; => on ne cherche plus à gauche
         ;;    mais on cherche plus loin à droite
         ;; (Rq: récursivité non terminale)
         (or (f1 x (cdr l)) l))
        (t
         ;; On n'en a pas trouvé ici
         ;; => on cherche à droite
         ;;    puis, si échec, à gauche
         (or (f1 x (cdr l)) (f1 x (car l))))))

Si on "factorise" une partie du code, on peut aboutir à un code plus compact et un peu moins redondant, mais que je trouve un peu moins facile à lire:

Code :

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

1
2
3
4
5
6
(defun f1 (x l)
  (when (consp l)
    (or (f1 x (cdr l))
        (if (eq x (car l))
            l
          (f1 x (car l))))))

On remarquera, au passage, que ce code répond comme j'aime aux questions limites que j'avais posées...

j'espère que j'ai suffisamment loquacé...

)jack(

[dividee]

Je t'invite à méditer sur ce que tu viens d'écrire...

ou, dit autrement: "nous n'avons pas les mêmes valeurs"... surtout en ce qui concerne l'équivalence...

Désolé, je ne vois pas ce que tu veux dire; le parcours DG visitera les feuilles dans l'ordre inverse d'un parcours GD; la dernière occurrence d'un atome dans un parcours GD est donc la première occurrence dans un parcours DG.

C'est assez facile à démontrer sur un arbre binaire, par induction sur la structure d'un arbre:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
- Si l'arbre est un atome, la propriété est trivialement vraie vu que
  l'atome recherché est présent au plus une fois.
 
- Si l'arbre est un 'cons', il est constitué de 2 sous-arbres; l'hypothèse
  d'induction étant que la propriété est vraie pour chaque sous-arbre.
 
  * si l'atome est présent dans le sous-arbre droit:
     - la dernière occurence trouvée par le parcours GD de l'arbre sera la
       dernière occurence trouvée par le parcours GD du sous-arbre droit
       (car le sous-arbre droit est visité en dernier dans le parcours GD)
     - la première occurence trouvée par le parcours DG de l'arbre sera la
       première occurence trouvée par le parcours DG du sous-arbre droit
       (car ...)
     Comme l'hypothèse d'induction nous indique que la propriété est vraie
     pour le sous-arbre droit, elle l'est donc pour l'arbre entier
 
  * si l'atome est présent dans le sous-arbre gauche mais pas le droit:
     - la dernière occurence trouvée dans le parcours GD de l'arbre sera la
       dernière occurence trouvée par le parcours GD du sous-arbre gauche
     - idem pour le parcours DG, on se ramène au parcours DG du sous-arbre
       gauche
     Hypothèse d'induction -> OK
 
  * si l'atome n'est pas présent dans l'arbre, la propriété est trivialement
    vraie
CQFD

Pour être parfaitement précis, il faudrait dire ce qu'on entend par "occurrence"...

Il semblerait bien que c'est le cas lorsque le sous-arbre gauche est égal (ou eq ou eql ou equal, comme on veut) à l'élément recherché.

Quant au prédicat, eql me semble le plus naturel (par défaut en tout cas); pourquoi exclure les nombres et les caractères en utilisant eq?
Une autre possibilité serait d'utiliser tree-equal. Cela me semble une bonne idée vu le contexte... On rechercherait alors un sous-arbre dans un arbre.
Une version plus évoluée de la fonction pourrait, comme member, prendre des keyword arguments pour modifier ce comportement.

Je ne vois rien dans les exemples de jahol qui indiquerait ce qu'il faudrait faire si c'est le sous-arbre droit qui est "égal" à l'élément recherché. Je m'attendais plutôt à ce qu'on retourne juste l'élément, dans ce cas.

Pour moi, (a . b) est bien un arbre binaire. Petit, je l'accorde, mais il a bien un sous-arbre gauche qui est la feuille "a" et un sous-arbre droit, la feuille "b".

et 'x aussi, c'est juste une feuille d'un arbre...

Je ne dis pas le contraire; je parlais d'arbres n-aires dans un représentation spécifique. Mais bon, allons-y pour l'arbre binaire.

et member ne s'embarrasse pas de savoir si l'élément recherché est un atome ou autre chose (sauf en ce qui concerne le test d'égalité, bien sûr).

OK; dans ce cas il faudrait faire attention à ne pas mentionner 'atome' dans la spec mais, comme pour member, parler d'un "élément"

Puisque tu as déjà donné une solution quasiment parfaite, voici celle que je proposerais:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
(defun f1 (x l)
  (cond ((not (consp l)) nil)
        ((eq x (car l))
         ;; On en a trouvé un ici
         ;; => on ne cherche plus à gauche
         ;;    mais on cherche plus loin à droite
         ;; (Rq: récursivité non terminale)
         (or (f1 x (cdr l)) l))
        (t
         ;; On n'en a pas trouvé ici
         ;; => on cherche à droite
         ;;    puis, si échec, à gauche
         (or (f1 x (cdr l)) (f1 x (car l))))))

Si on "factorise" une partie du code, on peut aboutir à un code plus compact et un peu moins redondant, mais que je trouve un peu moins facile à lire:

Code :

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

1
2
3
4
5
6
(defun f1 (x l)
  (when (consp l)
    (or (f1 x (cdr l))
        (if (eq x (car l))
            l
          (f1 x (car l))))))

On remarquera, au passage, que ce code répond comme j'aime aux questions limites que j'avais posées...

Je peux difficilement le remarquer, vu que tu n'avais pas donné les réponses que tu aimais...
Maintenant je peux les connaître:

Code :

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

1
2
3
 
> (f1 'x '(a . b))
NIL

OK

Code :

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

1
2
3
 
> (f1 'x '(a . x))
NIL

Je m'attendais plutôt à (cf plus haut):

Code :

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

1
2
3
 
> (f1 'x '(a . x))
X

Code :

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

1
2
3
4
 
> (let ((x '(a)))
     (f1 x (list x)))
((A))

OK, si on veille bien à ne pas parler d'atome dans la spec

Code :

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

1
2
3
 
> (f1 'x 'x)
NIL

Ici aussi, je m'attendais plutôt à X comme réponse

Le seul petit problème avec ma conception de la spec est que si on recherche NIL, on ne peut pas distinguer entre un NIL qui indiquerait "non trouvé" et un NIL qui serait trouvé dans un CDR... J'interdirais donc de chercher NIL pour l'instant...

Voici donc mon second essai:

Code :

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

1
2
3
4
5
6
7
 
(defun f1 (x l)
  (if (eql x l)
      l
      (when (consp l)
	(or (f1 x (cdr l))
	    (when (f1 x (car l)) l)))))

j'espère que j'ai suffisamment loquacé...

)jack(

Je loue ta loquacité

<offtopic> dans une balise [ code], comment éviter l'insertion de lignes vierges à la fin ? Ca ne le faisait pas avant, il me semble. Et éviter les retours de ligne autour des balises à l'édition ne semble plus avoir d'effet. </offtopic>

[jack-ft]

Désolé, je ne vois pas ce que tu veux dire; le parcours DG visitera les feuilles dans l'ordre inverse d'un parcours GD; la dernière occurrence d'un atome dans un parcours GD est donc la première occurrence dans un parcours DG.

C'est assez facile à démontrer sur un arbre binaire, par induction sur la structure d'un arbre:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
- Si l'arbre est un atome, la propriété est trivialement vraie vu que
  l'atome recherché est présent au plus une fois.
 
- Si l'arbre est un 'cons', il est constitué de 2 sous-arbres; l'hypothèse
  d'induction étant que la propriété est vraie pour chaque sous-arbre.
 
  * si l'atome est présent dans le sous-arbre droit:
     - la dernière occurence trouvée par le parcours GD de l'arbre sera la
       dernière occurence trouvée par le parcours GD du sous-arbre droit
       (car le sous-arbre droit est visité en dernier dans le parcours GD)
     - la première occurence trouvée par le parcours DG de l'arbre sera la
       première occurence trouvée par le parcours DG du sous-arbre droit
       (car ...)
     Comme l'hypothèse d'induction nous indique que la propriété est vraie
     pour le sous-arbre droit, elle l'est donc pour l'arbre entier
 
  * si l'atome est présent dans le sous-arbre gauche mais pas le droit:
     - la dernière occurence trouvée dans le parcours GD de l'arbre sera la
       dernière occurence trouvée par le parcours GD du sous-arbre gauche
     - idem pour le parcours DG, on se ramène au parcours DG du sous-arbre
       gauche
     Hypothèse d'induction -> OK
 
  * si l'atome n'est pas présent dans l'arbre, la propriété est trivialement
    vraie
CQFD

Euh... dans mon jeune temps, on faisait de l'induction sur N (ensemble des entiers):

Code :

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

1
2
si (p(0) et pour tout n, p(n) => p(n+1))
alors  pour tout n, p(n)

Je croyais que ce n'était pas directement transposable sur un arbre, mais ta démonstration me semble suffisamment convaincante!

Je viens de me rendre compte que, comme tu l'as si bien fait remarquer, le parcours GD est bien l'exact inverse du parcours DG. Pour m'en convaincre, il m'a suffi de dessiner un petit arbre avec 4 feuilles et de suivre son parcours dans les 2 sens.

J'ai cru un instant que le problème était ailleurs, mais ça ne marche pas non plus.

Tu as dit que les seuls parcours étaient GD et DG, mais il me semble que, dans l'exercice donné, bien que les noeuds ne portent pas d'information additionnelle, ils portent toutefois de l'information. En effet, dans le parcours de l'arbre, on va bien tantôt à droite, tanôt à gauche (pour appliquer le même processus à ces sous-arbres), mais on travaille aussi sur le noeud, car un noeud est candidat à être une réponse s'il est porteur d'une occurrence, c'est-à-dire si son sous-arbre gauche est l'élément cherché. Ce test (qui semble être un "test à gauche") est à faire que l'on parcoure l'arbre de droite à gauche ou de gauche à droite. Il est indépendant de la récursivité. De ce raisonnement, j'en déduis que le parcours est DRG et que (comme tu l'as dit) on cherche bien la première occurrence.

Du coup, le parcours GRD est bien l'exact parcours inverse de DRG et sa dernière occurrence est bien celle que l'on cherche.

En fait, mon erreur vient du fait que je pensais plus à faire le test d'occurrence AVANT de plonger à droite puis à gauche, auquel cas il me fallait prendre la dernière occurrence d'un parcours RDG où l'on ne va à gauche que si l'on n'a rien trouvé à droite. C'est cette pensée que reflète ma première fonction.

Bref, mon intuition était mauvaise et je trouve bien plus élégant ta formulation de chercher la première occurrence d'un parcours DRG. C'est d'ailleurs cette formulation que reflète ma seconde fonction... et, du coup, maintenant, je la préfère!

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
;;; Pb: Chercher la première occurrence de "x"
;;;     dans un parcours DRG de l'arbre "l".
;;; Déf: "x" est une occurrence directe d'un arbre "l"
;;;      ssi "x" est égal à la partie gauche de "l"
;;; i.e. ssi "(eql x (car l))".
 
(defun f1 (x l)
  (if (not (consp l))
      ;; "l" n'a pas de partie gauche => pas d'occurrence
      ()
    ;; "l" est un bon arbre => on fait un parcours DRG
    (or
     ;; On cherche à droite
     (f1 x (cdr l))
     ;; Puis, si on n'a rien trouvé, on examine la racine.
     (if (eql x (car l))
         ;; La racine est solution car l'élément cherché est sa partie gauche
         l
       ;; Sinon on cherche à gauche
       (f1 x (car l))))))

Quant au prédicat, eql me semble le plus naturel (par défaut en tout cas); pourquoi exclure les nombres et les caractères en utilisant eq?
Une autre possibilité serait d'utiliser tree-equal. Cela me semble une bonne idée vu le contexte... On rechercherait alors un sous-arbre dans un arbre.
Une version plus évoluée de la fonction pourrait, comme member, prendre des keyword arguments pour modifier ce comportement.

D'accord.

En Le_Lisp (mon "principal" langage), on n'a que "eq" (même adresse) et "equal" (même contenu).

Et, en emacs-lisp (un de mes langages courants), "eql" permet effectivement d'inclure les flottants.

Et, en Common Lisp (un de mes anciens langages), on pourrait effectivement mettre des mots-clés à la "member".

Je ne vois rien dans les exemples de jahol qui indiquerait ce qu'il faudrait faire si c'est le sous-arbre droit qui est "égal" à l'élément recherché. Je m'attendais plutôt à ce qu'on retourne juste l'élément, dans ce cas.

Difficile à dire!

Personnellement et en ce qui me concerne, j'étais parti sur l'hypothèse décrite dans ma dernière fonction:

Code :

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

1
2
3
4
 
"x" est une occurrence directe d'un arbre "l"
ssi "x" est égal à la partie gauche de "l"
i.e. ssi "(eql x (car l))".

Voici donc mon second essai:

Code :

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

1
2
3
4
5
6
7
 
(defun f1 (x l)
  (if (eql x l)
      l
      (when (consp l)
	(or (f1 x (cdr l))
	    (when (f1 x (car l)) l)))))

Hmmm...

ELISP> (f1 'x '(a (x b) c d))
=> ((x b) c d)

J'attendrais plutôt (x b), non?

)jack(

[dividee]

Euh... dans mon jeune temps, on faisait de l'induction sur N (ensemble des entiers):

Code :

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

1
2
si (p(0) et pour tout n, p(n) => p(n+1))
alors  pour tout n, p(n)

Je croyais que ce n'était pas directement transposable sur un arbre, mais ta démonstration me semble suffisamment convaincante!

Ce n'est pas pour rien que la définition d'un arbre binaire, telle que celle que tu donnes, est appelée une définition inductive... Un principe d'induction est dérivable pour toute structure de donnée définie de cette manière; dès qu'on l'a compris, l'induction structurelle parait souvent plus simple et naturelle, lorsqu'elle est applicable, que l'induction sur N. J'ai appris cela grâce à l'assistant de preuve Coq et à ce cours.

Je suis bien sûr d'accord en ce qui concerne le parcours.

En Le_Lisp (mon "principal" langage), on n'a que "eq" (même adresse) et "equal" (même contenu).

Et, en emacs-lisp (un de mes langages courants), "eql" permet effectivement d'inclure les flottants.

Et, en Common Lisp (un de mes anciens langages), on pourrait effectivement mettre des mots-clés à la "member".

J'ai assumé (à tort) que (1) presque tout le monde utilisait Common Lisp, (2) les autres LISPs ne différeraient pas sur ces concepts de base.

Hmmm...

ELISP> (f1 'x '(a (x b) c d))
=> ((x b) c d)

J'attendrais plutôt (x b), non?

impardonnable

Pour essayer de la corriger, j'ai écrit ceci:

Code :

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

1
2
3
4
5
6
7
8
 
(defun f1 (x l)
  (if (atom l)
      (when (eql x l) l)
      (or (f1 x (cdr l))
	  (if (eql x (car l))
	      l
	      (f1 x (car l))))))

Elle est quasiment identique à la tienne, mais défini la notion d'"occurence" aussi sur la partie droite de l'arbre. Le problème, c'est qu'elle n'est pas aussi générale que la tienne. Tout va bien si on se limite à chercher des atomes, mais elle ne se comporte pas de façon très cohérente dans certains cas si l'élément recherché n'est pas atomique:

Code :

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

1
2
3
4
5
6
 
CL-USER> (f1 'b '(a . b))
B
CL-USER> (let ((x '(a b)))
	   (f1 x (cons 'a x)))
NIL

Il me semble que le problème n'est pas facile à résoudre; par conséquent, je m'incline et admet que ta solution est plus simple et plus générale.

Bien que relativement familier avec le paradigme fonctionnel, je suis plus habitué aux langages fortement typés, j'ai encore un peu de mal à raisonner en tenant compte du fait que, par exemple, '(a b c) puisse être au choix une liste, un arbre, une paire ou bien d'autres choses encore.

[jack-ft]

Ce n'est pas pour rien que la définition d'un arbre binaire, telle que celle que tu donnes, est appelée une définition inductive... Un principe d'induction est dérivable pour toute structure de donnée définie de cette manière; dès qu'on l'a compris, l'induction structurelle parait souvent plus simple et naturelle, lorsqu'elle est applicable, que l'induction sur N. J'ai appris cela grâce à l'assistant de preuve Coq et à ce cours.

Merci pour les références.
C'est intéressant, je regrette de na pas avoir suffisamment de temps pour m'y consacrer plus.

Je suis bien sûr d'accord en ce qui concerne le parcours.

J'ai assumé (à tort) que (1) presque tout le monde utilisait Common Lisp, (2) les autres LISPs ne différeraient pas sur ces concepts de base.

impardonnable

Pardonné ! Euh.... non... une erreur n'est pas une faute...

Il me semble que le problème n'est pas facile à résoudre; par conséquent, je m'incline et admet que ta solution est plus simple et plus générale.

Je n'aime pas trop le "je m'incline"...
Après tout, there is more than one way to do it!

En plus, vu la précision des specs...
J'imagine que tu connais le dessin de la balançoire...

Bien que relativement familier avec le paradigme fonctionnel, je suis plus habitué aux langages fortement typés, j'ai encore un peu de mal à raisonner en tenant compte du fait que, par exemple, '(a b c) puisse être au choix une liste, un arbre, une paire ou bien d'autres choses encore.

En fait, mon expérience de programmation (outre quelques passages par 68000, Fortran, Pascal, LOGO, Smalltalk, Prolog, Simone, C++, postscript, csh, ksh, awk, PL/SQL, Java...) a surtout été orientée objet dans un environnement lisp, avec, successivement:
- Le_Lisp (avec un embryon de noyau objet de mon crû)
- Le_Lisp (avec FORMES (dérivé de objVlisp))
- Le_Lisp (avec PreFORM (un noyau objet de mon crû))
- Common Lisp (avec CLOS (pour moi, la Rolls des langages objet))
et, en parallèle, emacs-lisp

Pourtant, dans ma tête, je suis assez fortement typé.

Et j'utilise, en lisp, une liste pour implémenter:
- une orderedCollection, avec comme méthodes: first rest endp
où tous les éléments sont des instances d'une classe donnée (ou d'une de ses sous-classes)
ou bien
- une a-list, avec comme méthodes: cassq...
(sauf si j'ai vraiment besoin d'une hashtable)
ou bien
- un arbre binaire, avec comme méthodes: car, cdr, null

Si j'ai besoin de stocker un groupe de données hétérogènes, je fais une classe (ou un struct, si besoin de légèreté) avec des champs, des accesseurs et des méthodes.

Voilà

)jack(

[jahol]

Merci de votre clairvoyance