Partage

[Caml] Probleme de type

Sujet résolu

Sateth

2 décembre 2005 à 15:49:55

Salut c'est encore moi avec un nouveau probleme avec mon petit chéri ... Caml !

J'introduit le type Ville ::

type Ville = { nom:string ; villes_reliees:string list };;

let Paris = ( nom = "paris" ; villes_reliees = [ "marseille" ; "lyon" ; "nantes" ] );;

et la il me dit qu'il connait pas nom ?? je comprends plus j'ai mal introduit paris ?

>let Paris = (nom = "paris" , villes_reliees = [ "marseille" ; "lyon" ; "nantes" ]);;
> ^^^
The value identifier nom is unbound.

Merci de m'aider a combler mon ignorance

Sky

2 décembre 2005 à 16:50:39

let Paris = { nom = "paris" ; villes_reliees = [ "marseille" ; "lyon" ; "nantes" ] };;

Je crois que c'est comme ça

Sateth

2 décembre 2005 à 17:12:11

Merci, je note mal les cours :/

EDIT :

Sinon j'ai un autre probleme :

voila jai le nom de la ville mais je voudrait ses villes reliées donc je pensais faire :

let listeVillesAccessibles (v) = match v with n.nom -> n.villes_reliees;;

Mais ca ne marche pas :

>let listeVillesAccessibles (v) = match v with n.nom -> n.villes_reliees;;
> ^
Syntax error.

Si vous pouvez m'aider

Merci encore

bluestorm

2 décembre 2005 à 20:02:12

Et bien ton n, il sort d'où ?

C'est quoi le typde de v : c'est une ville ou le nom d'une ville ?

D'autre part, tu sais que les parenthèses autour des arguments d'une fonction sont inutiles (pas la première fois que je le dit)

let fonction v =
let fonction(v) =

C'est pareil, et c'est quand meme plus lisible.

Enfin, tu sais que les guidelines ocaml recommandent de noter les mots en les séparant par des underscore ?
let listeVillesAcessibles v =
let liste_villes_accessibles v =

c'est plus lisible et plus logique : il est anormal de mettre des majuscules à tous les mots sauf au premier.

Sateth

3 décembre 2005 à 12:09:58

Je voudrait bien noter comme ca d'ailleur pour les fonctions auxilliaires que j'invente moi même elles sont comme ca (avec des _ ) Mais c'est mon prof. IL n'accepte pas les autres écritures. SI je fais pas ca je suis sur d'avoir au moins 4 a 5 points en moins ....

Pour ce qui est de v :

Le type de v je pensais que Caml pouvait le retrouver logiquement :

match v with n.nom

Ce qui veut dire que v est donc un nom et n une Ville. Moi ca me parait logique
Je me suis dit qu'il allait chercher la ville correspondante et me sortir sa liste des villes reliées ... C'est assez simple mais logique non ?

bluestorm

3 décembre 2005 à 13:50:25

Hum, je demandais le type pour moi, parce que je ne sais pas ce que c'est.

De plus, ce que représente 'v' n'est pas assez explicite, prend un meilleur nom de variable la prochaine fois, comme par exemple 'nom_ville' ou 'city_name'.

De plus, on dirait que tu n'as pas vraiment bien compris le filtrage de motif : on ne peut filtrer que sur des valeurs constantes (donc pas n.nom).

Pour ton problème, il est nécessaire qu'il existe (soit passée en argument, soit (mais c'est moins bien) en variable globale) une liste de toutes les villes. Tu peux la fournir ?

Est-ce que le type 'ville' est imposé par l'exercice ? Je me disais que tu pourrais obtenir le même résultat avec une table de hachage.

Sateth

3 décembre 2005 à 14:00:06

Euh non , le type Ville n'est pas imposé c'est moi qui l'ai enregistré.

Voila mon travail à l'heure actuelle

(**********************************************************************************************)
(***************************Enregistrement des différents types *************************)
(**********************************************************************************************)

type Ville = { nom:string ; villes_reliees:string list };;

