Discussion :

[prgasp77]

fold_left est un outil merveilleux quand on sait s'en servir. Tiens regarde :

Code :

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

1
2
List.fold_left (fun a _ -> succ a) 0 [5;3;9;4]
- : int = 4

Et hop, la fonction cardinal est faite .

L'idée est de comprendre que List.fold_left × [u1;u2;u3; ... u_n] est équivalent à (((u0 × u1) × u2) × ...) × u_n où × est un opérateur quelconque (ou plus généralement une fonction de type 'a -> 'b -> 'a).

[magodeoz]

Merci de ta réponse prgasp
Oula....Si je comprends bien, tu as pris 2 fonctions prédéfinies...
List.fold_left et succ qui donne le nombre suivant..
Mais moi il faut que j'écrive ma fonction fold_left donc ça ça va...
Mon accumulateur va être 0 si j'ai bien compris,la liste ok pas de prblème par contre je n'ai pas très bien compris pour la fonction...Je ne dois pas prendre ma fonction cardinal?

[prgasp77]

En relisant la partie 3 du sujet que tu nous as montré, je comprends qu'il faut réécrire les fonctions cardinal et autres en utilisant les fonctions de haut niveaux telles que List.fold_left.

D'où cardinal = List.fold_left (fun a _ -> succ a) 0.

Il te reste à faire la même chose avec cardinalmultiens, inclus, inclusmultiens, union, unionmultiens, intersection et intersectionmultiens .

Edit: cardinalmultiens est assez facile, une fois que tu as compris qu'il s'agit tout simplement de la somme des occurrences.

[magodeoz]

Ok :-)

Code :

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

1
2
3
4
let rec fold_left (f: 'a -> 'b ->'a) (acc: 'a) (l: 'b list): 'a =
  match l with
    [] -> acc
  | x::xs -> fold_left f (f acc x) xs ;;

Code :

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

let cardinal =fold_left (fun a _ -> succ a) 0 ;;

Code :

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

1
2
fold_left (fun a b -> succ a) 0 [5;3;9;4] ;;
- : int = 4

EDIT: ça marche en mettant "a" à la place de " 'a " et "b" à la place de "_".J'ai compris que je ne devais pas mettre les " ' " car déjà défini dans le fold_left...Pardon ^^

[prgasp77]

Je pense que tu peux utiliser la fonction déjà écrite List.fold_left plutôt que d'écrire ta version, mais ça fais jamais de mal après tout.

Concernant les a et les b, dans l'exemple que j'ai donné il s'agit de nom d'arguments et non de type. J'aurais pu écrire (fun left right -> succ left). L'underscore (_) sert à préciser l'existence d'un paramètre que l'on ne veut pas nommer car on ne l'utilise pas.

Aller au travail, il te reste 7 fonctions.

[magodeoz]

J'ai un peu de mal encore avec cette fonction.... J'aimerais bien tout comprendre :-)

Quand j'ai:
fold_left (fun a b -> succ a) 0 [5;3;9;4] ;;
Le b, si j'ai bien compris c'est les différentes valeurs de la liste mais le a concrètement c'est quoi?

[prgasp77]

J'ai un peu de mal encore avec cette fonction.... J'aimerais bien tout comprendre :-)

Quand j'ai:
fold_left (fun a b -> succ a) 0 [5;3;9;4] ;;
Le b, si j'ai bien compris c'est les différentes valeurs de la liste mais le a concrètement c'est quoi?

Je pense que tu raisonnes à l'envers. Caml est un langage assez dense, attention. Dans la ligne fold_left (fun a b -> succ a) 0 [5;3;9;4], il faut différencier l'appel à la fonction fold_left et la définition de la fonction anonyme fun a b -> succ a. Je m'explique.

1/ Définition de la fonction anonyme. Appelons là f

Code :

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

let f a b = succ a

f est une fonction qui renvoie le successeur de a, quelque soit b. Ainsi, f 5 0 = f 5 49 = f 5 -4 = 6.

2/ Utilisons f conjointement à fold_left.

Code :

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

fold_left f 0 [1;3;3;7]

Nous l'avons vu, cette expression est équivalente à f (f (f (f 0 1) 3) 3) 7 elle même équivalente à f (f (f 1 3) 3) 7 et à f (f 2 3) 7 et à f 3 7 et à 4.

[magodeoz]

Ah merci j'ai compris!!! :-) le a en fait ça va être mon accumulateur!
Si j'avais mis:
let cardinal =fold_left (fun a _ -> succ a) 1 ;;
fold_left (fun a b -> succ a) 1 [5;3;9;4] ;; ça m'aurait renvoyé int 5
car:f (f (f (f 1 1) 3) 3) 7 elle même équivalente à f (f (f 2 3) 3) 7 et à f (f 3 3) 7 et à f 4 7 et à 5. :-)

