On définit ainsi la structure d'une liste : il s'agit d'une autre liste contenant le même nombre d'éléments mais ceux-ci sont triés et à chaque élément on a fait correspondre un nouvel entier de manière à ce que la nouvelle liste ne contienne aucun trou, en partant de 0. Par exemple, la liste [6;2;5;1;2;3;5;1;2;6] devient lorsqu'elle est triée [1;1;2;2;2;3;5;5;6;6]. On associe alors 0 au plus petit nombre, 1 au suivant, etc... Donc 1 devient 0, 2 devient 1, 3 devient 2, 5 devient 3 et 6 devient 4. La structure de la liste est finalement : [0;0;1;1;1;2;3;3;4;4].
Pour cela, on va utiliser l'algorithme suivant (mais on pourrait avoir d'autres stratégies) :
- on trie la liste
- on enlève les éléments en plusieurs exemplaires dans le résultat, ce qui crée une liste appelée « référence ».
- en utilisant référence, on crée une fonction qui à un entier associe son nouveau représentant. Il suffit pour cela de chercher la position de l'entier dans la référence.
- on applique cette fonction à tous les éléments de la liste triée.

1) Ecrire une fonction qui prend une liste qu'on suppose triée (et donc deux objets égaux sont toujours côte à côte) et qui rend la même liste, avec les éléments dans le même ordre mais ne contenant plus qu'un exemplaire de chaque (par exemple, [1;1;1;2;3;3] devient [1;2;3]).
On utilise une fonction auxiliaire récursive qui prend deux arguments : la liste « ok » des éléments qui doivent être dans le résultat et la liste « reste » des éléments qui restent à voir. On commence par appliquer cette fonction avec ok vide et reste contenant la liste à « épurer ». Puis à chaque étape :
   - si reste est vide, on a terminé et on rend la liste ok (renversée car on a pris tous les éléments dans le mauvais sens)
   - si reste ne contient qu'un élément, il est seul donc on peut le mettre dans ok
   - sinon, reste est de longueur au moins 2. On considère a son premier élément et b son deuxième élément. Si a = b, c'est un élément qui se répète donc on jette a et on appelle la fonction avec ok identique et la queue de reste. Si a est différent de b, il ne se répètera plus (la liste est supposée triée) donc on le met dans ok.
let enleve_redondances liste =
   let rec aux ok reste = match reste with
      |[] -> List.rev ok
      |[a] -> aux (a::ok) []
      |a::b::q -> if a = b then aux ok (b::q) else aux (a::ok) (b::q)
in aux [] liste;;

2) Ecrire une fonction compte qui reçoit une liste et un élément qui appartient à cette liste. La fonction rend la place de l'élément dans la liste, le premier élément de la liste étant numéroté 0, le second 1, etc... Ainsi, compte [1;2;3] 2;; doit rendre 1.
Solution

> Haut de la page