Discussion :

[TchoubiTchoub]

J'ai utilisé la version online sur le site http://tinyurl.com/ocamltop
Par contre, impossible de faire des copier/coller donc j'ai cherché comment l'installer sur mon PC et maintenant, c'est bon !

Ah oui...Vous êtes allé chercher loin, hein ! Ce site c'est pour montrer une utilisation de js_of_ocaml A la rigueur vous pouviez aller sur https://try.ocamlpro.com/ qui permet de copier/coller, sauvegarder

Du coup, j'ai toutes mes fonctions dans un fichier et même si je sors d'Ocaml, je peux recharger facilement mes fonctions

Hahaha !

[alexpand]

L'algorithme que je vois pour la fonction get n s est le suivant:
- si le nombre d'exemplaires de s (nb_ex s) est strictement inférieur à n alors je retourne l'élément Nil
- sinon, Cons ((e1, s1), Cons ((e2, s2), ..., Cons ((en, sn), Nil)))) -> pour chaque élément ei dans s, si i est différent de n, alors nb=nb+si, sinon (donc i=n), on retourne ei

Bon, je ne sais pas si c'est très clair

[TchoubiTchoub]

L'algorithme que je vois pour la fonction get n s est le suivant:
- si le nombre d'exemplaires de s (nb_ex s) est strictement inférieur à n alors je retourne l'élément Nil

Nil n'est pas un élément, c'est un ensemble. Vous aurez un problème de type assurément. En fait, si n > nb_ex s alors c'est une exception à gérer.

- sinon, Cons ((e1, s1), Cons ((e2, s2), ..., Cons ((en, sn), Nil)))) -> pour chaque élément ei dans s, si i est différent de n, alors nb=nb+si, sinon (donc i=n), on retourne ei

Ce n'est pas si i différent de n mais bien si s1 + s2 + ... + si < n alors on n'est pas encore arrivé au bon élément donc on augmente notre indice de recherche de si

Bon, je ne sais pas si c'est très clair

Ca l'est mais c'est incorrect

[alexpand]

Nil n'est pas un élément, c'est un ensemble. Vous aurez un problème de type assurément. En fait, si n > nb_ex s alors c'est une exception à gérer.


Ce n'est pas si i différent de n mais bien si s1 + s2 + ... + si < n alors on n'est pas encore arrivé au bon élément donc on augmente notre indice de recherche de si


Ca l'est mais c'est incorrect

