Epreuve enpc info problème Caml

[Archytas]

Bonsoir, j'essaie de faire ce sujet mais malheureusement je bloque à la question p9 page 5/8 si quelqun à le courage de lire ça commence à la page 3/8 et la page 4 ne concerne qu'un autre langage de programmation. Je dois créer une fonction voisins mais je maitrise mal le langage. Voici ce que j'ai essayé :

let rec voisins G s =
let m = G.n in
let B = [] in
match G.A with
| [] -> B
| t :: q ->
if t.a = s then begin
insere B t.b;
voisins {n = m - 1; A = q} s;
end
else if t.b = s then begin
insere B t.a;
voisins {n = m - 1; A = q} s;
end
else voisins {n = m - 1; A = q} s;;

Je reçois ce message d'erreur :

Entrée interactive:
> insere B t.a ;
> ^^^^^^^^^^^^
Attention: cette expression est de type int list,
mais est utilisée avec le type unit.

je ne comprends pas ma fonction insere est pourtant bien définie, B est bien une liste et t.a est bien un entier naturel, je ne vois pas ce que le type unit vient faire la dedans .

[Dlzlogic]

Bonjour,
Que voila une jolie épreuve.
Pour faire ça en 2h1/4, il faut pas tellement hésiter entre 2 questions.

Caml : Écrire une fonction insere telle que, si L est une liste d’entiers distincts triée par ordre croissant et s
un entier quelconque, insere L s renvoie
- la liste d’entiers obtenue en insérant s dans L selon l’ordre croissant si la valeur s ne figurait
pas dans L,
- la liste L si s figurait déjà dans L.

Cette fonction renvoie une liste donc la syntaxe attendue pourrait être
B = insere B t.a
En effet, on pourrait imaginer que pas défaut une fonction attend un int
Il serait intéressant de voir la fonction "insère".

A propos de couleurs, je vous propose un algorithme intéressant : soit un ensemble de zones accolées, tels que sont les départements par exemple. On sait que on peut attribuer une couleur, parmi 4, de façon que 2 zones voisines aient 2 couleurs différentes.
Ecrire un algorithme qui réalise cela.

[Archytas]

Bonjour,
Que voila une jolie épreuve.
Pour faire ça en 2h1/4, il faut pas tellement hésiter entre 2 questions.

Cette fonction renvoie une liste donc la syntaxe attendue pourrait être
B = insere B t.a
En effet, on pourrait imaginer que pas défaut une fonction attend un int
Il serait intéressant de voir la fonction "insère".

A propos de couleurs, je vous propose un algorithme intéressant : soit un ensemble de zones accolées, tels que sont les départements par exemple. On sait que on peut attribuer une couleur, parmi 4, de façon que 2 zones voisines aient 2 couleurs différentes.
Ecrire un algorithme qui réalise cela.

Haha je n'en suis pas encore aux couleurs (ce dont tu parles ressemble au théorème des 4 couleurs mais ici vu d'un point de vue géographique on ne serait pas en 2D vu que deux arretes peuvent se couper) !! Oui le problème c'est que t.a est bien un entier donc je ne vois pas pourquoi ça ne fonctionne pas ! Voici la fonction insere :

let rec insere L s =
match L with
| [] -> [s]
| t :: q -> if t = s then L
else if t < s then t :: insere q s
else s::L ;;

[Doraki]

(insere B t.a) est une liste d'entiers, alors que toi tu t'en sers comme si c'était un truc de type unit.

[Archytas]

(insere B t.a) est une liste d'entiers, alors que toi tu t'en sers comme si c'était un truc de type unit.

Justement c'est là le problème !! Je ne vois pas en quoi je m'en sers comme d'un type unit ! J'y entre deux paramètres qui sont les bons, d'où sort ce type unit :triste: ? C'est peut être le mélange récursif/itératif, non ? On m'a dit que c'était très mal vu mais de là à ne pas fonctionner...

[Doraki]

Le ; indique que tu demandes à calculer un type unit (donc un calcul qui est censé renvoyer (), et qui a probablement des effets secondaires comme afficher un truc ou modifier une valeur quelquepart)
comme :

