Exercice 1 : Random

On se propose d'écrire une fonction pour permuter aléatoirement les éléments d'une liste. Plusieurs méthodes existent, ici nous allons nous inspirer du tri rapide, mais avec une fonction de comparaison en quelque sorte aléatoire. L'algorithme procède ainsi :

• partitionner la liste en deux listes. Chaque élément est placé avec la même probabilité dans une des deux listes,
• permuter aléatoirement les deux listes par induction,
• concaténer les deux listes ainsi mélangée.

Écrire cet algorithme en utilisant la fonction Random.bool.

Exercice 2 : Enlever les éléments dupliqués d'une liste.

Étant donné une liste de $n$ entiers, on souhaite retirer les doublons de cette liste, de sorte que chaque entier apparaisse au plus une fois.

• donner un algorithme de complexité $O(n^2)$.
• on parcoure maintenant la liste de gauche à droite, en gardant les entiers déjà lus dans une structure d'ensemble (Set). Écrire cet algorithme. Quel est sa complexité ?
• Faire de cet algorithme un foncteur, pour l'utiliser sur des listes de n'importe quel type ordonné.

Exercice 3 : Fold sur les arbres.

Nous avons vu que le module Set propose une fonction fold, et aussi que les éléments de type Set.t sont des arbres binaires de recherches. Dans cet exercice, nous demandons comment est codé Set.fold, en regardant le cas des arbres binaires de recherche sur les entiers.

Coder la fonction suivante en utilisant une récurrence :

Dans la documentation, il est précisé que Set.foldapplique une fonction sur les éléments pris par ordre croissant. Faire de même.

Exercice 4 : Compter les mots d'un roman

Écrire un programme qui lit l'entrée standard et compte le nombre de mots distincts. On considère qu'un mot est une suite de caractères entre deux espacements. Pour cela on utilisera la fonction Scanf.scanf " %s".

Attention, lorsque cette fonction arrive en fin de l'entrée, la chaîne lue est "", mais elle ne lance pas d'exceptions.