Fonction récursive trouver le max dans une liste.

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:

---

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:

---

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:

---

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.

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.

Citation:

---

Envoyé par shirohige

Code:

---

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.

Citation:

---

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

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:

---

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:

---

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.

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:

---

1 2 3 4 5 6

(defun maxDef (def list) (if (null list) ... ... ) )

---

Et ensuite tu peux écrire :

Code:

---

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ï

Citation:

---

Envoyé par shirohige

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.

Citation:

---

Code:

---

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

Citation:

---

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 !

Citation:

---

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

Code:

---

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

Citation:

---

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.

Citation:

---

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

Citation:

---

Edit: Ça marche \o/.

---

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

Citation:

---

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

Citation:

---

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

---

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

Voila mon code:

Code:

---

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:

---

1 2 3 4

(defun minandmax (list) (mine (list)) (maxe (list)))

---

Merci de votre aide.

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:

---

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:

---

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:

---

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)

Voici ton code indenté:

Code:

---

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:

Citation:

---

Envoyé par jack-ft

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:

---

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:

---

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

---

Citation:

---

Envoyé par shirohige

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:

---

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

Hello, je pense aussi qu'une deuxième variable pour tenir la valeur maximale est plus pratique.
Je ferais avec deux fonctions:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

(defun maxim (l) (if (null l) nil (maximum l (nth 0 l))))   (defun maximum (l m) (if (eq l nil) m (if (> (first l) m) (maximum (rest l) (first l)) (maximum (rest l) m))))

---

Ça marche aussi!
En scheme, on utiliserait une fonction locale.
L'inconvénient en CL, c'est de créer une nouvelle fonction globale, mais bon...
On peut très très légèrement améliorer ta fonction de cette manière:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

(defun maxim (l) (if (endp l) nil (maximum (rest l) (first l))))   (defun maximum (l m) (if (endp l) m (maximum (rest l) (if (> (first l) m) (first l) m))))

---

On évite le test du (first l) de maxim avec lui-même (en passant à maximum (rest l) plutôt que l)!
on voit mieux la simple récursivité (un seul appel de maximum dans maximum)!

Merci, c'est vrai que c'est bcp mieux!

> L'inconvénient en CL, c'est de créer une nouvelle fonction globale, mais bon...

Ce n'est pas indispensable, car on peut créer une fonction locale avec LABELS. Quand même, dans ce cas elle ne va pas être une clôture, alors on peut utiliser aussi bien une fonction globale et ne pas l'exporter du paquet. En tout cas, en CL ce n'est pas habituelle d'employer recursion dans des problèmes de ce type.

Bonjour,

Citation:

---

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.

---

J'essayerais ça quand ça marchera, ça sera plus simple c'est vrai.

J'ai essayé:

Code:

---

1 2 3 4

(defun minandmax (list) (print (mine (list))) (print (maxe (list))))

---

Mais j'ai comme résultat:
NIL
NIL
NIL

EDIT: J'ai essayer de suprimer la '(' à la 3 eme ligne et donc de la rajouter à la fin mais ça m'a mis:
EVAL: too many parameters for special operator IF:
(IF (NULL (CDR LIST)) (CAR LIST) (SETQ RES (MAXE (CDR LIST)))
(IF (> RES (CAR LIST)) RES (CAR LIST)))

Citation:

---

Envoyé par shirohige

J'ai essayé:

Code:

---

1 2 3 4

(defun minandmax (list) (print (mine (list))) (print (maxe (list))))

---

---

Il existe une fonction qui s'appelle "list", qui construit et retourne une liste avec ses arguments.
Il n'est pas recommandé (un peu long d'entrer dans les détails) d'utiliser une variable qui a le même nom qu'une fonction.
Essaie de remplacer "list" par "lst" ou "l", pour voir ce que ça donne.

Citation:

---

