Programmation Fonctionnelle, TP5

Version & licenses
Creative Commons License

Programmation Fonctionnelle, TP5 : Listes infinies.

Guyslain Naves

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.

Un type pour les listes infinies.

Nous allons travailler avec le type suivant, et la fonction view associée.

  1. (* le type des listes infinies *)
  2. type 'elt stream = Cons of ('elt * 'elt stream) Lazy.t

  3. (* view : 'elt stream -> 'elt * 'elt stream, déconstruit une liste infinie. *)
  4. let view (Cons stream) = Lazy.force stream

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 :

  1. match view stream with
  2. | (head,tail) -> ...

Recopier les définitions de 'elt stream et view.

Construire une liste infinie définie par une fonction itérée.

É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.

  1. let rec make_sequence : ('elt -> 'elt) -> 'elt -> 'elt stream =
  2. fun f init ->
  3. Cons (lazy ( (* à compléter *) ))

Construire une liste, plus général.

É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 $$

  1. let rec make : ('accu -> 'elt * 'accu) -> 'accu -> 'elt stream =
  2. fun f init ->
  3. Cons (lazy ( (* à compléter *)))

Ajouter un élément à une liste.

Écrire une fonction ajoutant un élément en tête d'une liste infinie.

  1. let cons : 'elt -> 'elt stream -> 'elt stream =
  2. fun elt stream ->
  3. Cons (lazy ( (* à compléter *)))

Manipulations simples.

Les entiers naturels.

Définir la liste ints de tous les entiers naturels par ordre croissant (Utiliser make_sequence).

Prendre le préfixe.

Écrire une fonction qui retourne la liste (finie) des $k$ premiers éléments d'une liste infinie.

  1. val take : int -> 'elt stream -> 'elt list

  2. let to_ten = take 11 ints
  3. val to_ten : int list = [0;1;2;3;4;5;6;7;8;9;10]

Enlever un préfixe.

Écrire une fonction retirant les $k$ premiers éléments d'une liste infinie.

  1. val drop : int -> 'elt stream -> 'elt stream

  2. let ten_to_twenty = take 11 (drop 10 ints)
  3. val ten_to_twenty : int list = [10;11;...;19;20]

Ajouter un préfixe.

Écrire une fonction prenant une liste finie et une liste infinie, et concatènant les deux.

  1. val append : 'elt list -> 'elt stream -> 'elt stream

Fonctionnelles.

Scan.

Utiliser make pour écrire une fonction scan.

  1. let scan f init stream =
  2. make
  3. (fun (accu, stream) -> match view stream with
  4. | (head,tail) -> (* à compléter *)
  5. )
  6. (init,stream)
  7. val scan : ('accu -> 'elt -> 'res * 'accu) -> 'accu -> 'elt stream -> 'res stream

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$$

Les nombres triangulaires.

Utiliser scan pour définir la liste des nombres triangulaires : il s'agit de la liste des sommes des entiers de $1$ à $k$.

  1. val triangles : int stream
  2. # let _ = take 10 triangles;;
  3. - : int list = [1;3;6;10;15;21;28;36;45;55]

Map.

Déduire de scan la fonction map, similaire à List.map.

  1. val map : ('elt -> 'im) -> 'elt stream -> 'im stream

  2. let positifs = map (fun n -> n+1) ints
  3. let _ = take 10 positifs
  4. - : int list = [1;2;3;4;5;6;7;8;9;10]

Combine.

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$.

  1. val combine : 'left stream -> 'right stream -> ('left * 'right) stream

Addition de deux listes.

En déduire une fonction (++) pour additioner deux listes infinies d'entiers terme-à-terme.

Fibonacci comme vous ne l'avez jamais vu.

Pourquoi ce code calcule-t-il la suite de Fibonacci ?

  1. let rec fibonacci = Cons (lazy (1, Cons (lazy (1, fibonacci ++ drop 1 fibonacci))))

Les rubans

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$.

  1. (* un ruban est constitué d'un demi-ruban à gauche, un élément au centre, et un demi-ruban à droite *)
  2. type 'a tape = 'a stream * 'a * 'a stream

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.

Les entiers relatifs

Définir le ruban des entiers relatifs, avec la tête en 0.

Déplacer la tête de lecture

Coder les fonctions suivantes :

  1. (* retourne l'élément sous la tête de lecture *)
  2. val top : 'a tape -> 'a = <fun>

  3. (* Déplace la tête de lecture d'un cran à gauche *)
  4. val move_left : 'a tape -> 'a tape = <fun>

  5. (* Déplace la tête de lecture d'un cran à droite *)
  6. val move_right : 'a tape -> 'a tape = <fun>

Extraire une partie du ruban.

É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.

  1. val clip : 'elt tape -> int -> int -> 'elt list

(indice : déplacer vous sur le ruban jusqu'à ce que $i=0$. Ensuite seulement, extraire la partie désirée.)

Map.

Écrire la fonction map pour les rubans. Appeler cette fonction map_tape.

  1. val map_tape : ('elt -> 'im) -> 'elt tape -> 'im tape

Le ruban des rubans.

É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$.

  1. val coextend : 'elt tape -> 'elt tape tape

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.)

Automates cellulaires

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 :

  1. type 'state rule : 'state tape -> 'state

  2. let rec int_of_bool_list = function
  3. | [] -> 0
  4. | true::tail -> 1 + 2 * int_of_bool_list tail
  5. | false::tail -> 2 * int_of_bool_list tail

  6. let rule_of_int : int -> 'bool rule =
  7. fun i tape ->
  8. let local_value = int_of_bool_list (clip tape (-1) 1) in
  9. (i lsr local_value) mod 2 <> 0

Transitions

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.

  1. val transition : 'state rule -> 'state tape -> 'state tape

Un ruban aléatoire

Ajouter à votre code la ligne suivante, initialisant le générateur aléatoire :

  1. let _ = Random.self_init ()

Puis, en utilisant Random.bool : unit -> bool, écrire une fonction générant un ruban infini de booléens aléatoirement.

  1. val random_tape : unit -> bool tape

Génération d'un demi-plan par un automate cellulaire.

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.

  1. val plane_of_rule : bool rule -> bool tape tape
  2. val draw_plane : bool tape tape -> unit

Tester ensuite avec diverses règles. Vous devriez obtenir des images similaires à celles-ci :

Règle 26
Règle 45
Règle 45
Règle 110
Règle 110
Règle 184

À vous de jouer...

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.

Avec des couleurs
Avec des couleurs

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 :

  1. let make_seq f tape = make_sequence f (f tape)

  2. let move_up tapes_tape = map_tape move_right tapes_tape
  3. let move_down tapes_tape = map_tape move_left tapes_tape

  4. let coextend_plane : 'a tape tape -> 'a tape tape tape tape = fun tapes_tape ->
  5. map_tape
  6. (fun tapes_tape ->
  7. (make_seq move_down tapes_tape, tapes_tape, make_seq move_up tapes_tape)
  8. )
  9. (coextend tapes_tape)

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.

Le Jeu de la Vie de Conway