Discussion :

[Dunk]

Bonsoir

Voici mon problème : j'ai un bout de code en Caml qui doit me servir à coder une fonction... mais je ne connais pas le Caml !
Le morceau de code n'étant vraiment pas long, je me suis dit que je trouverais bien qqun ici pour m'aider à le traduire... (en algo pure, ou à la limite en C, en Pascal, ...)
Voici le code en question :

Code :

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

1
2
3
4
5
6
7
8
let enumere p =
  let t = make_vect (p+1) [] in
  t.(0) <- [[|1;-1|]];
  for k=1 to p do
     for i=0 to k-1 do t.(k) <- t.(k)@fusion (t.(i)) (t.(k-1-i))
     done
  done;
  t;;

A noter que "fusion" est une fonction définie plus haut, qui accepte 2 paramètres.
En gros, ce que je comprends :
- on a à faire à une procédure "enumere", qui admet un paramètre p (qui est un réel, ça je le sais)
- elle remplit un tableau (ça je le sais aussi ) t, de p+1 éléments
- t[0] : je comprends pas ce qu'on met dedans...
- on a 2 boucles imbriquées, je comprends la syntaxe du for... mais que signifie : t.(k) <- t.(k)@fusion (t.(i)) (t.(k-1-i)) ??
J'ai lu qqpart que @ était un opérateur de concaténation... mais je comprends pas trop...


Merci d'avance de votre aide

[pcaboche]

- t[0] : je comprends pas ce qu'on met dedans...

[|1;-1|] est un tableau d'entier contenant 1 et -1
[[|1;-1|]] est une liste contenant un seul élément: un tableau d'entier contenant 1 et -1

mais que signifie : t.(k) <- t.(k)@fusion (t.(i)) (t.(k-1-i)) ??

En fait, il doit manquer des parenthèses:
t.(k) <- t.(k)@( fusion (t.(i)) (t.(k-1-i)) )

Vu que t.(k) = [] (la liste vide), cela revient à faire directement :
t.(k) <- fusion (t.(i)) (t.(k-1-i))

Après, c'est facile à comprendre... (ça ressemble à n'importe quel langage impératif)

Sinon, elle est censée faire quoi la fonction fusion?

[Jedai]

Vu que t.(k) = [] (la liste vide), cela revient à faire directement :
t.(k) <- fusion (t.(i)) (t.(k-1-i))

t.(k) n'est pas toujours égal à la liste vide ! Par ailleurs sans fusion() il est difficile de déterminer ce que fait ce code.

--
Jedaï

[Dunk]

Je comprends bien, mais ça va être relativement compliqué à expliquer, étant donné que c'est une fonction très spécifique au programme en question.
En gros, fusion est une fonction qui admet comme paramètres 2 listes et qui renvoie une 3e liste formée à partir de combinaisons d'éléments des 2 premières...

Autre question : y a-t-il des pointeurs en Caml ? est-ce qu'il y a une analogie possible entre l'utilisation des pointeurs pour les listes en Pascal et les listes de Caml ?

[pcaboche]

t.(k) n'est pas toujours égal à la liste vide !

J'ai l'impression que si: au départ, on créé une liste avec make_vect ne contenant que []. Ensuite on change t.(0) en [|1;-1|], puis on prend k=1. De par le parcours du tableau, à tout moment du programme, pour tout i1 tel que i1<k, t.(i1) != [], et pour tout i2 tel que k=<i2, t(i2)=[]. Par conséquent, à tout moment du programme on a t.(k)=[].

[pcaboche]

Autre question : y a-t-il des pointeurs en Caml ?

On appelle ça des références.

est-ce qu'il y a une analogie possible entre l'utilisation des pointeurs pour les listes en Pascal et les listes de Caml ?

Il y a longtemps que je n'ai pas fait de Pascal. Ce que tu cherches à faire, c'est un itérateur sur la liste, c'est bien cela? Je ne sais pas si cela existe.

