TD 1, corrigé de l'exercice 4

1   Version avec des chaînes de caractères

On utilisera ici la fonction sous_chaîne vue en cours.

Question 1.1   

#let rec calc_préfixe = function str ->
   if str = "" then 0 else 
   if string_length str = 1 then 1 else 
   if str.[0] = str.[2] then 1 + (calc_préfixe (sous_chaîne str 2)) else 1;;
calc_préfixe : string -> int = <fun>
Question 1.2   

#let rec genere_ligne = function str ->
   if str = "" then "" else
      let nb = calc_préfixe str in
        (string_of_int nb) ^ " " ^ (sub_string str 0 2) ^
        (genere_ligne (sous_chaîne str (2 * nb)));;
genere_ligne : string -> string = <fun>
Question 1.3   

#let rec do_it = function p -> function str ->
   if p = 0 then str ^ " \n" else
     let str2 = genere_ligne str in  str ^ " \n" ^ (do_it (p-1) str2);;
do_it : int -> string -> string = <fun>
#
 let genere = function k ->
   if k <= 0 then failwith "k doit etre strictement positif" 
   else do_it (k-1) "1 ";;
genere : int -> string = <fun>
Question 1.4   

#let ecrit_suite = function k -> print_string (genere k);;
ecrit_suite : int -> unit = <fun>

Remarques :
  1. Pour une version efficace de ces fonctions, il faudrait par exemple passer les longueurs de chaîne argument en paramètre et la tenir à jour au fur et à mesure des appels récursifs pour éviter de re-parcourir la chaîne à chaque appel.
  2. La fonction calc_préfixe n'a pas besoin d'être récursive puisqu'il n'y aura jamais de suite de chiffres identiques de longueur supérieure à 3, mais une version non récursive n'est pas valable sans la démonstration de la propriété sur laquelle elle s'appuie.

2   Version avec des listes

Question 2.1   

#let rec calc_préfixe = function lst ->
   match lst with
   | [] -> 0
   | [x] -> 1
   | x1::x2::l -> if x1 = x2 then 1 + (calc_préfixe (x2::l)) else 1;;
calc_préfixe : 'a list -> int = <fun>
Question 2.2   

#let rec génère_ligne = function lst ->
   if lst = [] then [] else
   let nb = calc_préfixe lst in
     nb::(hd lst)::(génère_ligne (iter nb tl lst));;
génère_ligne : int list -> int list = <fun>
Remarque : Les fonctions hd et tl sont les noms prédéfinis des fonctions tête et reste du cours; iter est la fonction d'itération définie dans le cours sur l'ordre supérieur; iter n tl lst est la liste lst privée de ses n premiers éléments. On aurait pu écrire directement cette fonction de la façon suivante : 

#let rec reste_n = function n -> function lst ->
   if n = 0 then [] else reste_n (n-1) (tl lst);;
reste_n : int -> 'a list -> 'b list = <fun>
Question 2.3   

#let rec génère = function k -> 
   if k = 1 then [[1]] else 
     let res = génère (k-1) in
       (génère_ligne (hd res))::res;;
génère : int -> int list list = <fun>
Question 2.4   On utilise ici la séquence dénotée par le point virgule « ; », les fonctions print_int et print_string et l'itérateur do_list qui répète une action sur tous les éléments d'une liste (à l'instar de map qui retourne le résultat de l'application de la même fonction à tous les éléments d'une liste). 

#let rec écrit_suite = function k ->
   do_list (function lst -> 
     do_list (function k -> print_int k; print_string " ") lst;
     print_newline ()) 
   (génère k);;
écrit_suite : int -> unit = <fun>
Ce document a été traduit de LATEX par HEVEA.