PRFO23 : TP3

Exercice 1 : Interface des ensemble

Dans un fichier set.mli écrire un interface pour les ensembles, avec un type abstrait polymorphe pour les ensembles et des valeurs pour

• l'ensemble vide
• le test de vacuité
• le cardinal
• le test d'appartenance
• l'ajout dans un ensemble
• l'union de deux ensembles
• l'intersection de deux ensembles
• la suppression dans un ensemble
• l'égalité entre deux ensembles
• le map d'une fonction sur un ensemble
• le fold d'une fonction sur un ensemble et un accumulateur

Exercice 2 : Implémentation à l'aide de listes sans doublons

Dans un fichier set.ml, implémenter les ensembles à l'aide de listes sans doublons.

Exercice 3 : Utilisation, triplets pythagoriciens

Un triplet pythagoricien est un triplet d'entiers naturels distincts x, y et z tels que x² + y² = z².

On cherche à construire toutes les façons possibles de découper l'ensemble des entiers entre 1 et un n fixé en deux ensembles N1 et N2 tels que ni N1 ni N2 ne contiennent de triplet pythagoricien. Par exemple, si 3 et 5 sont dans N1, alors 4 est forcément dans N2.

Dans un fichier pythagorician.ml :

1. Écrire une fonction de type int Set.set -> unit qui affiche un ensemble d'entiers sur la sortie standard, de la forme { x1 x2 ... xn }. On utilisera un fold.
2. Écrire une fonction de type ('a -> bool) -> 'a Set.set -> bool qui teste si un prédicat est vrai pour tous les éléments d'un ensemble.
   Dans un premier temps, on pourra faire un simple parcours de l'ensemble à l'aide du fold.
   Dans un deuxième temps, on utilisera une exception pour sortir plus rapidement dans le cas où un contre-exemple est trouvé.
3. Écrire une fonction qui prend trois entiers x, y et z en entrée et qui teste si x est strictement plus petit que y et si x² + y² = z².
4. Écrire une fonction de type int Set.set -> int -> bool qui teste si un entier peut être rajouté à un ensemble sans qu'il n'y ait de triplet pythagoricien dans le nouvel ensemble. L'entier ajouté sera supposé plus grand que les éléments de l'ensemble.
5. Écrire une fonction int -> (int Set.set * int Set.set) list qui prend un entier n en paramètre et qui retourne la liste de toutes les façons de couper {1; ... ; n} en deux sans triplets pythagoriciens.
   On procédera ainsi :
   • Si n = 1, on retourne [ { 1 }, { } ]
   • Sinon, on calcule récursivement toutes les façons de couper {1; ...; n-1}.
   • Pour chacune de ses façons N1, N2 :
     • on teste si on peut ajouter n dans N1, si oui on rajoute N1 ∪ { n }, N2
     • on teste si on peut ajouter n dans N2, si oui on rajoute N1, N2 ∪ { n }
6. Ajouter du code pour lire un entier sur l'entrée standard, calculer les partitions possibles pour cette entier, et les afficher sur la sortie standard.