Indépendemment de cela, il est assez maladroit en Caml de vouloir reproduire ce que l'on a l'habitude de faire dans des programmes impératifs comme C ou Pascal. Surtout au début (un fois que tu as un peu d'expérience, tu fais ce qui te semble le mieux). Caml est avant tout un langage fonctionnel et les fonctions sont programmées récursivement.

Pour appliquer une fonction à tous les éléments d'une liste, on utilisera list__map:

Code :

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

list__map lafonction liste

Au fait, tu utilise camllight ou ocaml? c'est un projet universitaire ou autre?

[Jedai]

J'ai l'impression que si: au départ, on créé une liste avec make_vect ne contenant que []. Ensuite on change t.(0) en [|1;-1|], puis on prend k=1. De par le parcours du tableau, à tout moment du programme, pour tout i1 tel que i1<k, t.(i1) != [], et pour tout i2 tel que k=<i2, t(i2)=[]. Par conséquent, à tout moment du programme on a t.(k)=[].

Prenons k = 2, et supposons que si l'une des deux listes est non vide, fusion() renvoie une liste non vide. Tu est d'accord que quand k = 2, t.(0) et t.(1) sont non vide ? Lorsque i = 0, on met donc t.(2)@(fusion t.(0) t.(...)) dans t.(2), donc t.(2) n'est plus vide lorsqu'on arrive à i = 1... J'ai l'impression que tu avais oublié la boucle interne dans ton raisonnement ?

--
Jedaï

[pcaboche]

Oui, tu as raison Jedai. Ca me parait tellement pas naturel de faire de l'itératif en Caml que j'avais pas vu qu'on réécrivait toujours dans la même case du tableau.

[Dunk]

Bon, je vais vous "avouer" ce qui m'a amené à essayer de déchiffrer ce programme...
Je suis en prépa maths, option informatique, et j'ai un DM d'info, qui est en fait un sujet de concours. Or, en France, il y a 2 langages possibles pour l'option informatique : Caml et Pascal. Comme vous pouvez vous en douter, dans ma prépa, on apprend le Pascal...
Au final, j'ai réussi à me procurer le corrigé du sujet en question... mais bien sûr les programmes sont corrigés uniquement en Caml.
Jusque là (çàd la dernière question), le corrigé ne m'avait pas servi, étant donné que j'en étais venu à bout tout seul. Mais pour cette question, étant donné que j'ai déjà du mal à comprendre la question, j'ai voulu regarder le corrigé... et je tombe sur ce programme en Caml, qui m'est totalement incompréhensible...

Voila tout...
Je vais au devant de toute critique : je ne considère pas que je triche, étant donné que ça fait maintenant 3 jours que je planche sérieusement sur le sujet et sur cette question, et que je ne la recopie pas bêtement ; alors que 90% de ma promo n'arrivera pas à faire plus de 75% du sujet et ne se cassera pas la tête plus que ça... C'est le principe d'un devoir maison : pouvoir chercher sur les réseaux d'information à sa disposition.


Je vais continuer à chercher maintenant, merci de votre aide en tout cas

[Jedai]

Et tu es dans quelle prépa ? Bonne chance pour tes concours en tout cas (mais tu dois être en MPSI pour l'instant, sinon tu serais jusqu'au cou dans les écrits tout de suite).
L'option informatique en Pascal, c'est vraiment idiot... CaML est bien mieux adapté pour faire de l'algorithmique ! En tout cas bonne chance, je suis passé par là moi aussi.

--
Jedaï, étudiant en Informatique fondamentale à l'ENS Lyon (rentré par le concours maths )

PS : t'aurais pas un lien vers le sujet par hasard ?

[pcaboche]

Il n'y a pas de mal à chercher des ressources pour voir comment implémenter certains programmes (c'est comme cela qu'on apprend), dès l'instant que tu essayes de comprendre ce que tu fais (ce qui est vraisemblablement ton cas).

Maintenant, si je comprends bien, ton problème c'est de traduire ce bout de programme en Pascal (ou en langage algorithmique), c'est ça?

Ce qui m'étonne, c'est qu'un prof d'université ait utilisé Caml pour faire de l'itératif . Le principe de Caml, c'est justement de programmer autrement qu'en itératif, surtout en fac de maths.

[pcaboche]

L'option informatique en Pascal, c'est vraiment idiot... CaML est bien mieux adapté pour faire de l'algorithmique !

+1

[Dunk]

Jedai -> Je suis en effet encore en MPSI au lycée Fabert de Metz.
L'option info en Pascal, ça se discute... étant donné qu'on a fait "pas mal" de Maple au 1er trimestre, ça permet de rester dans la continuité plus ou moins... là où Caml est radicalement différent.
D'ailleurs, dans la majorité des grosses prépas, il me semble qu'ils font du Caml, étant donné que la plupart des sujets sont corrigés en Caml et que l'option info est surtout destinée (par tradition plus qu'autre chose...) aux "plus forts".
Sinon, puis-je te demander dans quelle prépa tu étais, comment tu étais classé en sup et spé et si tu as fait 5/2 ? parce qu'informatique fondamentale à ENS Lyon, ça m'intéresserait particulièrement et j'en suis encore à un stade où je cherche mon orientation (à la base, j'aimerais bien avoir Mines Nancy, mais bon, je ne suis pas encore fixé)
Enfin, le lien du sujet (ESIM 2000) : http://info-prepa.leledy.org/sujets-...rs/i00fm1e.pdf L'exo en question est le 3e : "Expressions préfixées bien formées".