Bon je vais réfléchir à cardinalmultiens maintenant.... le souci que je vais avoir c'est que ma liste va être de la forme:
[(1,2);(2,3);(3,4)]....
Donc le cardinal va être égal aux occurences....
Bon je vais essayer je vous tiens au courant ^^

[magodeoz]

J'ai tenté :
let cardinalmultiens =List.fold_left (fun _ (a,b) -> b) 0 ;;
List.fold_left (fun _ (a,b) -> b) 0 [(3,1);(2,3)];;
- : int = 3
Mais ça ne marche pas....

[prgasp77]

Tu n'en est pas loin. Mais remarque que dans ton essai précédent, tu retournes b sans le modifier. Ce qui fait que tu obtiens en sortie la valeur du membre de droite du dernier élément de la liste (3), quelque soit les autres éléments de la liste et l'initialiseur (0).

Alors que toi, tu veux la _____ des membres de droite des éléments de ta liste.

[magodeoz]

Oui il faudrait que j'ai la somme des "b" :-) J'imagine qu'il faut stocker les valeurs de b dans l'accumulateur n'est ce pas...?
Je vais voir si j'arrive à faire ça...

[magodeoz]

J'imagine que le début est de la forme:

Code :

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

letcardinalmultiens=List.fold_left (fun a (_,b)->

mais je peine à trouver comment renvoyer la somme des b....

[prgasp77]

Oui le début est bon. Mais tu ne penses pas assez « récursif ». La somme des occurrences de la liste n'est que l'addition de la première occurrence avec la somme des occurrences suivants

[magodeoz]

Je vais avoir un autre problème.... ^^ cardinalmultiens doit me renvoyer un couple de int.... Donc mon accumulateur va être (0,0)....
Je pense que je n'en suis pas loin...

Code :

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

1
2
3
4
let rec fold_left (f: 'a -> 'b ->'a) (acc: 'a) (l: 'b list): 'a =
  match l with
    [] -> acc
  | x::xs -> fold_left f (f acc x) xs ;;

Code :

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

let f(x,y:'e*int)(a,z:int*int):int*int=(a+1,z+y);;

Code :

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

let cardinalmultiens(a:('e*int)list):int*int=fold_left f (0,0)(a);;

Mais quand je teste....:

Code :

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

1
2
cardinalmultiens [(2,3);(3,2);(4,1)];;
- : int * int = (5, 6)

Or c'est sensé me renvoyer (3,6)...Pourriez-vous m'indiquer où est l'erreur? 0_o

[Ptival]

Haha, drôle d'erreur. Dans ta fonction f, tu confonds l'accumulateur et l'élément courant. Du coup tu incrémentes l'élément courant au lieu d'incrémenter l'accumulateur !

[magodeoz]

Débile que je suis....

Code :

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

1
2
3
4
let rec fold_left (f: 'a -> 'b ->'a) (acc: 'a) (l: 'b list): 'a =
  match l with
    [] -> acc
  | x::xs -> fold_left f (f acc x) xs ;;

Code :

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

let f(x,y:'e*int)(a,z:int*int):int*int=(x+1,z+y);;

Code :

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

let cardinalmultiens(a:('e*int)list):int*int=fold_left f (0,0)(a);;

Code :

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

1
2
cardinalmultiens [(2,3);(3,2);(4,1)];;
- : int * int = (3, 6)

[magodeoz]

Bon je vais essayer inclus maintenant....J'appréhende déjà

[prgasp77]

T'es sur la bonne voie. Mais petit conseil, pour une meilleur lisibilité, ne donne pas le type des arguments de tes fonctions :

Code Ocaml :

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

1
2
3
4
5
let cardinalmultiens = List.fold_left (
   fun (occurrences_simples, occurrences_totales) (occ,_) ->
      (succ occurrences_simples, occ + occurrences_totales)
   ) (0,0)
;;

Code Ocaml :

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

1
2
cardinalmultiens [(1,'u'), (3, 't'), (2, 'd')]
- : val (3, 6) : int * int

C'est quand même plus lisible non ?

[magodeoz]

Oui en effet...Bien plus lisible Je manque encore de pratique en ocaml et j'aime bien marqué le type des arguments de la fonction pour m'y retrouver.Je manque encore d'automatismes ou plutôt j'en ai trop (de mauvais), tout dépend du point du vue

Pour inclus je suis en panne sèche totale....

[magodeoz]

J'ai à la base:

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
let rec cardinal (l:'a list) :int=
  match l with
  |a::b->1+cardinal (b)
  |[]->0;;
 
let rec appartient (x : 'a) (l : 'a list) : bool =
  match l with |a::ensemble2 -> if(a = x) then true else appartient (x) (ensemble2)
               |[] -> false
;;
let inclus ((e1, e2) : 'a list * 'a list) : bool =
  if (cardinal (e1)<=cardinal (e2)) then
   match e1 with|a :: ensemble2 -> appartient (a) (e2)= true
                |[] -> true
  else match e2 with |b::ensemble3 -> appartient (b) (e1) = true
                     |[] -> true
 ;;