failwith pour fonction récursive

Bonjour à tous,
Je suis débutante en programmation et je pense avoir mal assimilé l'utilisation du failwith dans une fonction récursive.
On utilise ici les arbres binaires:

type 'a arbre = F | N of 'a * 'a arbre * 'a arbre où la construction N(x,g,d) représente un arbre dont la racine est étiquetée par x et qui a comme fils gauche g (d pour droit); les feuilles F ne sont pas étiquetées. Toutes les étiquettes dans le fils g sont strictement inf à x et toutes les étiquettes dans le fils d sont strictement sup à x

max_abr : 'a arbre -> 'a prend un arbre binaire en argument t et renvoie le plus grand élément de t. Je cherche donc à lancer une exception si l'arbre entier est F

Code:

---

1 2 3

let rec max_abr a = match a with |F -> 0 |N(x,g,d) -> max x (max_abr d);;

---

je ne sais pas où mettre le failwith puisque si je mets après le F il me renverra l'exception quelque soit l'arbre en argument?
Pourriez-vous me donner un petit indice svp?
Merci d'avance.

Quand tu definies une fonction recursive, tu as principalement deux questions a te poser: Quel est ma condition d'arret, et qu'est ce que je fais dans le cas de recurence. Oublie une minute le cas ou tout l'arbre est une feuille, et demande toi quelle est ta condition d'arret, pour retourner le plus grand element de l'arbre.

On s'arrête des que l'on trouve un F pour calculer le Max avant de le renvoyer. C'est pas ça le critère d'arrêt ici?

Ce n'est pas assez precis comme reponse! Regarde bien le type de la fonction max_abr:

Code:

---

max_abr: 'a arbre -> 'a

---

Tu dois donc etre capable de retourner un 'a, quelque soit 'a (int, float, string, un type qui decrit une date, n'importe quoi). Et maintenant regarde le type 'a arbre

Code:

---

1 2 3

type 'a arbre = | F | N of 'a * 'a arbre * 'a arbre

---

Quand tu es dans le cas F, tu n'a pas de 'a! (D'ailleurs, si tu regardes ta solution, quelle est son type? Est ce que c'est bien 'a arbre -> 'a?)

Donc ce n'est pas quand tu arrives a F que tu peux retourner un 'a. Quand est ce que tu peux?

Bon alors j'espère que j'ai trouvé

Code:

---

1 2 3 4 5 6

let rec max_abr t = match t with |F -> failwith "no max" |N(x,g,F) -> x |N(x,g,d) -> max x (max_abr d);;   val max_abr : 'a arbre -> 'a = <fun>

---

Sinon j'avais une toute petite question à propos des types:
Est-il possible de déclarer des types de char pour représenter par exemple Node (Node (Sym('A'), Sym('B') ) )
L'interpréteur n'a pas l'air d'accepter type symbole = |'A' |'B' |'C' |'D' ;;
N'y a t-il donc pas de solution mis à part écrire ceci type symbole = |A |B |C |D ;; ?

Tu nous dis :

Citation:

---

Envoyé par PST25

toutes les étiquettes dans le fils d sont strictement sup à x

---

Du coup tu peux simplifier ta dernière ligne de code (tu n'as pas besoin de max) :

Code:

---

1 2 3 4

let rec max_abr t = match t with |F -> failwith "no max" |N(x,g,F) -> x |N(x,g,d) -> max x (max_abr d)

---

Ah oui, donc du coup je mets directement max_abr d pour la dernière ligne. Merci beaucoup ! Et à propos des types, auriez-vous une réponse à me proposer ?

Citation:

---

Envoyé par PST25

Et à propos des types, auriez-vous une réponse à me proposer ?

---

Tu peux nous decrire ton probleme avec plus de detail? Par exemple avec la definition du type qui contient les constructeurs Node et Sym.

Code:

---

type symbole= |'A' |'B' |'C' |'D' ;;

---

Ça c'est ce que je voudrais faire seulement ça ne marche pas à cause des apostrophes

Code:

---

1 2	type arbre_huffman = |Sym of symbole |Node of arbre_huffman * arbre_huffman;;

---

Ton type symbole, ce ne serait pas tout simplement le type char?

(Désolé pour le retard) Mais alors du coup je devrais écrire Sym of char alors?

Bah ouais (si ce sont bien des caractères)

D'accord merci beaucoup!!!