print "blabla";
x:= 5;
t.(0)<-17;
();
Ca c'est des trucs de type unit.

Imagine que le résultat de insere machin soit [1;3;4;5].
y'a pas un truc qui te gêne dans :

begin
[1;3;4;5];
voisins {n = m - 1; A = q} s; (où encore une fois tu prends une liste et tu mets un ; derrière)
...

[Dlzlogic]

La fonction insere renvoie quelque-chose.
Dans pratiquement tous les langages, une fonction renvoie quelque-chose.
Ce quelque-chose peut être "rien" ou "n'importe quoi" (ex type void en C)
ça peut être un booléen, mais en l'occurrence c'est une liste.
Donc, une fois que la fonction sera exécutée, à la place, il y aura ce qu'elle a renvoyé.
Comme elle revoie une liste, il n'y a pas la place prévue pour la recevoir. D'où l'erreur.

Concernant les 4 couleurs, il s'agit bien de ce théorème, mais l'algorithme dont je parle ne consiste pas à le démontrer, mais à le mettre en œuvre.

[Archytas]

D'accord merci de votre aide !
Mais dans mon cours il est bien spécifié que lorsque je veux faire plusieurs actions dans un then le doit faire appelle au bloc begin ... end avec un ";" entre chaque action ! D'après ce que vous me dîtes l'usage du ";" est réservé à ce qu'on appelle les effets de bords, non ? Ou ça n'a rien à voir ? Du coup je ne sais pas comment appréhender le problème. Quelle synthaxe est la bonne ?

[Doraki]

effet de bord est une traduction malheureuse de "side-effect" (effet secondaire, comme les médicaments), qui s'est regrettablement propagée dans le milieu informatique.

écrire "t.(2)<-17; ..." est équivalent à "let _ = t.(2)<-17 in ...", qui fait l'évaluation de t.(2)<-17, (à savoir (), avec l'effet secondaire d'aller changer la valeur de t.(2)), et qui jette le résultat () (qui est complètement inutile)

La fonction insere n'a aucun effet secondaire (à moins que t'aies fait n'importe quoi j'ai pas regardé)
Donc quelquechose me dit que tu n'as pas envie de calculer cette liste pour la jeter immédiatement derrière, donc tu dois lui donner un nom, et mettre
let nouvelleliste = insere truc machin in
...

Ensuite, ce que tu fais avec nouvelleliste dépend de ce que tu veux faire avec cette liste



Dans ton cours, les "actions" sont des trucs de type unit donc des trucs qui font des effets secondaires.

Une liste n'est pas une action. Ecrire "[1;3;4;5];" ne fait aucun sens.

[Dlzlogic]

Je ne connais pas la syntaxe de ce langage, mais ce devrait être suivant cette logique.
Déclaration 'une_liste'
Déclaration 'liste_res'
Début_boucle
liste_res = insere une liste val
une_liste = liste_res
fin_boucle

Le signe '=' signifie "on attribue à la variable de gauche (LV) la valeur obtenue par ce qui est à droite (RV)".

[edit] @ doraki, je crois que pour une fois on est d'accord.

[Archytas]

Très bien merci à vous deux je vais essayer comme ça :id: ! Bonne journée !

[Dlzlogic]

Il me semble utile d'apporter une précision sur ceci.

Dans pratiquement tous les langages, une fonction renvoie quelque-chose.

Dans le langage mathématique une fonction "renvoie un résultat", ceci peut être synthétisé ainsi "y = f(...)"
Il en est à peu près de même en informatique, une fonction "renvoie" quelque-chose.
Il y une exception de taille : les constructeurs.
Un constructeur, comme un destructeur ne revoie rien.
Pour rappel, un constructeur est une fonction qui crée un objet dans les langages orientés objet.
La syntaxe type est
OBJET *unObjet = new OBJET(...);
new est un opérateur qui renvoie un pointeur.
Cet opérateur appelle une fonction qui fait quelque-chose, mais ne renvoie rien.

J'ai utilisé un langage interprété dont la syntaxe est constituée d'instructions de la forme
ABCD,V1,V2, ... Vn
Où ABCD est le nom de l'instruction, et les noms Vn des variables.
Il est vrai que cette syntaxe est un peu déroutante lorsqu'on a fait de la programmation.