(***********************************************************************************************)
(**Fonction permettant de déterminer la présence d'un élement dans une liste*******)
(***********************************************************************************************)

let rec presence (liste,element) =
   if (liste=[] ) then
false
else if ( hd (liste) = element ) then
true
else presence (tl(liste),element) ;;

(***********************************************************************************************)
(*****************************Définition des villes initiales (LC)****************************)
(***********************************************************************************************)

let Paris = { nom = "paris" ; villes_reliees = [ "marseille" ; "lyon" ; "nantes" ] };;
let Marseille = { nom = "marseille" ; villes_reliees = [ "paris" ; "lyon" ] };;
let Nantes = { nom = "nantes" ; villes_reliees = [ "paris" ] };;
let Lyon = { nom = "lyon" ; villes_reliees = [ "paris" ; "marseille" ] };;

(***********************************************************************************************)
(****************************** Introduction de la fonction gare ****************************)
(***********************************************************************************************)

let g =[
( Paris.nom , Paris.villes_reliees );
   ( Marseille.nom , Marseille.villes_reliees ) ;
   ( Nantes.nom , Nantes.villes_reliees );
   ( Lyon.nom , Lyon.villes_reliees ) ;
];;

(***********************************************************************************************)
(**************** autre méthode pour avoir g en tant que Ville list ***********************)
(****************************************** A privilégier*************************************)
(***********************************************************************************************)

let g =[
Paris;
   Marseille;
   Nantes;
   Lyon;
];;

(***********************************************************************************************)
(*************************Introduction de la fonction string_of_Ville************************)
(***********************************************************************************************)

let string_of_Ville (ville) = ville.nom::ville.villes_reliees;;

(***********************************************************************************************)
(*****************************************Question 1*****************************************)
(***********************************************************************************************)

(***********************************************************************************************)
(************************Faire la liste des villes contenues dans une LC******************)
(***********************************************************************************************)

let listeVilles (ville) = string_of_Ville (ville);;

(***********************************************************************************************)
(**********Liste des villes accessibles directement depuis une autre ville**************)
(***********************************************************************************************)

let listeVillesAccessibles (nom_ville) = match nom_ville with ville.nom -> ville.villes_reliees;;

(***********************************************************************************************)
(*****************************************Question 2*****************************************)
(***********************************************************************************************)

(***********************************************************************************************)
(***********Teste l'appartenance d'une ville à une gare ou à ses villes reliées**********)
(***********************************************************************************************)

let rec appartenance_gare (nom_ville,gare) =
match gare with
tete :: queue ->
if tete.nom::tete.villes_reliees =[] then
failwith " la ville ne peut etre trouvée"
else if (nom_ville = (tete.nom) ) then
true
else if ( presence ( (tete.villes_reliees) , nom_ville ) = true ) then
true
else appartenance_gare ( nom_ville , queue );;

(***********************************************************************************************)
(********** Teste l'appartenance d'une ville à une liste de correspondance ************)
(***********************************************************************************************)
(*
x une ville => String
lc une liste de correspondance => Ville

*)

let rec appartVille (nom_ville,ville) =
match ville with
tete :: queue ->
match t with
(tete.nom)::(tete.villes_reliees) ->
if tete = [] then
false
else if presence (tete,nom_ville) = true then
true
else appartVille (nom_ville,ville);;

bluestorm

3 décembre 2005 à 14:25:44

Tu devrais utiliser le type HashTable, ou alors Map, plutot que des listes de types personnels.

Hashtable : a chaque indice (clé) on associe une liste de valeurs (donc l'idée serait clé = nom de la ville et liste = villes reliées). Ce n'est pas vraiment l'usage habituel des tables de hachages mais j'ai déja implémenté des graphes comme cela en Ocaml et je sais que c'est assez efficace. En effet le temps d'accès est constant (complexité O(1)).

Map : a chaque clé tu associe une valeur (donc une liste de ville). C'est une structure de données plus 'conventionnelle' pour faire ca, mais elle repose sur des arbres binaires balancés : temps d'accès logarithmique (O(log(n))).

Tu peux aussi faire une liste de couples, qui a un temps d'accès beaucoup plus lent (O(n)) mais qui est plus intuitive je pense (c'est que que tu as fait pour ta première liste g).

D'autre part :
- ta fonction présence est inutile : List.exists sert à ca.
- en fait toutes tes fonctions 'appartenance' sont inutiles, List.exists suffit

Sateth

3 décembre 2005 à 14:36:13

C'est vrai ? ca existe ??? je sens que je vais m'en servir

En fait on a quasiment rien vu sur les listes et je suis qu'en premiere année a la fac je comprend pas trop ton truc sur la complexité logarithmique

Pourrait tu me faire un exemple ? (avec toi j'apprend plus qu'avec mon prof ^^)

Au fait c'est quoi la structure de List.exists ?

Merci encore

parce que :

List.exists qui applique une fonction à valeur booléenne à tous les éléments d'une liste, si une de ces applications vaut true alors le résultat est true, sinon la fonction retourne false.

Ca m'avance pas vraiment ... en plus ils ne donne aucun exemple :/

bluestorm

3 décembre 2005 à 15:04:18

là t'as le manuel ocaml
http://caml.inria.fr/pub/docs/manual-ocaml/manual034.html
dans lequel tu as la doc sur tous les modules, dont le module List :
http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html
dans lequel tu as la doc sur toutes les fonctions sur les listes, dont la fonction List.exists :
http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html#VALexists

Sateth

3 décembre 2005 à 15:10:21

Merci mais :

>exists "paris" g;;
> ^^^^^^^
This expression has type string,
but is used with type 'a -> bool.

.... bon alors la je ne suis pas , le 'a ca peut devenir un string non ???

bluestorm

3 décembre 2005 à 15:33:56

Citation

exists : ('a -> bool) -> 'a list -> bool

exists p [a1; ...; an] checks if at least one element of the list satisfies the predicate p. That is, it returns (p a1) || (p a2) || ... || (p an)

p est une fonction de type ('a -> bool) : elle prend en argument un élément de la liste et renvoie un booléen.

Si tu as une liste de vile, tu pourrais mettre par exemple :

if List.exists (fun ville -> ville.nom = "paris") liste_des_villes then ....

Pour la complexité algorithmique, voici ce qu'on trouve sur la wikipédia :
<lien>http://fr.wikipedia.org/wiki/Complexité_algorithmique</lien>

Sateth

4 décembre 2005 à 16:03:17

ok je capte, je devrai mettre un then (true ou false)

Merci encore pour la page avec les informations

Mais j'ai résolu mon problème initial :

let rec listeVillesAccessibles (nom_ville,gare) =
match gare with
tete::queue ->
if ( nom_ville = tete.nom ) then
tete.villes_reliees
else listeVillesAccessibles (nom_ville,queue);;

Ca me parait quand même suffisement clair comme ca non ?

bluestorm

4 décembre 2005 à 19:00:15

ta fonction elle compile pas.

Il faut rajouter un cas ou la liste est vide.

Sateth

4 décembre 2005 à 20:51:43

hehe, juste apres avoir posté jai changer ca

let rec listeVillesAccessibles (nom_ville,gare) =
match gare with
tete::queue ->
if ( nom_ville = tete.nom ) then
tete.villes_reliees
else if queue =[] then
failwith "aucune ville n'est accessible depuis cette ville"
else listeVillesAccessibles (nom_ville,queue);;

Pour une fois que je corrige avant que tu me reprennes

EDIT :

let appartVille (nom_ville,ville) =
if ville.nom = nom_ville then
true
else if exists (fun nom_ville -> ville.nom = nom_ville) ville.villes_reliees then
true
else false;;

ARF CA NE MARCHE PAS !!!

Bon je voudrait que cette fonction me dise : si nom_ville existe dans ville.villes_reliees alors vrai !! seulement la je comprend rien du tout !!!!!!!!!!! c vraiment casse tete cette fonction ... pourquoi faire simple quand on peut faire compliquer ....

bluestorm

4 décembre 2005 à 21:18:22

exists (fun nom_ville -> ville.nom = nom_ville) ville.villes_reliees

Prendre en argument un nom qui a déja été attribué, c'est vraiment pas cool du tout :
nom_ville là dedans, c'est l'argument de cette fonction ou de apartVille ?

let appartVille (nom_ville,ville) =
(ville.nom = nom_ville) ||
(exists
(fun ville_reliee -> ville_reliee.nom = nom_ville)
ville.villes_reliees)
;;

Sateth

4 décembre 2005 à 21:25:09

let appartVille (nom_ville,ville) =
(ville.nom = nom_ville) ||
(exists (fun villes_reliees -> villes_reliees.nom = nom_ville) ville.villes_reliees)
;;

Arf ca peut pas etre possible ton truc :

regarde le type :

type Ville = { nom:string ; villes_reliees:string list };;

ca te donne (exemple)

Paris = { nom = "paris" ; villes_reliees: ["blabla";"blabla";"blabla";"blabla";"blabla";"blabla"] )

Toplevel input:
> (exists (fun villes_reliees -> villes_reliees.nom = nom_ville) ville.villes_reliees)
> ^^^^^^^^^^^^^^^^^^^^
This expression has type string list,
but is used with type Ville list.

Je sens que je vais arreter de me casser la tête avec une fonction a laquelle je comprend rien, si je suis pas capable de l'expliquer au prof ca va pas aller, serieusement comment t'as réussi à comprendre son fonctionnement ??

Moi plus je regarde et moins je comprends ....

Comment est ce que se déroule la fonction qu'on introduit ???

De plus c'est quoi tes 2 traits avant la ligne exists [....] ? le filtrage c'est un trait avant normalement ...

bluestorm

4 décembre 2005 à 21:39:58

regarde mon code, regarde ton code, tu verras une petite différence qui tue.
(un indice : dans le (fun -> ...) c'est pas villes_reliees mais ville_reliee).

De plus, les deux barres ca veut dire 'ou' :
si c'est le nom de la ville, ou s'il existe une ville appartenant à la liste villes_reliees telle que son nom soit égale à nom_ville

Mais euh c'est qui ton prof ? Parce que tu ponds des choses tellement étranges parfois...

Sateth

4 décembre 2005 à 21:43:28

hihi, c'est pas la faute à mon prof sur ce coup , je sais que je suis bizare, j'ai une facon de voir les choses ...

Je teste de suite

EDIT :

J'ai compris comment ca marchait et j'ai rectifier ton erreur !!! tu te rends compte ??? ton code marchait pas et voial le bon :

let appartVille (nom_ville,ville) =
(ville.nom = nom_ville) ||
(exists
(fun ville_reliee -> ville_reliee = nom_ville)
ville.villes_reliees)
;;

en fait c'est de la forme exist ( fun ville-test -> ville-test = ville-quon-cherche) liste_ou_chercher

Merci encore et bravo pour ton axx en modo

Au fait, j'ai amoché ton joli code

let appartVille (nom_ville,ville) =
if (ville.nom = nom_ville) then
true
else if (exists (fun ville_test -> ville_test = nom_ville) ville.villes_reliees) then
true
else false
;;

bluestorm

4 décembre 2005 à 23:18:43

est-ce que tu te rend compte que quand tu fais

if blabla then true
else false

tu dis "si blabla est vrai alors vrai sinon faux" ?
C'est rigoureusement équivalent à 'blabla', et beaucoup plus long.

J'ai compris pourquoi mon code marchait pas : je croyais que la liste villes_reliees contenait des villes, et pas des chaines de caractères.

let appartVille (nom_ville,ville) =
(ville.nom = nom_ville) OR
(exists (fun ville_test -> ville_test = nom_ville) ville.villes_reliees)
;;

Examine tous les cas (ou = rend vrai et exists ren vrai, = rend vrai et exists rend faux, = rend faux et exists ren vrai, = rend faux et exists rend faux) et tu verras que ma solution avec 'OR' ou '||' est équivalent à la tienne, et beaucoup plus courte et plus jolie.

Sateth

4 décembre 2005 à 23:31:11

je sais
simplement je suis pas sur que mon prof aime, enfin je verrai avec lui

Je la met. Merci encore, mais stp, essaye de m'aider sans me donner un code tout fait.

Parce que c'est pas bon pour moi, je progresserai pas sinon. Même si c'est tres gentil