J'ai essayer de suprimer la '(' à la 3 eme ligne et donc de la rajouter à la fin mais ça m'a mis:
EVAL: too many parameters for special operator IF:
(IF (NULL (CDR LIST)) (CAR LIST) (SETQ RES (MAXE (CDR LIST)))
(IF (> RES (CAR LIST)) RES (CAR LIST)))

---

[EDIT]ATTENTION! J'ai tout mélangé! :oops:
(Honte à moi de n'avoir pas vérifié! :marteau:
et merci à byjav de m'avoir corrigé! :applo:)

En Le_lisp et en emacs-lisp, le "if" a un "progn" implicite.
En Common Lisp et en Scheme, le "if" n'a pas de "progn" implicite.

PS: j'ai programmé en CL pendant ~ 5 ans (il y a 15 ans), en Le_lisp pendant ~20 ans et en emacs-lisp depuis ~30 ans (ceci explique peut-être cela!)

Hummm... Le dialecte de lisp que utilises n'est sûrement pas Common Lisp où l'on peut écrire:

Code:

---

(if <test> <then-expr> <else-expr1> ... <else-exprN>)

---

On appelle cette succession de <else-expr> un progn implicite (accepté par le "if" de CL d'emacs lisp, de Le_lisp et d'autres dialectes de lisp).

[/EDIT]

Comme le "if" de ton dialecte n'accepte pas les progn implicites (too many parameters), il faut donc utiliser un "progn" explicite:

Code:

---

(if <test> <then-expr> (progn <else-expr1> ... <else-exprN>))

---

Rq: on peut également utiliser "cond" où, normalement, chaque clause contient un test et un progn implicite.

Mais la meilleure solution est d'utiliser un "let", comme je l'ai proposé précédemment (lequel fait aussi un progn implicite).

Cette histoire de "progn" implicite est un peu dérangeante pour ceux qui ont appris un autre langage de programmation, comme C.
En C, on utilise des successions d'instructions qui sont autant de progn implicites.
Dans un langage fonctionnel comme lisp, il n'y a que des fonctions. Du coup, on peut avoir besoin d'une fonction pour décrire une "successions d'instructions". Cette fonction est "progn".

"progn" est une fonction (pour faire simple) qui évalue chacun de ses arguments et retourne la valeur retournée par le dernier argument.
(Rq: Elle n'a de sens que si les arguments avant le dernier font des "effets de bord", comme "setq". C'est une sorte d'entorse à la programmation purement fonctionnelle.)

Et, histoire de simplifier les choses, "defun", qui est l'une des premières fonctions que l'on apprend, fait justement un progn implicite. On peut remplacer:

Code:

---

(defun foo (x) (progn (print "x vaut:") (print x))) ; progn explicite

---

par

Code:

---

(defun foo (x) (print "x vaut:") (print x)) ; progn implicite (succession d'instructions (faisant des effets de bord))

---

Citation:

---

Envoyé par shirohige

J'ai essayé: ... Mais j'ai comme résultat:
NIL
NIL
NIL

---

Il semble que les fonctions mine et maxe ne marchent pas, il faudrait les tester. Quelles sont tes définitions ? Il y en a plusieures pour maxe en aucune pour mine. :)

A propos, c'est la raison de programmer avec le REPL: on peut tester ce qu'on écrit en même temps qu'on l'écrit. C'est une métode bien differente de plusieurs autres langages compilés, mais elle est devenue assez habutuelle chez des langages interprétés tels que Python. C'est pourquoi on ne code en Lisp sous block-note, mais sous des éditeurs intelligents, voire aussi chez Norvig: http://norvig.com/luv-slides.ps

En plus, quant on utilise le REPL, on n'a pas tentation d'écrire de fonctions d'affichage superflues, car le REPL affiche ce qu'on veut voire. Il suffit d'écrire les fonctions qui font le travail, c'est-à-dire calculent.

Quant'à IF, en Common Lisp il n'a pas de progn implicite.

> 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 effet, en Common Lisp il y a une solution pareille qui est simple, pratique et usitée, c'est de retourner deux valeurs. Mais dans ce cas particulier c'est difficil à dire quelle soit la valeur principale dans le cas d'une liste vide. A mon goût, il suffirait de renvoyer NIL au lieu de -1 proposé si la liste est vide.

J'ai essayé de changer list par lst puis l mais j'ai ce message:

Code:

---

1 2 3 4

(defun minandmax (l) (print (mine (l))) (print (maxe (l))))

---

Eval: Undefined function L.

J'ai essayé avec progn et ça marche :) :

Code:

---

1 2 3 4 5 6 7 8

(defun maxe (l) (if (null (cdr l)) (car l) (progn (setq res (maxe (cdr l))) (if (> res (car l)) res (car l)))))

---

D'autre par j'essaye de coder une fonction qui s'arrete lorsque l'utilisateur frappe 0:

Code:

---

1 2 3 4 5 6 7 8

(defun Stopzero (list) (setq res(read)) (if (= res 0) list (progn (cons list res) (princ list) (Stopzero (list)))))

---

Mais lorsque que je demande d'afficher la list, il affiche NIL, j'ai essayer avec append mais ça marche pas, peut etre par ce que res n'est pas une liste.

Lors de l'appel je fait:
(stopzero '(1))
ou
(stopzero nil)
Mais sans succé.
Ce que ça me fait, c'est que ça me marque NIL a chaque fois, ça s'arrete bien au zero (merci progn).

Edit: J'ai essayé en mettant lst comme nom mais j'ai le même problème que dans l'exemple d'avant:

Eval: Undefined function L.

Peut être que list appelait la dite fonction, c'est pour cela que j'avais NIL.
Merci.

Pour appliquer une fonction F aux arguments X1, ..., Xn, on écrit (f x1 ... xn); si la fonction n'exige pas d'arguments, on écrit conformément (f). Alors, (l) c'est l'invocation d'une fonction L qui est indéfinie. Pour appliquer la fonction MAXE a la variable L il faut écrire (maxe l)

Quant à stopzero, il y a deux erreurs. La fonction CONS ne modifie pas la valeur de ses arguments (en effet, aucune fonction ne peut les modifier), pour cette raison l'opération (cons list res) est tout à fait inutile, car elle calcule une valeur que est tout de suite rejetée. Voici une version qui marche :

Code:

---

1 2 3 4 5 6 7

(defun stop-zero (list) (let ((res (read))) (if (zerop res) list (progn (push res list) (princ list) (stop-zero list)))))

---

N'oublie pas déclarer les variables avant de les utiliser ! Le plus souvent ça ce fait à l'aide de LET.

D'ailleurs, c'est un mauvais Lisp.

Citation:

---

Envoyé par shirohige

J'ai essayé de changer list par lst puis l mais j'ai ce message:

Code:

---

1 2 3 4

(defun minandmax (l) (print (mine (l))) (print (maxe (l))))

---

Eval: Undefined function L.

---

Ben oui! C'est ce que j'attendais!
Et j'espérais que ça te mettrait la puce à l'oreille!
byjav t'a donné la solution.
Rq: pour prendre le "car" de "lst", tu écris bien (car lst) et non (car (lst)), non?

Sinon, il risque de te dire "Eval: Undefined function LST."...

C'est pas grave! C'est juste de la syntaxe! (<fun> <arg1> ... <argn>), c'est tout ce qu'il faut savoir...