Discussion :

[PST25]

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 :

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

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.

[TropMDR]

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.

[PST25]

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?

[TropMDR]

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

Code :

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

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 :

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

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?

[PST25]

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

Code :

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

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>

[PST25]

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 ;; ?

[SpiceGuid]

Tu nous dis :

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

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

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)

[PST25]

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 ?

[TropMDR]

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.

[PST25]

Code :

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

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

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

Code :

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

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

[TropMDR]

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

[PST25]

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

[TropMDR]

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

[PST25]

D'accord merci beaucoup!!!