Discussion :

[shirohige]

Bonjour,

Je suis nouveau en lisp et j'aime pas du tout la récursivité.

J'essaye de faire une fonction qui me retourne le nombre le plus grand dans une liste.

Voici mon code.

Code :

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

1
2
3
4
5
6
 
(defun max (list) ;creation de la fonction max
(if (null list) ;si ma liste est vide je retoune null
null)
(if (> (setq res (max (cdr list))) (car list))
res))  ;je recupère la valeur que me renvoie max et la compare avec la valeur actuel "car" de ma liste si elle est plus grande je retourne cette valeur. J'essaye de stocker cette valeur dans res avec setq, je ne sais pas si c'est possible.

Il y a peut etre des choses qui sont incohérentes dans mon code, je ne suis pas familier avec la syntaxe.

Edit: j'ai modifier mon code mais j'ai un stack overflow^^:

Code :

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

1
2
3
4
5
6
7
8
9
 
(defun maxe (list)
(if (null list)
nil)
(setq res (maxe (cdr list)))
(if (nil res)
(car list)
(if (> res (car list))
res)))

Mon problème viens du setq res....
Je pensais que mettre le nil signifiait (return null) en C par exemple. Mais au lieu de s'arreter le programme continue.

Edit 2:

Ca marchotte mais le problème c'est que lorsque j'arrive à la fin de la liste je voudrais retourné autre chose qu'un nombre pour dire que c'est la fin, sinon si dans la liste il y a le nombre ça arrêtera la récursivité trop tot:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
(defun maxe (list)
(if (null list)
(return-from maxe 1))
(princ (car list))
(setq res (maxe (cdr list)))
(if (= res 1)
(car list))
(if (> res (car list))
res
(car list)))

J'ai essayé nil mais comme ma fonction retourne des nombres ça marche pas.

[jack-ft]

Bonjour!

Bien qu'ayant lu (ou écrit) des dizaines de milliers de lignes de lisp, j'avoue avoir beaucoup de mal à lire ton code (et j'imagine que ce doit être pareil pour pas mal de lecteurs potentiels (si tant est qu'il y en ait)) car ton code manque cruellement d'indentation!
Pourrais-tu éditer ton post pour en indenter le code?
(Remarque: avec emacs (la rolls pour éditer du lisp), tu te places sur la parenthèse ouvrante de la fonction et tu tapes C-M-q)

Pourrais-tu également jeter un coup d’œil aux 4 dernières conversations dans lesquelles j'ai décrit des algorithmes récursifs et t'en inspirer pour en proposer un pour ta fonction?
(ensuite, on verra les problèmes de syntaxe...)

Sinon, si tu veux vraiment continuer directement en lisp, essaie de l'écrire sans aucun setq.

Code :

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

1
2
3
4
5
6
7
8
9
 
(defun maxe (list)
(if (null list)
nil)
(setq res (maxe (cdr list)))
(if (nil res)
(car list)
(if (> res (car list))
res)))

Mon problème viens du setq res....
Je pensais que mettre le nil signifiait (return null) en C par exemple. Mais au lieu de s'arreter le programme continue.

Si ton code était indenté, tu verrais que le premier if est suivi d'autres instructions (le setq...), donc c'est normal qu'il ne s'arrête pas après l'avoir exécutée.
Si tu supprimes la parenthèse après le premier nil (3ème ligne), alors la fonction s'arrêtera bien si l'argument list est nil.

Ca marchotte mais le problème c'est que lorsque j'arrive à la fin de la liste je voudrais retourné autre chose qu'un nombre pour dire que c'est la fin,

What???

Dire que c'est la fin???

Ça marche pas comme ça!

La seule question importante est: "que doit retourner la fonction?"
Avec comme sous-questions: "lorsque telle ou telle condition est réalisée, que doit retourner la fonction?"

ce qui aide considérablement à écrire l'algorithme... puis le code

[shirohige]

Merci pour ta réponse.

Se que je voulais dire c'est que ma fonction doit retourner un nombre, un int. Mais lorsque j'arrive à la fin de ma liste, et que je suis sur l'élément null, je voudrais retourner un nombre me disant "ok la c'est l'élément null de la liste". Je ne peut pas retourner un nombre genre -1 ou -564889 car si la personne veut tester avec le nombre définit comme représentant de l'élément null mon programme s’arrêtera. Un exemple (mixe entre c et lisp lol):

Code :

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

1
2
3
 
if ((car list) == null)
   return -1; //-1 pour indiquer que c'est la fin de la liste

Si la personne envoie cette liste de nombre: ( 1 2 3 8 7 -1 9 7 8).
Lorsqu'elle va rencontrer le -1 elle va s’arrêter et pas tester 9 7 8.