Merci pour votre retour
Ok. J'ai l'impression qu'il y a une histoire d'accumulateur à mettre en place... je m'y atèle donc ...
Par contre, je vais laisser tomber cette fonction get (merci en tout cas pour votre aide mais j'y reviendrai ultérieurement). En effet, mon formateur m'a bien souligné l'importance de l'ordre supérieur: il nous a conseillé de reprendre les fonctions nb_ex, subset, sum et intersection. Je vais donc comprendre la fonction nb_ex que vous m'avez détaillé lors d'un précédent message

EDIT: je viens de comprendre l'accumulateur!

En reprenant un exemple, c'est plus clair:

Pour rappel, voici ce qui avait été déclaré (il se reconnaitra ):

Code :

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

1
2
3
let rec fold_mset f a s = match s with
  | Nil -> a
  | Cons (e', s') -> fold_mset f (f a e') s'

Et la fonction suivante:

Code :

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

let inc acc (_, i) = acc + i

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fold_mset inc 0 (Cons ((3, 1), Cons ((7, 5), Nil)))
 
e'=(3, 1)
s'= Cons ((7, 5), Nil)
--> fold_mset inc (inc 0 (3,1)) Cons ((7, 5), Nil)
--> fold_mset inc 1 Cons ((7, 5), Nil)
 
e'=(7, 5)
s'=Nil
--> fold_mset inc (inc 1 (7, 5)) Nil
--> fold_mset inc 6 Nil
 
s=Nil
--> 6

Je vais essayer avec la fonction subset

[alexpand]

Bon, j'ai vraiment du mal avec l'accumulateur

Pour la fonction subset, voilà ce que je vois: il faut appliquer un accumulateur acc de type booléen qui vérifie si le premier élément e du multi-ensemble s1 est présent dans s2 et on retourne acc && member e s2 et on fait ainsi de suite en prenant l'élément de gauche du multi-ensemble.

Par contre, il faut prendre 2 multi-ensembles en paramètres de la fonction. Or, la fonction fold_mset ne peut prendre qu'un multi-ensemble.

Faut-il que je modifie la fonction fold_mset ou peut-on le faire autrement? Merci

EDIT:

Je pensais à une fonction comme ci-dessous pour gérer la valeur booléenne à chaque itération mais je ne comprends pas l'erreur:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
# let subset_crt acc e s = acc && member e s
  ;;
val subset_crt : bool -> 'a -> 'a mset -> bool = <fun>
# subset_crt true (1, 4) s2;;
Characters 23-25:
  subset_crt true (1, 4) s2;;
                         ^^
Error: This expression has type int mset
       but an expression was expected of type (int * int) mset
       Type int is not compatible with type int * int
# s2;;
- : int mset = Cons ((1, 4), Cons ((5, 1), Cons ((7, 3), Nil)))

Ca ne me rassure pas pour mon examen...

[TchoubiTchoub]

Bon, j'ai vraiment du mal avec l'accumulateur

Pour la fonction subset, voilà ce que je vois: il faut appliquer un accumulateur acc de type booléen

La formulation "appliquer un accumulateur acc" est malheureuse ;-)

qui vérifie si le premier élément e du multi-ensemble s1 est présent dans s2 et on retourne acc && member e s2

Pourquoi renvoyer acc && member e s2 ? Si acc est vrai, autant renvoyer member e s2 et si acc est faux alors autant s'arrêter.

et on fait ainsi de suite en prenant l'élément de gauche du multi-ensemble.

Par contre, il faut prendre 2 multi-ensembles en paramètres de la fonction. Or, la fonction fold_mset ne peut prendre qu'un multi-ensemble.

Faut-il que je modifie la fonction fold_mset ou peut-on le faire autrement? Merci

La fonction fold_mset est faite pour appliquer une opération sur l'ensemble des éléments d'UN ensemble.

Subset étant une opération sur deux ensembles qui renvoie un booléen, fold_mset n'est pas appropriée. Néanmoins, l'idée derrière fold_mset est à garder.

Il vaut mieux construire une fonction

Code :

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

for_all_mset : ('e -> bool) -> 'e mset -> bool

Telle que

Code :

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

for_all_mset f s renvoie vrai si f est vraie pour chaque élément de s et faux sinon

. Ca reste de l'ordre supérieur.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
# let subset_crt acc e s = acc && member e s
  ;;
val subset_crt : bool -> 'a -> 'a mset -> bool = <fun>
# subset_crt true (1, 4) s2;;
Characters 23-25:
  subset_crt true (1, 4) s2;;
                         ^^
Error: This expression has type int mset
       but an expression was expected of type (int * int) mset
       Type int is not compatible with type int * int
# s2;;
- : int mset = Cons ((1, 4), Cons ((5, 1), Cons ((7, 3), Nil)))

Ca ne me rassure pas pour mon examen...

Déjà, pour votre examen, rassurez-vous. Le problème que vous avez sur subset c'est que vous voulez utiliser un accumulateur, ce qui n'est pas logique donc vous cherchez une solution alambiquée pour rien

Sinon, vous refaites la même erreur : member prend un 'e, pas un ('e * int), il faut donc appeler : subset_crt true 1 s2;; même si, de toutes façons, l'accumulateur true est inutile.

[alexpand]

La formulation "appliquer un accumulateur acc" est malheureuse ;-)

Ok

Pourquoi renvoyer acc && member e s2 ? Si acc est vrai, autant renvoyer member e s2 et si acc est faux alors autant s'arrêter.

Je ne sais pas. En fait, je pense que je me perds un peu sur ce concept d'ordre supérieur

La fonction fold_mset est faite pour appliquer une opération sur l'ensemble des éléments d'UN ensemble.

Subset étant une opération sur deux ensembles qui renvoie un booléen, fold_mset n'est pas appropriée. Néanmoins, l'idée derrière fold_mset est à garder.

Il vaut mieux construire une fonction

Code :

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

for_all_mset : ('e -> bool) -> 'e mset -> bool

Telle que

Code :

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

for_all_mset f s renvoie vrai si f est vraie pour chaque élément de s et faux sinon

. Ca reste de l'ordre supérieur.

Ok, je vais voir. Merci encore

Déjà, pour votre examen, rassurez-vous. Le problème que vous avez sur subset c'est que vous voulez utiliser un accumulateur, ce qui n'est pas logique donc vous cherchez une solution alambiquée pour rien

Idem qu'avant: l'ordre supérieur n'est pas encore clair pour moi (vous avez dû vous en douter ).

Sinon, vous refaites la même erreur : member prend un 'e, pas un ('e * int), il faut donc appeler : subset_crt true 1 s2;; même si, de toutes façons, l'accumulateur true est inutile.

