Consolidation

Rappels des traits syntaxiques qui doivent vous évoquer quelque-chose.

\disablelispcomment
(* commentaire *)

let VAR = EXPRESSION;;          définition globale 

let FUN VAR+ = EXPRESSION;;     définition globale de fonction

let DEFINITION                  codéfinition globale
[and DEFINITION]* ;;

let rec DEFINITION              codéfinition récursive globale
[and DEFINITION]* ;;

En ce qui concerne les expressions, on trouve:

\disablelispcomment
let [rec] DEFINITION [and DEFINITION]*   définition locale
in EXPRESSION

if EXPRESSION_BOOLEENNE then EXPRESSION  alternative
else EXPRESSION

( EXPRESSION [EXPRESSION]* )             appel de fonction

EXPRESSION OPERATEUR-INFIXE EXPRESSION   opération binaire

function VAR -> EXPRESSION               création de fonction unaire

match EXPRESSION with                    filtrage explicite
    PATTERN -> EXPRESSION
[ | PATTERN -> EXPRESSION ]*
end

for VAR = EXPRESSION to EXPRESSION do   boucle
EXPRESSION [ ; EXPRESSION]*
done

Exercice 17

Écrire une fonction compter qui prend un entier et une liste d'entier et compte les occurrences de ce premier dans cette dernière.

Solution 17

let rec compter n ln =
  if ln = [] then 0
  else if hd ln = n then 1 + compter n (tl ln)
       else compter n (tl ln);;
compter : 'a -> 'a list -> int = <fun>
compter 1 [1;2;3;44;5;6;1;34;56;82;1;0];;
- : int = 3

On peut aussi écrire la même chose avec du filtrage.

let rec compter n = function
  []   -> 0
| h::l -> let resultat = compter n l in
          if h = n then 1+resultat else resultat;;
compter : 'a -> 'a list -> int = <fun>
compter 1 [1;2;3;44;5;6;1;34;56;82;1;0];;
- : int = 3

Notez que l'on ne peut écrire n à la place de h. Ce qui est requis dans un filtre c'est une variable à lier et non une valeur à vérifier. Le test h=n apparaît donc peu après. Observez la mise en facteur de l'appel récursif à compter.

Exercice 18

Écrire une fonction au_moins_deux retournant les entiers apparaissant au moins deux fois dans une liste d'entiers. Aucun ordre n'est exigé dans la réponse, les répétitions y sont également permises.

Solution 18

let rec au_moins_deux = function
  []     -> []
| n :: l -> let reste = au_moins_deux l in
            if mem n l
            then n :: reste
            else reste;;
au_moins_deux : 'a list -> 'a list = <fun>
au_moins_deux [1; 2; 3; 1; 1; 4; 1; 2; 2; 1; 5; 9; 2; 3; 1; 1; 9];; 
- : int list = [1; 2; 3; 1; 1; 1; 2; 2; 1; 9; 1]

La fonction prédéfinie mem teste l'appartenance d'un élément à une liste. Cette définition est quadratique du fait que mem et au_moins_deux parcourent chacune tous les segments terminaux de la liste.

Exercice 19

Écrire la fonction exactement_deux qui extrait d'une liste de nombres ceux qui y apparaissent exactement deux fois. La solution ne doit pas comporter de répétition.

Solution 19

let rec exactement_deux l =
  let rec parcourir deja_vus doublons trop_vus = function
    []     -> doublons
  | n :: l -> if mem n trop_vus
              then parcourir deja_vus doublons trop_vus l
              else if mem n doublons
                   then parcourir deja_vus 
                                  (except n doublons) 
                                  (n :: trop_vus)
                                  l
                   else if mem n deja_vus
                        then parcourir (except n deja_vus)
                                       (n :: doublons)
                                       trop_vus
                                       l
                        else parcourir (n :: deja_vus)
                                       doublons
                                       trop_vus
                                       l