Je pense avoir la solution, il suffit de mettre, peut être lol:

Code :

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

1
2
if (cdr list == null)
    return car list;

Mais je suis pas sur de ma comparaison, si on peut comparer tout une liste à null. J'essaye et j'édite si ça marche.

PS: Je code sous bloc-note lol, je me perd dans les '(' mais comme mon code n'est pas très long, je réussi à mi retrouver généralement.

Edit: Ça marche \o/. Mais j'ai une question. J'avais essayé de mettre if (= list nil). Mais ça marchais pas. Je voudrais savoir la différence entre if (null list) et if (= list nil), dans quel cas utiliser l'un plutôt que l'autre. Et pourquoi pas la différence avec if (= null list) aussi, merci.

[Jedai]

Je propose d'écrire une autre fonction, qui prend en paramètre un nombre et une liste et retourne le maximum parmi les éléments de la liste et le nombre fourni. C'est très facile récursivement et parfait pour résoudre le problème d'origine proprement

Code :

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

1
2
3
4
5
6
(defun maxDef (def list)
  (if (null list) 
      ... 
      ...
  )
)

Et ensuite tu peux écrire :

Code :

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

1
2
3
4
5
6
(defun maxList (list)
  (if (null list) 
      nil 
      (maxDef ...)
  )
)

Je rappelle que (max n m) renvoie le maximum entre n et m.

--
Jedaï

[jack-ft]

Se que je voulais dire c'est que ma fonction doit retourner un nombre, un int. Mais lorsque j'arrive à la fin de ma liste, et que je suis sur l'élément null, je voudrais retourner un nombre me disant "ok la c'est l'élément null de la liste". Je ne peut pas retourner un nombre genre -1 ou -564889 car si la personne veut tester avec le nombre définit comme représentant de l'élément null mon programme s’arrêtera. Un exemple (mixe entre c et lisp lol):

Je crois qu'il faut absolument changer de manière de penser!
Le mixte entre C et lisp, ça va pas le faire!

Si tu programmais en shell, tu pourrais écrire des fonctions qui utilisent 2 canaux pour communiquer avec l'appelant:
- le status retourné qui permet de dire si ça s'est bien passé ou non
- la stdout (sortie standard) où tu récupères le résultat lorsque ça s'est bien passé.

En C ou en Lisp, on ne peut pas (simplement) utiliser ce mode de fonctionnement.

Ici (et, de manière plus générale, en programmation fonctionnelle), une fonction, pour une entrée donnée, retourne un résultat ou lève une exception.

Code :

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

1
2
if ((car list) == null)
   return -1; //-1 pour indiquer que c'est la fin de la liste

Ceci n'est pas une spécification (amha)!

Si la personne envoie cette liste de nombre: ( 1 2 3 8 7 -1 9 7 8).
Lorsqu'elle va rencontrer le -1 elle va s’arrêter et pas tester 9 7 8.

Encore plus grave: si tu passes la liste '(-5 -6), la fonction risque de retourner -1 !

Je pense avoir la solution, il suffit de mettre, peut être lol:

Code :

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

1
2
if (cdr list == null)
    return car list;

Quelque chose comme ça!
Je regrette que tu n'aies pas essayé de donner l'algorithme...

Mais je suis pas sur de ma comparaison, si on peut comparer tout une liste à null.

Lorsque je lis cette phrase, j'ai l'impression que tu n'as pas les idées très claires sur ce qu'est une liste!?

