TD 3 : Evaluation paresseuse

L'évaluation paresseuse est le moyen qu'ont trouvé les informaticiens non pas pour se la couler douce, mais pour manipuler des objets infinis ! Nous prendrons ici l'exemple des suites. Ce TD est une introduction au TL sur les flux.

Faisons planter caml....

Faisons le planter tout de suite

Ecrivez la foonction repete_infini qui prend un élement x et constitue une liste où cet élement est répété une infinité de fois. Essayez alors ce qui suit:

repete_infini "toto";;
let a = repete_infini "a";;
a;;

Faisons le planter à la demande

Rappel : Le symbole () est une valeur du type unit... c'est même la seule. Une fonction qui s'écrit function () -> ... est une fonction avec filtrage sur une valeur particulière, comme function 0 -> ..., mais avec le type unit, le cas particulier de () recouvre tous les cas...

Essayez maintenant ce qui suit.

let a = function () -> repete_infini "a";;
a;;

Ca n'a pas planté... comment utiliser ce a pour planter à nouveau ?

Echouons à définir la notion de suite

Définition du type

Pour nous ici, une suite sera définie par Un+1 = f(Un), et par u0, le premier élément. Il nous faut donc, pour représenter une suite, stocker la valeur de u0, et la fonction f. Comme on ne veut pas contraindre le type des élements de la suite, on va laisser traîner des 'a dans l'affaire. Cela donne:

type 'a suite = Suite of 'a * ('a -> 'a);;

Donnez une valeur de type int suite qui correspond à la suite des entiers naturels.

let entiers = ... ;;

Suite de syracuse

La suite de syracuse est définie par Un+1 = Un/2 si Un est paire, et Un+1 = 3*Un + 1 sinon. Au passage, elle semble finir par produire inévitablement 4,2,1,4,2,1,4,2,... sans que personne ne sache le démontrer (conjecture de Collatz)... mais revenons à nos moutons. Définissez la suite de syracuse syr27 commençant par 27.

Definissez la fonction list_of_suite qui met dans une liste les n premiers éléments de la suite (cela nous permet de voir la suite). Par exemple:

let l1 = list_of_suite syr27 200;;
val l1 : int list = [27; 82; 41; 124; 62; 31; 94;...]

let l2 = list_of_suite entiers 200;;
val l2 : int 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; 70; 71; 72; 73; 74;
   75; 76; 77; 78; 79; 80; 81; 82; 83; 84; 85; 86; 87; 88; 89; 90; 91; 92;
   93; 94; 95; 96; 97; 98; 99; 100; 101; 102; 103; 104; 105; 106; 107; 108;
   109; 110; 111; 112; 113; 114; 115; 116; 117; 118; 119; 120; 121; 122; 123;
   124; 125; 126; 127; 128; 129; 130; 131; 132; 133; 134; 135; 136; 137; 138;
   139; 140; 141; 142; 143; 144; 145; 146; 147; 148; 149; 150; 151; 152; 153;
   154; 155; 156; 157; 158; 159; 160; 161; 162; 163; 164; 165; 166; 167; 168;
   169; 170; 171; 172; 173; 174; 175; 176; 177; 178; 179; 180; 181; 182; 183;
   184; 185; 186; 187; 188; 189; 190; 191; 192; 193; 194; 195; 196; 197; 198;
   199]

Opération sur les suites

L'idée de tout ce TD, c'est de maintenant pouvoir définir la notion de somme de deux suite, même si ces deux suites sont des objets infinis. A la demande (c'est ça qui est paresseux), on pourra toujours faire un list_of_suite pour générer autant d'éléments de la suite somme que l'on veut. Définissez somme_suite pour que ce qui suit fonctionne:

let s = somme_suite syr27 entiers;;
list_of_suite s 200;;
- : int list = [27; 83; 43; 127; 66; 36; 100;...]

Alors ? On sèche ?

La notion de flux

Définition

Nous allons jouer ici avec une idée géniale, pour résoudre les limitations précédentes des suites. Elle passe par un mélange des deux premières parties du TD. Cette idée vient de la littérature, car votre enseignant de cours de Modèles de Programmation eût été bien incapable de trouver ça tout seul. Définissions le type 'a flux comme suit, attachez vos ceintures...

type 'a flux = Flux of 'a * (unit -> 'a flux);;

Définissions de quoi lire les morceaux qui constituent une valeur de type flux, comme on l'avait fait avec courant et fonction_suivant pour les suites.

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

L'idée est qu'un flux représente une liste infinie. Une liste, c'est un élement en tête, et la liste des suivants. Ici, si flx est une valeur de type 'a flux, on aura

let flx = Flux ....;;
val flx : 'a flux = ...

courant flx;;
- : 'a = la tete du flux

let fct = la_fonction flx;;
val fct : unit -> 'a flux = une fonction a definir...

La construction que l'on fera des flux sera telle que fct () est le flux (donc une valeur du genre Flux (...,...)) qui commence par l'élément suivant de flx. On définira donc plutôt, au lieu de la_fonction:

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

suivants flx;;
- : 'a flux = le flux des éléments suivants de flx.

Notre premier flux : les entiers

Définissez récursivement une fonction entiers qui prend un entier i en argument, et qui renvoie le flux des entiers [i,i+1,i+2,i+3,...infini]. Essayez:

let depuis_0 = entiers 0;;
let depuis_1 = suivants depuis_0;;
let depuis_2 = suivants depuis_1;;
courant depuis_2;;

Pour dérouler le flux

Définissez la fonction list_of_flux telle que:

# list_of_flux depuis_0 100;;
- : int 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; 70; 71; 72; 73; 74; 75; 76; 77;
 78; 79; 80; 81; 82; 83; 84; 85; 86; 87; 88; 89; 90; 91; 92; 93; 94; 95; 96;
 97; 98; 99]

L'avantage des flux sur les suites ?

C'est l'objet du TL...