L'utilisation des pointeurs en C prend toute sa signification dans ce contexte.
Exemple l'instruction d'ouverture de fichier s'écrit ainsi
FILE *fic = fopen("MonFic.txt","rt"); // par exemple
La valeur renvoyée est un pointeur sur quelque-chose qui définit un fichier (son âge, sa taille, son auteur, son contenu etc.). La valeur renvoyée est sur 32 bits (4 octets).

Je tenais à préciser cela pour qu'il n'y ait pas d’ambigüité sur ce qui a été dit dans les réponses précédentes.

[Archytas]

Je n'ai plus de message d'erreur mais le programme ne fonctionne pas et me renvoie la liste vide automatiquement . C'est donc une erreur de logique ce qui est plus rassurant !

Voici le nouveau programme :

let rec voisins G s =
let m = G.n in
let B =[] in

match G.A with
| [] -> B
| t :: q -> if t.a = s then begin
let _ = insere B t.b in
voisins {n = m ; A = q} s;
end

else if t.b = s then begin
let _ = insere B t.a in
voisins {n = m ; A = q} s;
end

else voisins {n = m ; A = q} s;;

[Doraki]

Oui il renvoie toujours [].
Le seul endroit où ta fonction ne s'appelle pas récursivement, c'est quand tu lui donnes un graphe sans arête, et dans ce cas-là il renvoie B, qui est toujours la liste vide [].

Toutes les autres fois, il fabrique un graphe avec une arête en moins et s'appelle dessus. Donc il fait ça jusqu'à ce qu'il fabrique le graphe sans arête et là il renvoie [].

Ca ne sert à rien de mettre "let _ = insere machin truc in" puisque insere ne fait pas d'effet secondaire. A quoi bon calculer cette liste si tu ne t'en sers pas !?? Qu'est-ce que tu veux en faire du résultat de insere machin truc ? tu veux l'utiliser quelque part ?

je ne comprends pas trop non plus l'intérêt de ton let B = [] in ...
autant remplacer tous tes B par des [], ça fera la même chose.

C'est toi qui a écrit la fonction insere ou c'est quelqu'un d'autre ?

[Archytas]

Oui il renvoie toujours [].
Le seul endroit où ta fonction ne s'appelle pas récursivement, c'est quand tu lui donnes un graphe sans arête, et dans ce cas-là il renvoie B, qui est toujours la liste vide [].

Toutes les autres fois, il fabrique un graphe avec une arête en moins et s'appelle dessus. Donc il fait ça jusqu'à ce qu'il fabrique le graphe sans arête et là il renvoie [].

Ca ne sert à rien de mettre "let _ = insere machin truc in" puisque à bon calculer cette liste si tu ne t'en sers pas !?? Qu'est-ce que tu veux en faire du résultat de insere machin truc ? tu veux l'utiliser quelque part ?

je ne comprends pas trop non plus l'intérêt de ton let B = [] in ...
autant remplacer tous tes B par des [], ça fera la même chose.

C'est toi qui a écrit la fonction insere ou c'est quelqu'un d'autre ?

C'est moi qui est écrit cette fonction et on a fait la correction et le prof avait la même à quelques variantes bénignes près, je l'ai testé sur de nombreux exemples et elle respecte toutes les conditions que le sujet lui impose. Bref le problème ne vient pas de là.
La question qui est posée est suivant un graphe G et un sommet s de donner tous les voisins de s ordonné dans une liste. Donc je créé une liste vide et suivant la liste composant le graphe : si elle est vide c'est le cas de base on renvoit []. Sinon elle est de la forme t::q avec t un élement de la liste et q le reste de la liste privé de cet élément. Je regarde donc si s est dedans auquel cas l'autre entier est un voisin que je range dans ma liste B grâce à la fonction insere... d'où son utilité. Enfin niveau logique c'est tenable, non ? Je vois pas où ça coince :mur: .

[Doraki]

ue je range dans ma liste B grâce à la fonction insere...

Non. Ce n'est pas ce que fait la fonction insère.