pcaboche -> oui, je peux t'assurer que je suis particulièrement sérieux j'avoue qu'en maths/physiques, je me serais pas cassé la tête (pourtant, ça serait peut-être plus utile... ) mais j'aime bcp l'info, et j'ai passé le plus clair de ma jeunesse devant mon pc, donc je me dois de bien maitriser au moins l'info
Mon problème, en clair, est en effet de traduire ce bout de code Caml en Pascal. Mais étant donné ce que j'ai pu lire, vu la "philosophie" de Caml, ça va être dur d'en faire une simple traduction, étant donné que les 2 langages n'ont pas vrmt la même optique... Mais c'est pas grave, si j'arrive à comprendre l'algo, je ferai le programme en Pascal sans trop de problèmes je pense.
Et puis pour ce qui est de ton étonnement quant à la correction en Caml... disons que tous les sujets ou presque sont corrigés en Caml, car comme je l'ai dit, la majorité des options info de France apprennent le Caml et passent leurs concours en Caml...



En tout cas, merci beaucoup à tous les 2 de votre aide et de votre compréhension, ça fait plaisir de ne pas se sentir en terrain hostile à peine la phrase "j'ai trouvé la correction de mon DM" prononcée...

[Dunk]

Ah, je vais mettre le corrigé que j'ai trouvé en pièce jointe aussi, ça peut servir...

[pcaboche]

Mais étant donné ce que j'ai pu lire, vu la "philosophie" de Caml, ça va être dur d'en faire une simple traduction, étant donné que les 2 langages n'ont pas vrmt la même optique...

Ce ne sera pas un problème vu que justement le programme est plus une traduction littérale d'un programme en langage impératif (façon Pascal). Je pourrai t'aider, mais un peu plus tard, car là j'ai des choses à faire.

Si ça t'intéresse, je pourrai aussi te montrer comment on aurait fait selon la "philosophie" Caml.

[Dunk]

pcaboche -> Merci beaucoup !
Et oui, ça m'intéresse de voir ce que ça donnerait en "vrai" Caml, mais il faudrait que tu commentes un peu, parce qu'il y a qques éléments de syntaxe de Caml qui me déroutent encore... (pour ne pas dire "la plupart" )
Encore merci en tout cas

[Dunk]