Arf oui, en effet! Je pense que c'est le stress des examens! Merci

[TchoubiTchoub]

Je ne sais pas. En fait, je pense que je me perds un peu sur ce concept d'ordre supérieur

Ah non ! Je ne peux accepter qu'on soit "perdu" sur l'ordre supérieur.

Revenons à la base de la base !

Lorsque vous écrivez

Code :

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

1
2
3
let main () = 
  let a = 3 in
  a + 2

a est une variable local à la fonction main. Jusque là, rien d'anormal.

Maintenant, on veut que main soit paramétrable donc on écrit

Code :

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

let main a = a + 2

Maintenant on voudrait que l'opération appliquée au paramètre soit aussi un paramètre !

On écrit donc

Code :

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

let main f a = f a

et pour revenir à la fonction précédente on peut donc écrire

Code :

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

1
2
3
let main f a = f a
let f = fun p -> p + 2 (* on peut aussi écrire let f p = p + 2 *)
let main a = main f a (* on peut aussi écrire let main = main f *)

En réalité, l'ordre supérieur c'est simplement que les fonctions sont des valeurs, on fait ce qu'on veut avec. On en crée, on en renvoie, on en passe en paramètre.

Ce n'est pas compliqué, c'est simplement qu'au lieu de penser qu'une fois une fonction écrite elle ne dépend que de ses paramètres qui sont des valeurs de base (entiers, chaînes de caractères, objets etc.), les valeurs de bases sont toutes celles que vous connaissez plus les fonctions.

Donc, par exemple, supposons que vous avez une liste d'éléments (strictement positifs) et vous voulez chercher le plus grand :

Code :

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

1
2
3
4
5
6
7
8
9
10
type 'a list = Nil | Cons of 'a * 'a list;;
let head = function Nil -> assert false | Cons (e, _) -> e::
val head : 'a list -> 'a = <fun>
 
let max_elt l =
  let rec mr acc = function
    | Nil -> acc
    | Cons (e, l') -> let acc = if e > acc then e else acc in mr acc l'
  in mr (head l) l;;
val max_elt : 'a list -> 'a = <fun>

Elle vous plaît, cette fonction ? Moi elle ne me plaît pas. Oui, bien sûr, on peut lui passer n'importe quelle liste en paramètre (l'opérateur ">" est polymorphe, vous pourriez donc lui donner une liste d'entiers comme de string comme de liste d'entiers, je vous invite à essayer ) mais supposons que je veuille définir mon propre ordre sur les éléments ? Par exemple, "ab" > "aaaa" car l'ordre sur les chaînes de caractères est l'ordre lexicographie. Mais moi je veux que ce soit un ordre basé sur la longueur des chaînes de caractères. Il faut donc que je réécrive la fonction comme ça :

Code :

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

1
2
3
4
5
6
let max_elt l =
  let rec mr acc = function
    | Nil -> acc
    | Cons (e, l') -> let acc = if (String.length e) > (String.length acc) then e else acc in mr acc l'
  in mr (head l) l;;
val max_elt : string list -> string = <fun>

Caramba ! C'est moche ! J'avais une fonctions polymorphe et maintenant je ne peux l'appliquer qu'à des listes de chaînes de caractères !

Mais, et l'ordre supérieur alors ?

Et si j'écrivais :

Code :

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

1
2
3
4
5
6
let max_elt cmp l =
  let rec mr acc = function
    | Nil -> acc
    | Cons (e, l') -> let acc = if cmp e acc > 0 then e else acc in mr acc l'
  in mr (head l) l;;
val max_elt : ('a -> 'a -> int) -> 'a list -> 'a = <fun>

Et pour faire ma fonction qui récupère la plus grande chaîne de caractères dans une liste il me suffit d'écrire :

Code :

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

1
2
3
4
5
let cmp_str s1 s2 = String.length s1 - String.length s2;;
val cmp : string -> string -> int = <fun>
 
let max_elt_stringlist = max_elt cmp_str
val max_elt_stringlist : string list -> string = <fun>

Voilà, max_elt reste polymorphe et en plus de lui donner une liste je lui donne la fonction de comparaison entre deux éléments de cette liste. C'est ça, l'ordre supérieur.