in parcourir [] [] [] l;;
exactement_deux : 'a list -> 'a list = <fun>
exactement_deux [1; 2; 3; 1; 1; 4; 1; 2; 2; 1; 5; 9; 2; 3; 1; 1; 9];; 
- : int list = [9; 3]

La fonction mem (pour member) teste si son premier argument apparaît dans la liste de second argument.

Exercice 20

Écrire la fonction xpl dont voici un exemple:

xpl [1; 2; 3; 4];;
- : int list list = [[1]; [1; 2]; [1; 2; 3]; [1; 2; 3; 4]]

Solution 20

Il en existe de multiples variantes. En voici une:

let xpl l = 
  let rec xpl_internal l = function
    []      -> l
  | v :: ll -> xpl_internal (map (function u -> v :: u)
                                 ([]::l) )
                            ll
in xpl_internal [] (rev l);;
xpl : 'a list -> 'a list list = <fun>

La fonction rev (pour reverse) renverse les termes d'une liste.

Exercice 21

Soit le générateur linéaire suivant:

let generateur_lineaire a b c =
  function n -> (a * n + b) mod c;;
generateur_lineaire : int -> int -> int -> int -> int = <fun>

On peut alors construire une sorte de dé à jouer, ainsi:

let de = generateur_lineaire 1 2 6;;
de : int -> int = <fun>

Mais il n'est pas très aléatoire comme le montre:

for i = 1 to 20 do
  print_int (de i);
  print_string " "
  done;;
3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 - : unit = ()

Écrire le prédicat boucle qui teste si un tel dé boucle ou plus généralement si les termes de la suite f(i) bouclent? On utilisera la méthode de Floyd qui consiste à comparer les n ème et 2n ème lancers de dé ou termes de la suite. En effet la suite boucle ssi il existe n tel que f(n)=f(2n).

Solution 21

let boucle f x =
  let rec iterer xn x2n =
     if xn = x2n then true
     else iterer (f xn) (f (f x2n))
  in iterer x (f x);;
boucle : ('a -> 'a) -> 'a -> bool = <fun>
boucle de 1;;
- : bool = true

On peut aussi user d'exceptions pour programmer cette fonction.

let boucle_avec_exception f x =
  let rec iterer xn x2n =
     if xn = x2n then failwith "boucle"
     else iterer (f xn) (f (f x2n))
  in try iterer x (f x)
     with Failure "boucle" -> true;;
boucle_avec_exception : ('a -> 'a) -> 'a -> bool = <fun>
boucle de 1;;
- : bool = true

Noter les emplois de try pour contrôler l'irruption d'une exception et de failwith pour signaler une exception.

Exercice 22

Modifier la fonction précédente de telle sorte qu'elle retourne un élément du cycle trouvé. On utilisera un générateur du second ordre:

let generateur_second_ordre a b c d =
   function n -> (a * n * n + b * n + c) mod d;;
generateur_second_ordre : int -> int -> int -> int -> int -> int = <fun>
let f = generateur_second_ordre 23 12 31 67;;
f : int -> int = <fun>

Solution 22

let boucle_et_trouver_element_du_cycle f x0 =
  let rec iterer xn x2n =
     if xn = x2n then xn
     else iterer (f xn) (f (f x2n))
  in iterer x0 (f x0);;
boucle_et_trouver_element_du_cycle : ('a -> 'a) -> 'a -> 'a = <fun>
boucle_et_trouver_element_du_cycle de 1;;
- : int = 5
boucle_et_trouver_element_du_cycle f 15;;
- : int = 39

Exercice 23

Modifier encore une fois la précédente fonction de manière qu'elle retourne la liste des entiers composant le premier cycle trouvé.

Solution 23

On recherche un terme d'un cycle puis l'on construit le cycle tout entier à partir de lui.

let boucle_et_trouver_cycle f x0 =
  let rec enoncer les_x =
    let xn = f (hd les_x) in
     if mem xn les_x
     then let rec extrait_cycle x liste =
            if x = hd liste then [x]
            else (hd liste)::(extrait_cycle x (tl liste)) in
          rev (extrait_cycle xn les_x)
     else enoncer (xn::les_x) in
  enoncer [x0];;
