IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Caml Discussion :

failwith pour fonction récursive


Sujet :

Caml

  1. #1
    Candidat au Club
    Profil pro
    Inscrit en
    décembre 2013
    Messages
    13
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : décembre 2013
    Messages : 13
    Points : 3
    Points
    3
    Par défaut 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 : 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.

  2. #2
    Membre éprouvé
    Profil pro
    Inscrit en
    mars 2010
    Messages
    309
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : mars 2010
    Messages : 309
    Points : 928
    Points
    928
    Par défaut
    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.

  3. #3
    Candidat au Club
    Profil pro
    Inscrit en
    décembre 2013
    Messages
    13
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : décembre 2013
    Messages : 13
    Points : 3
    Points
    3
    Par défaut
    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?

  4. #4
    Membre éprouvé
    Profil pro
    Inscrit en
    mars 2010
    Messages
    309
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : mars 2010
    Messages : 309
    Points : 928
    Points
    928
    Par défaut
    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?

  5. #5
    Candidat au Club
    Profil pro
    Inscrit en
    décembre 2013
    Messages
    13
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : décembre 2013
    Messages : 13
    Points : 3
    Points
    3
    Par défaut
    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>

  6. #6
    Candidat au Club
    Profil pro
    Inscrit en
    décembre 2013
    Messages
    13
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : décembre 2013
    Messages : 13
    Points : 3
    Points
    3
    Par défaut
    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 ;; ?

  7. #7
    Membre émérite
    Avatar de SpiceGuid
    Homme Profil pro
    Inscrit en
    juin 2007
    Messages
    1 701
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : juin 2007
    Messages : 1 701
    Points : 2 976
    Points
    2 976
    Par défaut
    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 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)
    Du même auteur: mon projet, le dernier article publié, le blog dvp et le jeu vidéo.
    Avant de poser une question je lis les règles du forum.

  8. #8
    Candidat au Club
    Profil pro
    Inscrit en
    décembre 2013
    Messages
    13
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : décembre 2013
    Messages : 13
    Points : 3
    Points
    3
    Par défaut
    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 ?

  9. #9
    Membre éprouvé
    Profil pro
    Inscrit en
    mars 2010
    Messages
    309
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : mars 2010
    Messages : 309
    Points : 928
    Points
    928
    Par défaut
    Citation Envoyé par PST25 Voir le message
    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.

  10. #10
    Candidat au Club
    Profil pro
    Inscrit en
    décembre 2013
    Messages
    13
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : décembre 2013
    Messages : 13
    Points : 3
    Points
    3
    Par défaut
    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;;

  11. #11
    Membre éprouvé
    Profil pro
    Inscrit en
    mars 2010
    Messages
    309
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : mars 2010
    Messages : 309
    Points : 928
    Points
    928
    Par défaut
    Ton type symbole, ce ne serait pas tout simplement le type char?

  12. #12
    Candidat au Club
    Profil pro
    Inscrit en
    décembre 2013
    Messages
    13
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : décembre 2013
    Messages : 13
    Points : 3
    Points
    3
    Par défaut
    (Désolé pour le retard) Mais alors du coup je devrais écrire Sym of char alors?

  13. #13
    Membre éprouvé
    Profil pro
    Inscrit en
    mars 2010
    Messages
    309
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : mars 2010
    Messages : 309
    Points : 928
    Points
    928
    Par défaut
    Bah ouais (si ce sont bien des caractères)

  14. #14
    Candidat au Club
    Profil pro
    Inscrit en
    décembre 2013
    Messages
    13
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : décembre 2013
    Messages : 13
    Points : 3
    Points
    3
    Par défaut
    D'accord merci beaucoup!!!

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 1
    Dernier message: 15/07/2008, 23h59
  2. [MySQL] Fonction récursive pour affichage arborescence
    Par Mister Paul dans le forum PHP & Base de données
    Réponses: 11
    Dernier message: 01/12/2007, 19h30
  3. Réponses: 6
    Dernier message: 12/04/2007, 20h30
  4. Réponses: 10
    Dernier message: 03/07/2006, 11h32
  5. Fonctions récursives pour parcourir un arbre
    Par mikedavem dans le forum C
    Réponses: 4
    Dernier message: 05/06/2006, 12h00

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo