TL 1 : Les flux
L'objectif du TP est d'expérimenter l'approche fonctionnelle en manipulant un type bizarre : les flux, qui sont une version de ce qu'on appelle couramment des flots (streams en anglais, cf. cours sur la programmation par flots à venir). Les fichiers, entrées-sortties, sont des flots en informatique, et OCaml dispose de vrais flots. D'autres objets sont des flots, comme les séries (infinies) en mathématiques. C'est ce que nous allons étudier, a partir de données "maison" : les flux. L'idée n'est pas d'implanter des mécanismes performants, mais de voir comment on peut traiter avec élégance le problème des données infinies par une approche fonctionnelle.
Préliminaires
On repart des acquis du TD 3, à savoir
type 'a flux = Flux of 'a * (unit -> 'a flux);;

let courant  = function Flux(x,_) -> x;;
let suivants = function Flux(_,f) -> f ();;

let rec entiers = 
  function i -> Flux (i, function () -> entiers (i+1));;

let nat = entiers 0;;
Opérations élémentaires
n-ième élément
Définissez la fonction flux_nieme qui prends un flux, un nombre, et donne le n-iemme élément du flux (comptés à partir de 1).
# flux_nieme nat 100;;
- : int = 99
Consommation du flux
Le traitement usuellement réservé aux flux est que l'on en extrait les éléments un à un, dans l'ordre où ils sont définis dans le flux. On dit que l'on consomme ces élements, un à un. Ce qui est bien avec les flux, c'est que l'on peut consommer autant d'éléments que l'on souhaite, puisque le flux est infini.
Définissez la fonction consomme, qui prend un flux flx et un entier n, et qui renvoie une paire. Cette paire est constituée de la liste des éléments consommés d'une part, et du flux restant d'autre part.
Définissez la fonction list_of_flux du TD 3, mais en utilisant consomme.
La fonction map
Définissez la fonction flux_map, qui est aux flux ce que map est aux listes.
let nat2 = flux_map (function x -> x*x) nat;;
list_of_flux nat2 100;;
Nombres premiers
Filtrage de flux
On dira qu'une fonction qui à un élement associe un booléen est un filtre: quand on l'applique à l'élément, elle renvoie true s'il faut le garder, false sinon. Définissez la fonction flux_filtre qui prend un flux, un filtre, et rend le flux des éléments retenus par le filtre. Cela donne:
# 2=0;;
- : bool = false
# 9 mod 7;;
- : int = 2
# let nat_pair = flux_filtre nat (function x -> (x mod 2) = 0);;
val nat_pair : int flux = Flux (0, <fun>)
# list_of_flux nat_pair 100;;
- : int list =
[0; 2; 4; 6; 8; 10; 12; 14; 16; 18; 20; 22; 24; 26; 28; 30; 32; 34; 36; 38;
 40; 42; 44; 46; 48; 50; 52; 54; 56; 58; 60; 62; 64; 66; 68; 70; 72; 74; 76;
 78; 80; 82; 84; 86; 88; 90; 92; 94; 96; 98; 100; 102; 104; 106; 108; 110;
 112; 114; 116; 118; 120; 122; 124; 126; 128; 130; 132; 134; 136; 138; 140;
 142; 144; 146; 148; 150; 152; 154; 156; 158; 160; 162; 164; 166; 168; 170;
 172; 174; 176; 178; 180; 182; 184; 186; 188; 190; 192; 194; 196; 198]
Crible d'Eratostène
Cribler un flux d'entier, c'est retenir le premier élément, éliminer tous ces mutiples du flux, retenir l'élément suivant dans ce qui reste (c'est le deuxième élément du flux criblé), en éliminer tous les multiples, retenir l'élément suivant dans ce qui reste (le troisième élément du flux criblé), etc.... Cela donne, sur le flux entiers 2 :
*2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ...  // on garde 2, et on enlève ses multiples.
2 *3 5 7 9 11 13 15 17 19 21 23 ... // On garde 3, on enlève ses multiples
2 3 *5 7 11 13 15 17 19 23 ... // on garde 5, on elève ses multiples
2 3 5 *7 11 13 17 19 23 ...
2 3 5 7 *11 13 17 19 23 ...
En criblant le flux des entiers à partir de 2, on obtient le flux des nombres premiers.
Réalisez la fonction crible qui prend en argument un flux d'entiers, et calcule le flux criblé. Essayez-là :
let premiers = crible (entiers 2);;
list_of_flux premiers 100;;
flux_nieme premiers 1000;;
flux_nieme premiers 10000;;
Séries de Taylor
La fonction iter
Définissez la fonction flux_iter, qui prend un operateur op, un flux (disons a b c d e f ...), et qui renvoie un flux définit comme suit : son premier élément est a, le second a op b, le troisiemme a op b op c, etc.... Vous pourrez définit localement une fonction intermédiaire, ce qui donne:
let flux_iter = 
  function op     ->
  function flx    ->
  let rec flux_iter_tmp = function (flx2, res) -> ...
  in
    flux_iter_tmp (suivants flx,courant flx);;