boucle_et_trouver_cycle : ('a -> 'a) -> 'a -> 'a list = <fun>
boucle_et_trouver_cycle de 1;;
- : int list = [1; 3; 5]
boucle_et_trouver_cycle f 15;;
- : int list = [39]

Exercice 24

Toutes ces fonctions ont une structure quasiment identique: elles sont paramétrables par la condition de fin et le traitement final. Abstraire les fonctions précédentes en la fonction jusque_a de signature:

       jusque_a predicat traitement f x0

Puis définir, à l'aide de jusque_a, les fonctions boucle et boucle_et_trouver_element_du_cycle.

Solution 24

let rec jusque_a predicat traitement f x0 =
  let rec iterer xn x2n =
     if predicat xn x2n then traitement xn
     else iterer (f xn) (f (f x2n))
  in iterer x0 (f x0);;
jusque_a : ('a -> 'a -> bool) -> ('a -> 'b) -> ('a -> 'a) -> 'a -> 'b = <fun>
let boucle f = 
  jusque_a (prefix =) (function xn -> true) f;;
boucle : ('a -> 'a) -> 'a -> bool = <fun>
let boucle_et_trouver_element_du_cycle f =
  jusque_a (prefix =) (function xn -> xn) f;;
boucle_et_trouver_element_du_cycle : ('a -> 'a) -> 'a -> 'a = <fun>

On notera l'emploi du mot-clef prefix qui permet de parler de la fonction =

Exercice 25

Utiliser la méthode de Brent pour savoir si une fonction boucle. Elle permet de rechercher un élément de cycle plus petit que la méthode de Floyd. Elle revient à comparer f(0) avec les deux suivants f(1) et f(2), puis f(2) avec les quatre suivants f(3), f(4), f(5), f(6), puis f(6) avec les huit suivants f(7) ...

Solution 25

let trouver_par_Brent f x0 =
  let rec essayer_a_partir xn max =
    let rec suivant xni delta =
       if xn = xni then xn
       else if delta < max then suivant (f xni) (delta+1)
            else essayer_a_partir xni (2*max)
    in suivant (f xn) 1
  in essayer_a_partir x0 2;;
trouver_par_Brent : ('a -> 'a) -> 'a -> 'a = <fun>

Exercice 26

Écrire une fonction recherchant aléatoirement des diviseurs d'un nombre. Comme générateur aléatoire, on pourra prendre:

let alea n = generateur_second_ordre 1 0 1 n;;
alea : int -> int -> int = <fun>
for i = 1 to 20 do
  print_int (alea 100 i);
  print_string " "
  done;;
2 5 10 17 26 37 50 65 82 1 22 45 70 97 26 57 90 25 62 1 - : unit = ()

Solution 26

let cherche_diviseur n =
  let engendre = alea n in
    let rec essaye nombre =
      let gcd = pgcd n nombre in
      if gcd = 1 then essaye (engendre nombre)
      else nombre
    in essaye 2;;
cherche_diviseur : int -> int = <fun>
cherche_diviseur 48;;
- : int = 2

Exercice 27

Modifier la fonction précédente pour utiliser la méthode de Floyd-Pollard.

Solution 27

let cherche_diviseur_par_Floyd_Pollard n =
  let engendre = alea n in
    let rec essaye xn x2n =
      if xn = x2n then 0
      else let gcd = pgcd (abs(xn-x2n)) n in
           if gcd = 1 then essaye (engendre xn) (engendre (engendre x2n))
           else gcd in
    essaye 2 (engendre 2);;
cherche_diviseur_par_Floyd_Pollard : int -> int = <fun>
cherche_diviseur_par_Floyd_Pollard 78;;
- : int = 3
cherche_diviseur_par_Floyd_Pollard 1483;;
- : int = 0

On retourne ici zéro lorsque l'on détecte que le générateur aléatoire boucle.