Ensembles en ocaml

n12345 · May 2021

Bonjour, j'ai une petite question :
je travaille sur l'écriture des fonctions "de base" sur les ensembles en ocaml (insertion suppression intersection etc.). Pour ça, on définit le type :

type ensemble = int list

et j'écris ma fonction insertion d'un élément v dans un ensemble e : 'a -> ensemble -> ensemble

let rec insertion_ens v e = match e with 
                       | [] -> [v]
                       | t::q -> if t=v then e else insertion_ens v q ;;

Cette fonction n'a pas le bon typage puisque sa signature est : 'a -> 'a list -> 'a list.
Comment modifier le typage de cette fonction qui n'est pas le bon ? Lorsqu'on travaille sur des types comme :
type paire_dentiers = { a : int; b : int };; , on peut faire appel à un des champs (par exemple ici paire_dentiers.a ) mais dans notre cas, c'est impossible.

Merci de votre aide ! (Je m'excuse de présenter mon texte de cette manière, si quelqu'un peut m'expliquer comment présenter du texte informatique de façon correcte je suis preneur

)

[Utiliser le bouton "Code" (5ème par la droite au dessus de la fenêtre d'édition. AD]

Calli · May 2021

Bonjour,
Je ne suis pas sûr d'avoir bien compris le problème. Ta fonction devrait fonctionner quand v est un "int" et e est un "int list" ou "ensemble". N'est-ce pas le principal ? À la limite peut écrire le truc ci-dessous pour forcer le type int -> int list -> int list (où la dernière ligne n'est jamais activée), mais je ne vois pas l'intérêt.

let rec insertion_ens v e = match e with
| [] -> [v]
| t::q -> if t=v then e else insertion_ens v q
| [0] -> [0] ;;

PS: Pour écrire du code sur le forum, il faut cliquer sur le 5e bouton en partant de la droite dans l'éditeur de message (un carré blanc avec des petites lignes dedans).

Calli · May 2021

D'ailleurs, il y a un oubli dans ton code, ça devrait être

let rec insertion_ens v e = match e with
| [] -> [v]
| t::q -> if t=v then e else [color=#EE0000][b]t::[/b][/color]insertion_ens v q ;;

n12345 · May 2021

C'est vrai, merci pour l'oubli et pour l'écriture du texte !
Ma fonction marche bien pour une int list, mais pourquoi sa signature n'est pas 'a -> ensemble -> ensemble ? Je cherchais en effet une méthode pour forcer le typage et avoir la signature recherchée.. Je vais essayer ce que vous m'avez proposé même si c'est vrai que la ligne que vous avez rajoutée dans la reconnaissance de motifs n'apporte rien au code..

Merci !

(PS : j'ai essayé votre modification et finalement la signature de la fonction est : 'a -> int list -> int list donc est-ce possible d'obtenir 'a -> ensemble -> ensemble ou par définition du type ensemble, ce sont les mêmes signatures ?

Calli · May 2021

Je ne suis pas sûr de moi, mais comme "ensemble" a été défini comme égal à "int list", les signatures "int -> ensemble -> ensemble" et "int -> int list -> int list" sont peut-être égales.

En revanche, tu ne pourras pas obtenir la signature " 'a -> ensemble -> ensemble" puisque tes ensembles contiennent forcément des entiers.

Calli · May 2021

Je n'avais pas vu ton PS. Moi quand je teste

let rec insertion_ens v e = match e with
| [] -> [v]
| t::q -> if t=v then e else t::insertion_ens v q
| [0] -> [0] ;;

j'obtiens la signature int -> int list -> int list et non 'a -> int list -> int list.

Ensembles en ocaml

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 20