En lisp (ou dans plein d'autres langages (notamment java)), ce qu'on appelle généralement une liste n'est qu'un pointeur vers une zone mémoire, qui peut être soit l'adresse de la valeur particulière NIL, soit l'adresse d'un CONS.

Pour savoir si une liste est "vide", on compare son adresse avec celle de NIL. Si c'est la même adresse, on dit que la liste est vide.

J'essaye et j'édite si ça marche.

PS: Je code sous bloc-note lol, je me perd dans les '(' mais comme mon code n'est pas très long, je réussi à mi retrouver généralement.

Je te conseille d'installer emacs (pour Windows) ou, à défaut, NotePad++

Edit: Ça marche \o/.

Toujours pas d'algorithme? Ou, à défaut, de code?

Mais j'ai une question. J'avais essayé de mettre if (= list nil). Mais ça marchais pas. Je voudrais savoir la différence entre if (null list) et if (= list nil), dans quel cas utiliser l'un plutôt que l'autre.

La fonction "=" compare des nombres, pas des "objets" (ou des adresses). Cf. http://www.lispworks.com/documentati...y/f_eq_sle.htm

La comparaison d'objets est faite avec la fonction "eq". Cf. http://www.lispworks.com/documentati.../Body/f_eq.htm

Pour tester si une liste "l" est vide, on peut donc écrire (eq l nil) ou (eq l ()), mais, comme c'est un test qui revient tellement souvent, il a été créé une fonction spécifique "null". Ainsi (null l) retourne vrai si "l" est "vide" (est la liste vide, est égale à "nil" ou "()"). Mais certains lisps ont aussi une fonction "not" et une fonction "endp" qui donnent les mêmes résultats, mais améliorent la clarté du code. Ainsi:
(not flag) teste si un "booléen" est "faux",
(endp l) teste si une liste "l" est "vide",
(null x) teste si un "objet" x est "nil".

Et pourquoi pas la différence avec if (= null list) aussi, merci.

Si tu mets if (eq nil list), ça marche!

[shirohige]

Voila mon code:

Code :

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

1
2
3
4
5
6
7
8
 
(defun maxe (list)
(if (null (cdr list))
(return-from maxe (car list)))
(setq res (maxe (cdr list)))
(if (> res (car list))
res
(car list)))

Ca marche, mais j'ai aussi codé la fonction qui trouve le minimum dans une liste, j'essaye de les afficher dans une même fonction mais ça ne marche pas:

Code :

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

1
2
3
4
 
(defun minandmax (list)
(mine (list))
(maxe (list)))

Merci de votre aide.

[Bruno-Vdh]

Bonjour,

Personnellement pour éviter l'emploie d'un setq, j'aurais introduit un 2ème argument à la fonction afin de stocker la plus grande valeur rencontré dans le parcours de la liste.

Ma proposition :

Code :

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

1
2
3
4
5
6
(defun maxi (l n)
  (cond ((null l) n)
        ((< n (car l)) (maxi (cdr l) (car l)))
        (T (maxi (cdr l) n))
  )
)

Ou bien comme cela :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
(defun maxi (l n)
  (if (null l)
    n
    (maxi (cdr l)
          (if (< n (car l))
            (car l)
            n
          )
    )
  )
)

Dans le dialecte Lisp que j’utilise la comparaison (< nil nombre) retourne toujours T, cela permet l’appel de la fonction de la façon suivante :

Code :

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

1
2
_$ (maxi '( 8 12 5 -6 25 3) nil)
25

De ce que j’ai pu lire, il me semble qu’il est possible en Common Lisp de rendre ce second argument optionnel, et même d’appeler la fonction dans une autre fonction pour passer d’une fonction acceptant une liste de nombres, à une fonction acceptant un nombre indéterminé d’argument comme la fonction originel max =>(max nbr1 nbr2 … ). A confirmer bien sur part un adepte de Common Lisp..

A+
(Ps: Pour l’affichage des valeurs minimum et maximum, il suffit de retourner une liste de résultat)

[jack-ft]

Voici ton code indenté:

Code :

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

1
2
3
4
5
6
7
(defun maxe (list)
  (if (null (cdr list))
      (return-from maxe (car list)))
  (setq res (maxe (cdr list)))
  (if (> res (car list))
      res
    (car list)))

Le lisp ne nécessite presque jamais l'usage de return-from.
Si tu avais suivi mon conseil dans le post #3:

Si tu supprimes la parenthèse après le premier nil (3ème ligne), alors la fonction s'arrêtera bien si l'argument list est nil.

tu aurais alors pu simplifier ta fonction en:

Code :

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

1
2
3
4
5
6
7
(defun maxe (list)
  (if (null (cdr list))
      (car list)
    (setq res (maxe (cdr list)))
    (if (> res (car list))
        res
      (car list))))

De plus, on évite généralement d'utiliser des variables globales comme "res".
Il suffit de la déclarer comme locale et on obtient:

Code :

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

1
2
3
4
5
6
7
(defun maxe (list)
  (if (null (cdr list))
      (car list)
    (let ((res (maxe (cdr list))))
      (if (> res (car list))
          res
        (car list)))))

Ca marche, mais j'ai aussi codé la fonction qui trouve le minimum dans une liste, j'essaye de les afficher dans une même fonction mais ça ne marche pas:

Tu essaies de les afficher ou de les retourner?

Si tu veux les afficher:

Code :

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

1
2
3
(defun minandmax (list)
  (print (mine (list)))
  (print (maxe (list))))

Si tu veux "les" retourner, il faut dire précisément quel résultat tu attends (une liste de 2 nombres (comme proposé par Bruno-Vdh), une paire pointée, un vecteur, une chaîne, un objet, etc.).