Définissez flux_somme (sur le type float) en utilisant flux_iter.
Création
Une série est un flux de valeurs réelles, chacune d'elle s'obtenant à partir d'un entier (le rang d'une des valeurs de la série). Commençons par l'exponentielle. "A puissance B" se note a**b en caml. Le i-ème terme s'obtient par:
let rec fact = function   0.0 -> 1.0
                        | n -> n *. (fact (n -. 1.0));;
let exp_terme = function x -> function i -> x**i /. (fact i);;
Créez une fonction taylor permettant de définir les séries de Taylor, à savoir le flux des termes de la série... où plus exactement, une fonction qui à x associe ce flux. Cela donne:
# let exp_taylor = taylor exp_terme;;
val exp_taylor : float -> float flux = <fun>
# let exp_1 = exp_taylor 1.0;;
val exp_1 : float flux = Flux (1., <fun>)
# list_of_flux exp_1 10;;
- : float list =
[1.; 1.; 0.5; 0.166666666666666657; 0.0416666666666666644;
 0.00833333333333333322; 0.00138888888888888894; 0.000198412698412698413;
 2.48015873015873e-05; 2.75573192239858925e-06]
A l'aide de flux_somme et de flux_nieme, créez la fonction taylor_eval qui donne la valeur de la série pour un argument x, et une précision p (i.e. nombre de termes de la suite utilisés pour l'évaluation). On définira ainsi une approximation de la fonction exponentielle par:
let exp_approx = 
  function x -> 
  function p -> 
    taylor_eval (exp_taylor x) p;;

# exp_approx 1.0 5;;
- : float = 2.70833333333333304
# exp_approx 1.0 10;;
- : float = 2.71828152557319225
# exp_approx 1.0 20;;
- : float = 2.71828182845904553
Variables aléatoires
Préliminaire
Définissez un opérateur binaire sur les flux via la fonction flux_op
# let nat2 = flux_map (function x -> x*x) nat;;
# let flx = flux_op (function x -> function y -> x - y) nat2 nat;;
# list_of_flux flx 10;;
- : int list = [0; 0; 2; 6; 12; 20; 30; 42; 56; 72]
A l'aide de consomme, définissez la fonction flux_pack telle que
# let flx = flux_pack nat 7;;
# list_of_flux flx 10;;
- : int list list =
[[0; 1; 2; 3; 4; 5; 6]; [7; 8; 9; 10; 11; 12; 13];
 [14; 15; 16; 17; 18; 19; 20]; [21; 22; 23; 24; 25; 26; 27];
 [28; 29; 30; 31; 32; 33; 34]; [35; 36; 37; 38; 39; 40; 41];
 [42; 43; 44; 45; 46; 47; 48]; [49; 50; 51; 52; 53; 54; 55];
 [56; 57; 58; 59; 60; 61; 62]; [63; 64; 65; 66; 67; 68; 69]]
