Nous nous servons d'un type inductif et d'un peu d'évaluation paresseuse, pour définir des listes infiniment longues. Nous continuons ainsi à nous familiariser avec les structures linéaires et leurs fonctionnelles.
Nous allons travailler avec le type suivant, et la fonction view associée.
Ce code utilise le type paramétré Lazy.t, qui est le type des valeurs paresseuses. C'est donc en quelque sorte un conteneur, pouvant stocker une expression non-évaluée. Les valeurs de ce type ne sont calculées que si cela est nécessaire. Ainsi on peut définir des listes de longueurs infinies, mais il ne faudra jamais essayer de les parcourir entièrement. Il faudra donc être prudent en les utilisant, pour ne pas avoir de Stack overflow.
Si on omet l'apparition de ce Lazy.t, la définition du type stream rappelle celle d'une liste, excepté qu'il manque le cas de base, lorsque la liste est vide. C'est pour cela que ces listes sont de longueur infinies.
La fonction view permet de récupérer la tête et la queue de la liste. Lazy.force est une fonction de type 'a Lazy.t -> 'a, qui force l'évaluation de la valeur paresseuse. Ainsi, on utilisera souvent la construction :
Recopier les définitions de 'elt stream et view.
Écrire une fonction prenant une fonction f et un élément initial init, et calculant la liste infinie [init; f init; f (f init);...] . Pour cela, on utilise le mot-clé lazy qui se comporte comme une fonction de type 'a -> 'a Lazy.t, sauf que l'argument est évalué paresseusement.
Le code manquant est donc de type 'elt * 'elt stream.
Écrire une autre fonction pour construire une liste infinie. Cette fois-ci, on répète plusieurs fois la même fonction sur une suite de valeurs, mais la fonction fournie aussi une valeur auxiliaire, et c'est cette valeur qui est stockée dans la liste infinie. La liste construite par make $f~u_0$ est donc $e_1,e_2,e_3,\ldots$, avec pour tout $i \geq 0$ :
$$ (u_{i+1},e_{i+1}) = f~u_i $$
Écrire une fonction ajoutant un élément en tête d'une liste infinie.
Définir la liste ints de tous les entiers naturels par ordre croissant (Utiliser make_sequence).
Écrire une fonction qui retourne la liste (finie) des $k$ premiers éléments d'une liste infinie.
Écrire une fonction retirant les $k$ premiers éléments d'une liste infinie.
Écrire une fonction prenant une liste finie et une liste infinie, et concatènant les deux.
Utiliser make pour écrire une fonction scan.
Si le troisième argument stream est une liste infinie $e_1,e_2,e_3,\ldots$, et en notant $f$ et $u_1$ le premier et le second argument, alors la liste calculée doit être $a_1,a_2,a_3\ldots$ avec pour tout $i$ :
$$ f~u_i~e_i = (a_i,u_{i+1}) $$
scan est donc une sorte de fold_left qui construit la liste de toutes les valeurs intermédiaires calculées par fold_left :
$$ f~u_1~e_1 = (a_1,u_2) $$
$$ f~u_2~e_2 = (a_2,u_3) $$
$$ f~u_3~e_3 = (a_3,u_4) $$
$$ f~u_4~e_4 = (a_4,u_5) $$
$$\ldots$$
Utiliser scan pour définir la liste des nombres triangulaires : il s'agit de la liste des sommes des entiers de $1$ à $k$.
Déduire de scan la fonction map, similaire à List.map.
Utiliser make pour définir une fonction combine, qui prenant deux listes infinies $a_1,a_2,a_3,\ldots$ et $b_1,b_2,b_3,\ldots$, calcule la liste infinie $(a_1,b_1),(a_2,b_2),\ldots$.
En déduire une fonction (++) pour additioner deux listes infinies d'entiers terme-à-terme.
Pourquoi ce code calcule-t-il la suite de Fibonacci ?
Les listes infinies, c'est trop facile. Alors définissons les rubans : ce sont des listes infinies dans les deux sens. Là où les listes ont des éléments en positions $0,1,2,\ldots$, les rubans ont des éléments en positions $\ldots,-2,-1,0,1,2,\ldots$.
L'élément au centre peut être vu comme la tête de lecture du ruban (pensez à des bandes magnétiques). C'est l'endroit dont on peut connaître directement la valeur. On note $\ldots,e_{-2},e_{-1},\left|e_0\right|,e_1,e_2,\ldots$ le ruban avec une tête de lecture en $e_0$ : la tête de lecture est précisé par les barres verticales.
Définir le ruban des entiers relatifs, avec la tête en 0 .
Coder les fonctions suivantes :
Écrire une fonction prenant un ruban et deux entiers $i$ et $j$, et retournant la liste (finie) des éléments entre les positions $i$ et $j$ incluses sur le ruban.
(indice : déplacer vous sur le ruban jusqu'à ce que $i=0$. Ensuite seulement, extraire la partie désirée.)
Écrire la fonction map pour les rubans. Appeler cette fonction map_tape.
Écrire une fonction prenant un ruban $r$, et retournant le ruban dont l'élément en position $i$ est le ruban obtenu à partir $r$ en déplaçant la tête de lecture jusqu'à la position $i$.
Ainsi, si le ruban donné en argument est $\ldots,-2,-1,|0|,1,2,\ldots$, le ruban calculé doit être
$$ \ldots,(\ldots -3,\left|-2\right|,-1,0,\ldots),(\ldots -2,\left|-1\right|,0,1,\ldots),|(\ldots -1,\left|0\right|,1,2,\ldots)|,(\ldots -1,0,\left|1\right|,2,\ldots),\ldots$$
Ce ruban représente donc toutes les positions possibles de la tête de lecture.
(indice : utiliser make_sequence et les fonctions de déplacement.)
Les automates cellulaires sont un modèle de calcul, qui consiste à utiliser un très grand nombre (possiblement infini) d'automates finis identiques (les cellules), tel que chacun interagit avec un nombre fini d'entre eux : ces voisins. C'est notamment le modèle de calcul qui régit le projet Led's Chat.
Dans notre cas, nous allons utiliser un automate par entier relatif, l'automate $i$ pouvant interagir avec les automates $i+1$ et $i-1$. Ces automates cellulaires sont donc de dimension 1 (la dimension de la ligne). Par ailleurs, chaque automate ne pourra avoir que deux états (nous utiliserons le type bool pour coder l'état).
Ainsi, l'état de l'automate cellulaire est un ruban de booléen. Puisque chaque cellule interagit uniquement avec ces deux voisins, à chaque étape de calcul, son nouvel état dépend des $2^3 = 8$ configurations possibles de lui-même et ces deux voisins. Il existe donc $2^8 = 256$ automates possibles.
En apprendre plus sur Wikipedia. C'est seulement pour les curieux : vous n'avez pas besoin de lire cette page pour continuer le TP.
Une règle est une fonction des rubans vers les états, qui retourne l'état de la tête après une seule étape de calcul. Pour générer les règles, on utilise le code suivant :
Coder la fonction de transition, prenant une règle de type 'state rule, un ruban de type 'state tape, et retournant le ruban obtenu en appliquant cette règle à chaque case. Vous utiliserez pour cela coextend.
Ajouter à votre code la ligne suivante, initialisant le générateur aléatoire :
Puis, en utilisant Random.bool : unit -> bool, écrire une fonction générant un ruban infini de booléens aléatoirement.
En répétant une transition depuis le ruban aléatoire, on obtient une suite de rubans, c'est-à-dire une liste infinie de ruban. On peut ensuite ajouter une autre liste infinie de rubans dans l'autre sens pour obtenir un ruban de rubans. Un ruban de ruban représente l'ensemble des couples d'entiers relatifs, c'est donc le plan discret.
En utilisant deux fois clip, on peut récupérer un rectangle de même taille que la fenêtre graphique (cf. le TP 1, pour voir comment l'ouvrir), et l'afficher.
Écrire une fonction plane_of_rule générant un plan à partir d'une règle, et une fonction draw_plane affichant un rectangle d'un plan (à partir d'un point de coordonnées données en paramètres). Utiliser List.mapi pour écrire draw_plane.
Tester ensuite avec diverses règles. Vous devriez obtenir des images similaires à celles-ci :
Créer des automates cellulaires avec des ensembles d'états plus complexes (les entiers, des couleurs codés en rgb) et des règles adaptées.
On peut aussi facilement coder le Jeu de la Vie de Conway. Pour cela, on utilise un ruban de rubans (un plan) pour coder une position, puis on définit une fonction similaire à coextend pour les plans :
Une règle doit alors être une fonction de type 'state tape tape -> 'state, et la fonction de transition est définie avec coextend_plane. Le reste du code s'adapte facilement.