Tu as l'air de penser que B est une variable (qui d'ailleurs serait conservée par magie à travers chaque appelle récursif de voisins) et que la fonction insère modifie son contenu.

B n'est pas une variable, mais le nom d'une liste d'entiers. A chaque fois que la fonction voisins est appelée (donc à chaque étape), tu décides que B est le nom de la liste vide [].
Ensuite (dans le cas où la première arête t satisfait t.a = s), tu calcules insère B t.b, c'est-à-dire insère [] t.b, ce qui te renvoie la liste obtenue quand on insère t.b dans la liste [], à savoir [t.b].
Ensuite, tu jettes ce résultat (vu que tu ne donnes pas de nom à cette nouvelle liste),
et tu appelles voisins sur un nouveau graphe plus petit.
Celui-ci te renvoie la liste [], et donc c'est [] tu renvoies comme résultat.

De base, ça ne peut pas marcher parceque la liste des voisins de s dans le graphe G, ce n'est pas la même chose que la liste des voisins de s dans le graphe G' où on a retiré la première arête.
Donc il faut que tu réfléchisses mieux au rapport entre ce que tu veux (la liste des voisins de s dans le graphe G) et ce que ton appel récursif est censé te donner (la liste des voisins de s dans le graphe G' où on a retiré la première arête)

[Archytas]

Non. Ce n'est pas ce que fait la fonction insère.

Tu as l'air de penser que B est une variable (qui d'ailleurs serait conservée par magie à travers chaque appelle récursif de voisins) et que la fonction insère modifie son contenu.

B n'est pas une variable, mais le nom d'une liste d'entiers. A chaque fois que la fonction voisins est appelée (donc à chaque étape), tu décides que B est le nom de la liste vide [].
Ensuite (dans le cas où la première arête t satisfait t.a = s), tu calcules insère B t.b, c'est-à-dire insère [] t.b, ce qui te renvoie la liste obtenue quand on insère t.b dans la liste [], à savoir [t.b].
Ensuite, tu jettes ce résultat (vu que tu ne donnes pas de nom à cette nouvelle liste),
et tu appelles voisins sur un nouveau graphe plus petit.
Celui-ci te renvoie la liste [], et donc c'est [] tu renvoies comme résultat.

De base, ça ne peut pas marcher parceque la liste des voisins de s dans le graphe G, ce n'est pas la même chose que la liste des voisins de s dans le graphe G' où on a retiré la première arête.
Donc il faut que tu réfléchisses mieux au rapport entre ce que tu veux (la liste des voisins de s dans le graphe G) et ce que ton appel récursif est censé te donner (la liste des voisins de s dans le graphe G' où on a retiré la première arête)

Hm je vois... C'est assez génant en effet j'avais pas pensé que les appels récursif réinitialisaient les données... Bon je vais aller voir du coté de l'itératif, ça semble plus naturel pour cette question du coup mais en indication le prof nous avait conseillé si on comtait faire cette question de la traiter avec match G.A with ... ce qui est plutot utiliser en récursif !
En tout cas merci, je vais essayer de me débrouiller avec ça (= ! C'est beaucoup plus clair !

EDIT :
J'en suis finalement venu à bout de manière itérative si quelqun est interessé voici une solution :

let voisins G s =
let B = ref [] in
let C = ref G.A in
while !C [] do
if (hd !C).a = s then B := insere !B (hd !C).b
else if (hd !C).b = s then B := insere !B (hd !C).a ;
C := tl !C;
done;
B;;

[Iroh]

Salut,

Une autre version en OCaml ou en Haskell si ça peut t'aider.

[Archytas]

Salut,

Une autre version en OCaml ou en Haskell si ça peut t'aider.

Ah oui pas mal, j'avais pensé à faire une fonction auxilliaire pour voisin mais je ne savais pas comment la gérer :hum: . J'ai encore du mal à bien gérer les match... with récursif, je trouve ça plus naturel encore les while... if ... then ... else ... même si c'est pas très élégant !
En tout cas merci !

[Iroh]

Tu peux le faire plus simplement sinon: http://paste.scratchbook.ch/view/878bd988