TD n°2 : Fonctions et récursivité

Exercice 1 : Définition de fonctions

In [1]:
(* Évaluation en `0` *)
let fonction1 = fun f -> f 0
Out[1]:
val fonction1 : (int -> 'a) -> 'a = <fun>
In [2]:
(* Même fonction ; syntaxe différente *)
let fonction2 f = f 0
Out[2]:
val fonction2 : (int -> 'a) -> 'a = <fun>
In [3]:
(* Somme de deux fonctions *)
let fonction3 f g = fun x -> (f x) + (g x)
Out[3]:
val fonction3 : ('a -> int) -> ('a -> int) -> 'a -> int = <fun>
In [4]:
(* Même fonction ; syntaxe différente *)
let fonction4 f g x = (f x) + (g x)
Out[4]:
val fonction4 : ('a -> int) -> ('a -> int) -> 'a -> int = <fun>
In [5]:
(* Ajoute l'identité à une fonction qui doit alors être de type int -> int *)
let fonction5 = fonction3 (fun x -> x)
Out[5]:
val fonction5 : (int -> int) -> int -> int = <fun>
In [6]:
(* Identité fonctionnelle *)
let fonction6 = fun f -> fun x -> f x
Out[6]:
val fonction6 : ('a -> 'b) -> 'a -> 'b = <fun>
In [7]:
(* Même fonction ; syntaxe différente *)
let fonction7 f = fun x -> f x
Out[7]:
val fonction7 : ('a -> 'b) -> 'a -> 'b = <fun>
In [8]:
(* Même fonction ; syntaxe différente *)
let fonction8 f x = f x
Out[8]:
val fonction8 : ('a -> 'b) -> 'a -> 'b = <fun>

Exercice 2 : Composition

In [9]:
let compose f g = fun x -> f (g x)
Out[9]:
val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
In [10]:
(* Autre syntaxe *)
let compose f g = 
  let f_o_g x =
    f (g x)
  in
  f_o_g
Out[10]:
val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>

Exercice 3

In [11]:
(* 1. et 3. *)
let add x y = x + y
Out[11]:
val add : int -> int -> int = <fun>
In [12]:
(* 2. *)
let evaluation_en_zero f = (f 0) + 0
Out[12]:
val evaluation_en_zero : (int -> int) -> int = <fun>

Exercice 4 : Typage

In [13]:
let f1 n m = if n = m then n else m
Out[13]:
val f1 : 'a -> 'a -> 'a = <fun>
In [14]:
let f2 x y = let z = x + 1 in y || z > 10
Out[14]:
val f2 : int -> bool -> bool = <fun>
In [15]:
let f3 x y = x y
Out[15]:
val f3 : ('a -> 'b) -> 'a -> 'b = <fun>

f3 est l'identité fonctionnelle, c'est-à-dire l'identité, mais qui ne peut s'appliquer que sur des fonctions. C'est aussi la fonctionnelle "application" qui prend en entrée une fonction f et un élément x et qui renvoie l'évaluation (au sens mathématique) de f en x.

In [16]:
let f4 x y z = (x y) z
Out[16]:
val f4 : ('a -> 'b -> 'c) -> 'a -> 'b -> 'c = <fun>

f4 est encore l'identité, mais pour des fonctions avec trois flèches (au moins) et c'est aussi la fonction "application" d'une fonction à deux arguments (curryfiée).

In [17]:
let f5 x y z = x (y z)
Out[17]:
val f5 : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>

Avec f5 on retrouve la composition de fonctions $(f, g) \rightarrow f \circ g$

In [18]:
let f6 x y z = x y z
Out[18]:
val f6 : ('a -> 'b -> 'c) -> 'a -> 'b -> 'c = <fun>

f6 est exactement f4, sans les parenthèses implicites.

In [19]:
let f7 (x, y, z) = fun x -> (x, y, z)
Out[19]:
val f7 : 'a * 'b * 'c -> 'd -> 'd * 'b * 'c = <fun>

Que l'on peut réécrire plutôt :

In [20]:
let f7 (x, y, z) = function t -> (t, y, z)
Out[20]:
val f7 : 'a * 'b * 'c -> 'd -> 'd * 'b * 'c = <fun>

Exercice 5

In [21]:
let max3 x y z = (max max x) y z
Out[21]:
val max3 : ('a -> 'a -> 'a) -> 'a -> 'a -> 'a = <fun>

Observer bien le type de la fonction. Il faut que le premier argument soit du même type que max.

In [22]:
max3 55 0 42
Out[22]:
File "[22]", line 1, characters 5-7:
Error: This expression has type int but an expression was expected of type
         'a -> 'a -> 'a
Characters 5-7:
  max3 55 0 42
       ^^

Il faut donc lui fournir une fonction de ce même type :

In [23]:
max3 min 0 42
Out[23]:
Exception: Invalid_argument "compare: functional value".

Mais on ne peut pas comparer les valeurs fonctionnelles, Caml ne sait pas comparer des fonctions, la fonction max3 est inutilisable.

Bien entendu, ce que l'on voulait était :

In [24]:
let max3 x y z = max (max x y) z
Out[24]:
val max3 : 'a -> 'a -> 'a -> 'a = <fun>
In [25]:
max3 55 0 42
Out[25]:
- : int = 55

Exercice 6

In [26]:
let rec composition f n =
  if n = 0 then
    fun x -> x
  else
    fun x -> (f ((composition f (n - 1)) x))
Out[26]:
val composition : ('a -> 'a) -> int -> 'a -> 'a = <fun>

C'est la fonctionnelle qui calcule la composée $n$-ième : $f \rightarrow f^n$.

Exercice 7

In [27]:
let add1 (x, y) = x + y
Out[27]:
val add1 : int * int -> int = <fun>
In [28]:
let add2 x y = x + y
Out[28]:
val add2 : int -> int -> int = <fun>
In [29]:
let uncurry f (x, y) = f x y
Out[29]:
val uncurry : ('a -> 'b -> 'c) -> 'a * 'b -> 'c = <fun>
In [30]:
let add1_bis = uncurry add2;;
add1_bis (3, 4);;
Out[30]:
val add1_bis : int * int -> int = <fun>
Out[30]:
- : int = 7
In [31]:
let curry f x y = f (x, y)
Out[31]:
val curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c = <fun>
In [32]:
let add2_bis = curry add1
Out[32]:
val add2_bis : int -> int -> int = <fun>
In [33]:
add2_bis 41 1
Out[33]:
- : int = 42

Exercice 8

In [34]:
let rec nombre_chiffres n =
  if n < 10 then
    1
  else
    1 + nombre_chiffres (n / 10)
Out[34]:
val nombre_chiffres : int -> int = <fun>
In [35]:
nombre_chiffres 5;;
nombre_chiffres 15;;
nombre_chiffres 123456789;;
Out[35]:
- : int = 1
Out[35]:
- : int = 2
Out[35]:
- : int = 9

On montre par récurrence (forte) sur $n$ dans $\mathbb{N}$ que la fonction termine et renvoie le bon résultat.

Autre version avec accumulateur, récursive terminale :

In [36]:
let  nombre_chiffres n =
  (* accu + le nombre de chiffres de n = constant *)
  let rec nb_chiffres_aux n accu =
    if n < 10 then
      accu + 1
    else
      nb_chiffres_aux (n / 10) (accu + 1)
  in
  nb_chiffres_aux n 0
Out[36]:
val nombre_chiffres : int -> int = <fun>

Exercice 9

In [37]:
let rec mult_russe a b =
  if a = 0 then
    0
  else if a mod 2 = 0 then 
    mult_russe (a / 2) (2 * b)
  else
    b + (mult_russe (a - 1) b)
Out[37]:
val mult_russe : int -> int -> int = <fun>
In [38]:
mult_russe 3 27
Out[38]:
- : int = 81

Montrons par récurrence (forte) sur $a \in \mathbb{N}$ que cette fonction se termine et renvoie le produit de $a$ par $b$. Si $a = 0$, il n'y a pas de problème de terminaison et le résultat renvoyé est bien celui escompté. La propriété est donc vraie au rang $0$. Soit $a \geq 1$, tel que la propriété est vraie pour tout $n < a$. Montrons que la propriété est vraie au rang $a$ également. Comme $a \geq 1$, on rentre dans l'un des deux derniers else. Si $a$ est pair, $a / 2$ est un entier naturel strictement inférieur à $a$ et, par hypothèse de récurrence, l'appel récursif sur $(a / 2)$ et $(2 \times b)$ termine et renvoie $(a / 2) \times (2 \times b) = ab$. Sinon $a - 1$ est aussi un entier naturel strictement inférieur à $a$, et par hypothèse de récurrence, l'appel sur $(a - 1)$ et $b$ termine et renvoie $(a - 1)b$. En ajoutant $b$ à ce résultat on trouve encore $ab$. Dans les deux cas la conditionnelle termine et renvoie $ab$ et la propriété est donc vraie au rang $a$. D'après le principe de raisonnement par récurrence la propriété est ainsi vraie pour tout $a \in \mathbb{N}$.

Bien sûr, cette preuve est élémentaire et on ne fera pas toujours les récurrences lorsqu'elles sont aussi simples. Il faudra cependent bien dire que les appels récursifs se font sur une valeur strictement inférieure (ici $a / 2$ et $a - 1$) et atteignent bien l'un des cas de base. Pour la correction, on explicitera au moins très clairement l'hypothèse qui serait démontrée par récurrence.

Voici une autre manière de faire en utilisant une fonction auxiliaire et un accumulateur :

In [39]:
let mult_russe_bis a b =
  (* Diminue a en assurant ab + r constant *)
  let rec aux a b r =
    if a = 0 then
      r
    else if a mod 2 = 0 then
      aux (a / 2) (2 * b) r
    else
      aux (a - 1) b (r + b)
  in
  aux a b 0
Out[39]:
val mult_russe_bis : int -> int -> int = <fun>
In [40]:
mult_russe_bis 3 27
Out[40]:
- : int = 81

Exercice 10 : Moyenne arithmético-géométrique

  1. On remarque que les suites sont toujours positives et en utilisant l'identité $2xy \leq x^2 + y^2$ appliquée pour $x = \sqrt{u_n}$ et $y = \sqrt{v_n}$, on en déduit que pour tout $n \geq 1$, $u_n \leq v_n$. Pour $n \geq 1$, on a alors $v_{n + 1} \leq \frac{v_n + v_n}{2} \leq v_n$ et $u_{n + 1} \geq \sqrt{u_n u_n} \geq u_n$. De plus pour $n \geq 1$, $v_{n + 1} - u_{n + 1} \leq v_{n + 1} - u_{n} = \frac{u_n + v_n}{2} - u_n = \frac{v_n - u_n}{2} \leq \frac{1}{2^{n}}(v_1 - u_1)$. Ainsi, les suites $(u_n)_{n \geq 1}$ et $(v_n)_{n \geq 1}$ sont adjacentes et convergent vers une limite commune $M(a, b) \geq 0$ appelée moyenne arithmético-géométrique de $a$ et $b$.
In [41]:
let rec u n =
  if n = 0 then
    1.
  else
    sqrt((u (n - 1)) *. (v (n - 1)))
and v n =
  if n = 0 then
    2.
  else
    (u (n - 1) +. v (n - 1)) /. 2.
Out[41]:
val u : int -> float = <fun>
val v : int -> float = <fun>
In [42]:
u 10 = v 10
Out[42]:
- : bool = true

L'arrondi des flottants et la convergence (rapide) des deux suites vers une même limite fait que le résultat de Caml est le même pour u_10 et v_10, en tout cas sur cette machine.

In [43]:
let suites a b =
  let rec u n =
    if n = 0 then
      a
    else
      sqrt((u (n - 1)) *. (v (n - 1)))
  and v n =
    if n = 0 then
      b
    else
      (u (n - 1) +. v (n - 1)) /. 2.
  in
  (u, v)
Out[43]:
val suites : float -> float -> (int -> float) * (int -> float) = <fun>
In [44]:
let u, v = suites 1. 2. in u 10, v 10
Out[44]:
- : float * float = (1.45679103104690677, 1.45679103104690677)
In [45]:
let termes a b n =
 let u, v = suites a b in
 (u n, v n)
Out[45]:
val termes : float -> float -> int -> float * float = <fun>

Attention, ce n'est pas du tout efficace ! Voyez-vous pourquoi ?

In [46]:
termes 1. 100. 10;;
termes 2. 487. 10;;
termes 500. 501. 10;;
Out[46]:
- : float * float = (26.2166887202249228, 26.2166887202249228)
Out[46]:
- : float * float = (111.165431136800507, 111.165431136800507)
Out[46]:
- : float * float = (500.499875124836194, 500.499875124836194)

Exercice 11

In [47]:
let rec f n =
  (n = 0) || g (n - 1) 
and g n = 
  (n <> 0) && f (n - 1);;
Out[47]:
val f : int -> bool = <fun>
val g : int -> bool = <fun>

f teste si $n$ est pair et g si $n$ est impair. Si $n < 0$, les fonctions ne terminent pas.

In [48]:
f 11;;
f 12;;
g 57;;
g 0;;
Out[48]:
- : bool = false
Out[48]:
- : bool = true
Out[48]:
- : bool = true
Out[48]:
- : bool = false
In [49]:
let rec f n =
  if n = 0 then 1 else 3 + g (n - 1) 
and g n = 
  if n = 0 then 0 else 1 + f (n - 1);;
Out[49]:
val f : int -> int = <fun>
val g : int -> int = <fun>

f n renvoie $2n + 1$ et g n renvoie $2n$. Si $n < 0$, les fonctions ne terminent pas.

In [50]:
f 3;;
g 6;;
Out[50]:
- : int = 7
Out[50]:
- : int = 12
In [51]:
let rec f m n =
  if m = 0 then
    n
  else
    g (m - 1) (n + 1)
and g m n =
  if m = 0 then
    n
  else
    (f (m - 1) n) + 1
Out[51]:
val f : int -> int -> int = <fun>
val g : int -> int -> int = <fun>

f m n et g m n renvoient $n + m$. Si $m < 0$, les fonctions ne terminent pas. En revanche $n$ peut être un entier relatif ici.

In [52]:
f 3 4;;
g 23 (-14)
Out[52]:
- : int = 7
Out[52]:
- : int = 9