Bon, j'ai un peu avancé...

En gros, j'ai compris ça :

Code :

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

1
2
3
for k:=1 to p do
   for i:=0 to k-1 do
      t[k]:=concat(t[k],fusion(t[i],t[k-1-i]));

Alors, je comprends pourquoi k-1-i, je comprends l'utilisation des boucles, pas de prob...
Y a un truc qui me pose vraiment problème :
t.(0) <- [[|1;-1|]];
En fait, pour ceux qui auront le courage de jeter à l'énoncé, je comprends pas pourquoi on peut mettre 1... -1 OK, mais normalement, y a que -1 et pas de 1...
Je sens que j'y suis presque là...

[pcaboche]

Y a un truc qui me pose vraiment problème :
t.(0) <- [[|1;-1|]];

Euh... je ne sais pas comment dire, en fait c'est:

Code :

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

t[0] := {1, -1}

On affecte à t[0] un tableau contenant les éléments 1 et -1 (ce n'est pas un intervalle, au cas où tu te poserais la question vu que tu as un cursus math)




En Caml, on ferait un truc comme ça (code non testé, c'est pour donner une idée) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
let rec compute_list rList p =
 
  (* on inverse la liste *)
  let liste = rev rList in
 
  (match p with
     0 -> liste
   | n when 0<n -> 
 
     let nextElem = compute_elem liste rlist in
 
     compute_list (nextElem::rList) (p-1)
 
   (* cas où n<0 *)
   | _ -> raise InvalidArgumentException
  )
 
and compute_elem l1 l2 =
  (match (l1, l2) with
     ([], [])         -> []
 
   | (t1::q1, t2::q2) -> (fusion t1 t2)::(compute_elem q1 q2)
 
   (* en cas d'erreur *)
   | _                -> raise SizeMismatchException
  )
;;
 
 
let enumere = compute_list [ [[|1;-1|]] ] ;;

... sauf qu'au lieu d'avoir comme résultat un tableau de listes de tableaux d'entiers, on aurait une liste de listes de tableaux d'entier.

[Jedai]

Y a un truc qui me pose vraiment problème :
t.(0) <- [[|1;-1|]];
En fait, pour ceux qui auront le courage de jeter à l'énoncé, je comprends pas pourquoi on peut mettre 1... -1 OK, mais normalement, y a que -1 et pas de 1...
Je sens que j'y suis presque là...

Relis ton sujet : tout mot est représenté par un tableau de la façon suivante :
à l'emplacement 0 on met la longueur du mot.
Ensuite on met un 1 pour '+' et un -1 pour 'a'.
Autrement dit ce que veut dire t.(0)<-[ [|1;-1|] ] c'est : la liste des mots de longueur 1 (= 2 * 0 + 1) bien formés est "a" (et c'est tout).

--
Jedaï

[Dunk]

Ah oui d'accord... mais dans ce sujet, il est plus intéressant d'avoir un tableau plutot qu'une liste...
Je comprends pas grand chose au code Caml que tu donnes, mais c'est relativement intéressant, je me pencherai un peu sur le Caml pdt les vacances d'été je pense.

Sinon, oui, j'avais compris que c'était un tableau de 2 éléments : 1 et -1... mais c'est plutot en contradiction avec mon énoncé, c'est pour ça que je me pose des questions dessus...

J'ai essayé de traduire la fonction en Pascal, mais bien sûr, ça ne marche pas... même si j'ai vrmt l'impression que j'en suis pas loin.
Quoiqu'il en soit, vous avez rempli votre mission, mes problèmes maintenant n'ayant plus grand chose à voir avec du Caml.

A moins que vous n'ayiez encore de choses susceptibles de m'aider à rajouter, je pense qu'on va clore le débat
J'attends encore juste la réponse de Jedai, pour la prépa

Et en attendant, je vous remercie beaucoup de l'aide que vous m'avez apporté, j'en espérais pas tant, je reviendrai