[Caml] Arbre de listes

[Rockleader]

Bonjour,

je cherche à comprendre comment construire des arbres en caml d'un type donné. Pour commencer un arbre qui contiendrait des String par exemple. Par la suite je voudrais une fois la construction d'arbre comprise essayer de faire un arbre sur un type liste de String.

J'ai fais pas mal de recherche, mais je ne trouve pas une façon simple de comprendre !!!

[Monsieur23]

Aloha,

Tu as regardé du côté des types polymorphes ? Un truc dans le genre devrait fonctionner pour des arbres binaires

type 'a bin_tree = Nil | Node of ('a bin_tree)*'a*('a bin_tree)

[Rockleader]

Aloha,

Tu as regardé du côté des types polymorphes ? Un truc dans le genre devrait fonctionner pour des arbres binaires

type 'a bin_tree = Nil | Node of ('a bin_tree)*'a*('a bin_tree)

Je ne connaissais pas l'instruction type pour définit un type, maintenant que je n'ai tout va mieux !


Par contre j'ai quelque soucis

J'ai fais un type personne = int * String

Ainsi qu'une fonction qui prend un couple de valeur et me renvoi la première, le numéro me servira en fait à construire mon arbre.


J'ai testé par exemple si je fais p1=(1,"toto);; et que j'appelle numPersonne p1 ==> cela me renvoit bien la valeur 1.


En revanche mon typé déclaré fait des caprices.


Si je fais personne p1=(1,"toto");;

p1 n'est pas connu. ou plutôt mon p1 est considéré comme un couple int*string sans valeur. C'est assez bizarre je dois dire...

[Monsieur23]

Je comprends pas bien l'erreur que tu as… tu peux expliquer un peu plus ?

[Rockleader]

Je viens d'avoir le cours sur la définition des types, donc je pense que je vais le travailler un peu puis si je bloque toujours je vous referais signe ;)

Merci beaucoup pour le coup de main en tout cas^^

[Rockleader]

Voici une séquence ocaml

Code: Tout sélectionner

 type pers = int*char;;
type pers = int * char

let p1=(3,'n');;
val p1 : int * char = (3, 'n')

Je déclare un type pers comme étant un couple de int,char

Ensuite je déclare une variable étant un couple de int,char. Mais lorsque caml l'évalue, il se contente de int*char. Pourquoi ne remplace il pas par pers ?

[Monsieur23]

C'est ce genre de trucs que tu veux : http://fr.wikibooks.org/wiki/OCaml/Structures#Contraintes_de_types ?

[Rockleader]

J'ai pu avancer dans mes problèmes, grace aux cours je comprends mieux à présent^^


Mais j'avais une petite remarque anodine, pour représenter ces arbres généalogique, j'ai choisi une structure d'arbre binaire.

AU final la feuille de mon arbre c'est une personne
et les noeud sont défini par le type de l'arbre * une personne * type de l'arbre




C'est un formalisme qui correspond aux données de mon projet; mais je me suis posé la question la réutilisation du code, et jme suis rendu compte que c'était fumeux quand même.


S'il est vrai qu'on peut dire qu'une personne a forcement un père (fils gauche) et une mère (fils droit); il n'est pas possible de modéliser avec l'arbre binaire le fait qu'un père et une mère possède plus d'un enfant.

[joel76]

Dans le premier cas, tu modélise les parents d'une personne, c'est un arbre, dans le deuxième cas, tu modélises les descendants de deux personnes, ça devient un graphe, ce n'est effectivement pas la même chose (quoique on peut dire qu'un arbre est un graphe particulier, je pense).