La variable uniforme
Sachant que Random.float 1.0 renvoie une valeur aléatoire entre 0.0 et 1.0, définissez la fonction va_uniforme telle que l'appel va_uniforme () corresponde aux échantillons d'une variable aléatoire uniforme sur [0,1[.
# let x = va_uniforme ();;
# let y = va_uniforme ();;
# list_of_flux x 3;;
- : float list =
[0.140791689359313688; 0.328350422991705138; 0.0476270454552507744]
# list_of_flux y 3;;
- : float list =
[0.766880082826698506; 0.148955353190282663; 0.965852937050789562]

Moyenne et variance
A l'aide des fonctions définies au TD 1, et de la fonction flux_pack, définissez la fonction va_moyenne qui prend une variable aléatoire x, en entier n, et renvoie une variable aléatoire donc chacune des valeurs est la moyenne de n tirages de x. Faites de même pour la fonction va_variance.
Opérations sur les variables aléatoires
Ecrivez les fonctions va_somme et va_produit qui font respectivement la somme et le produit de deux variables aléatoires... Passez par le cas général d'opérateur à deux arguments flux_op, et spécialisez-le à la somme et au produit. Faites de même la fonction va_f qui correspond à l'application d'une fonction f à une variable aléatoire.
Intégration de Monte Carlo
On peut calculer numériquement l'intégrale d'une fonction, en tirant des points (x,y) aléatoirement, et en comptant combien, en moyenne, sont au dessous de la courbe. Utilisons les variables aléatoires que l'on vient de définir pour calculer des intégrales.

Intéressons nous pour commencer à f(x)=2x² sur [0,1]. Exécutez
let xrange = (0.0,1.0);;
let yrange = (0.0,2.0);;
let f      = function x -> 2.0 *. x *. x;;
let range  = 
  function (min,max) -> 
  function x         -> min +. x *. (max -. min);;
let dessous_f = 
     function x -> 
     function y -> (f x) > y;;
Définissez à l'aide de va_f et de range deux variables aléatoires, x et y, qui sont uniformes respectivement sur [0,1] et [0,2].
Définissez le flux mc_bool de booléens, construits à partir des variables aléatoires x et y, qui a des contenus vrais quand (f x) > y. Définissez mc_float comme étant le flux mc_bool, où true et false sont remplacés par 1.0 et 0.0.
Définissez
let precision = 1000;;
let aire = 
  function (xmin,xmax) ->
  function (ymin,ymax) ->
    (xmax -. xmin) *. (ymax -. ymin);;
puis calculez le flux proba correspondant à la moyenne (avec precision termes) de mc_float A l'aide de la fonction aire, calculez enfin l'intégrale de f sur xrange.
L'idée est maintenant de reprendre ces étapes et de les regrouper sous forme de fonctions.
Définissez la fonction monte_carlo_test, qui elle-même définit x, y et range localement (let in), telle que
monte_carlo_test dessous_f xrange yrange;;
soit le flux mc_bool.
Définissez monte_carlo_proba qui prend un flux de booléens, une précision entière, et renvoie le flux des probabilités de true (calculé via une moyenne, comme nous l'avons fait pour passer de mc_bool à proba). Testez avec:
let dans_cercle = 
  function x -> 
  function y ->
    x*.x +. y*.y < 1.0;;

let flux_cercle = monte_carlo_test dans_cercle (-1.0,1.0) (-1.0,1.0);;
let flux_pi     = flux_map (function x -> 4.0*.x) (monte_carlo_proba flux_cercle 10000);;
list_of_flux flux_pi 100;;
let flux_pi_moy = va_moyenne flux_pi 20;;
list_of_flux flux_pi_moy 10;;
Définissez la fonction monte_carlo_integrale, qui définit localement aire, telle que
monte_carlo_integrale f xrange yrange 10000;;
- : float flux = Flux (0.6612, <fun>)
ou 10000 est la précision (nombre d'échantillons pour les moyennes).