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.
On se sert de la fonction précédente : si notre liste est vide, le terme suivant est également vide. Sinon, on calcule le triplet (a,n,r) correspondant à préfixe l. On obtient que la liste est composée de n fois le chiffre a, suivis d'une autre liste r. Le terme suivant contient donc le chiffre n, puis a, puis le terme suivant correspondant à r (d'où l'appel récursif).
let rec suivant l = match l with
   |[] -> []
   |_ -> let (a,n,r) = prefixe l in n::a::(suivant r);;

3) Ecrire une fonction « affiche » qui dans la boucle interactive reçoit un terme de la suite (c'est-à-dire une liste d'entiers), qui affiche ce terme à l'écran (affiche [1;2;1;1];; doit afficher 1211) et passe à la ligne. On pourra utiliser les fonctions print_int et print_newline.
Solution

> Haut de la page