La partie compliquée concerne la représentation des notes. Puisque le nombre de matières est grand, et susceptible de changer d'année en année, on se contente de les identifier par une chaîne de caractère plutôt qu'un type ad-hoc. Par contre chaque candidat passe un petit nombre de matières, il n'est donc pas utile d'utiliser une structure de données compliquée pour mémoriser toutes les notes, une liste fait l'affaire.
Pour construire une structure de dictionnaire efficace, on utilise le foncteur Map.Make. Il prend pour argument une module contenant un type, le type des clés (ici les candidats), et une fonction de comparaison des clés.
On veut bien sûr éviter de réécrire un algorithme de tri, donc utiliser List.sort. Il faut donc construire une fonction de comparaison. Celle donnée en argument à notre sort ne compare pas les éléments de la liste, mais on peut transformer les éléments de la liste vers le type comparable. Un piège est de vouloir faire List.map by, car alors on perd les éléments. Ce qu'il faut c'est modifier la fonction de comparaison.
Il faut récupérer les notes des trois matières, les agréger, puis comparer et trier les étudiants avec. Cela suggère les fonctions suivantes.
On utilise un type inductif pour représenter l'arbre binaire. Chaque nœud contient trois informations d'après l'énoncé : la priorité, la valeur et la taille du sous-arbre. Pour clarifier on utilise un type pour les nœuds.
La taille est immédiatement disponible dans le nœud.
On doit récupérer les éléments dans l'ordre pour les mettre dans la liste. Le plus simple est donc d'utiliser les fonctions sur les files de priorité permettant d'extraire l'élément minimum. Par exemple, observe nous permet de procéder par filtrage par motif.
fold prend en plus une fonction et un état à retourner lorsque la file de priorité est vide. On ajoute donc ces deux arguments et on retourne l'état initial dans le premier cas. Pour le deuxième cas, on garde l'appel récursif, on remplace l'opération de construction de liste par l'appel à la fonction f et cela donne :
Ce n'est pas encore parfait, l'ordre des arguments de f n'est pas bon, et on applique f à l'élément minimum en fin de calcul (on veut le faire au début). On corrige donc :
On obtient une fonction très proche de celle définissant List.fold_left. Pour obtenir to_list, on redonne la fonction d'insertion en tête de liste (attention (::) n'est pas une fonction, on ne peut le passer en argument).
On peut par exemple tester que le nombre d'éléments varie correctement pour pop, push et merge.
Pour générer un booléen vrai avec probabilité $p$, il suffit de tirer un flottant entre $0$ et $1$ uniformément, et tester s'il est plus petit que $p$. float 1. est une générateur de flottants (et non un flottant). Il faut utiliser map pour modifier les valeurs générées pour en faire des booléens.
Même principe pour cette question.
Pour filtrer les éléments d'une liste par un test aléatoire, le plus simple est de procéder récursivement : on décide si on garde la tête, puis ce qu'on garde de la queue, et on retourne le résultat. L'appel récursif produit un générateur, on va donc devoir utiliser bind pour chaîner les décisions successives.
Pour ajuster le nombre d'éléments choisis, il faut connaitre les éléments sélectionnés et les éléments rejetés, ce qui demande de modifier filter.
On peut ensuite implémenter l'algorithme proposé :
On réutilise bipartition pour couper la liste.
On procède par étape sur chaque élément de la liste, on peut donc envisager une récursion. Il nous faut un argument de plus pour contenir la file de priorité avec les éléments choisis pour l'instant.
On peut encore améliorer cette algorithme est remarquant que la probabilité que la nouvelle priorité soit plus grande que celles des priorités des éléments encore dans la file de priorité est $\frac{k}{n+1}$. Ainsi, il n'est pas nécessaire de calculer les priorités, mais seulement de garder une collection des $k$ éléments choisis. L'algorithme qu'on obtient alors est appelé reservoir sampling.
