Cette liste est très connue : elle part du nombre 1. Puis à chaque étape, on trouve le terme suivant en décrivant le dernier. Par exemple, partant de « 1 », le deuxième terme est la description du premier : celui-ci s'écrit avec une fois le chiffre « 1 » donc le deuxième terme est « 11 ». Il s'écrit avec deux fois le chiffre « 1 » donc le terme suivant est « 21 ». Ce dernier s'écrit avec une fois le chiffre « 2 » puis une fois le chiffre « 1 » donc le terme suivant est « 1211 », etc....
On va créer ici une fonction qui calcule le n-ième terme de la suite. On représentera chaque terme par une liste d'entiers.

1) Ecrire une fonction « prefixe » qui prend une liste d'entiers et qui rend le premier terme de la liste, le nombre de termes égaux au début de cette liste et le reste de la liste. Par exemple, prefixe [2;5;4;7;8;2] doit rendre le triplet (2,1,[5;4;7;8;2]) et prefixe [1;1;1;8] doit rendre le triplet (1,3,[8]). On suppose que la liste est non vide.
On utilise une fonction auxiliaire récursive qui prend trois arguments : la liste des entiers qu'on n'a pas encore regardés, le premier élément de la liste de départ (celui qui nous intéresse) et le nombre de tels entiers qu'on a déjà trouvés. La fonction aux fonctionne donc ainsi :
- si la liste li est vide, on a terminé donc on rend premier, nombre et la liste vide.
- sinon, il y a deux cas :
   - si le premier élément de la liste restante est égal à premier, on doit continuer et on rappelle notre fonction avec (List.tl li), premier et (nombre + 1)
   - sinon, on a fini donc on rend premier, nombre et la liste restante (y compris le premier élément qu'on a testé).
On doit donc appeler la fonction auxiliaire avec li valant la queue de la liste étudiée, premier valant le premier élément de la liste et nombre valant 1 (car on doit compter le premier élément qu'on a enlevé).
Remarquons qu'on pourrait aussi l'appeler avec l (List.hd l) 0.
let prefixe l =
   let rec aux li premier nombre = match li with
       |[] -> (premier,nombre,[])
       |t::q -> if t = premier then aux q premier (nombre+1) else (premier,nombre,(t::q))
in aux (List.tl l) (List.hd l) 1;;
On a été obligé de supposer la liste non vide pour ne pas déclencher une erreur avec l'appel « List.hd l ».

2) En déduire la fonction « suivant » qui reçoit un terme de notre suite et qui rend le terme suivant.
Solution

> Haut de la page