Rappel : les flottants

---

En OCaml, les entiers (int) et les flottants (float) ne se mélangent pas :

• les constantes flottantes s'écrivent avec un point : 1., 0.5, 3.14 (et 1 est un entier)
• les opérations sur les flottants ont un point : +., -., *., /.
• pour convertir : float_of_int 3 vaut 3., int_of_float 3.7 vaut 3 ;
• fonctions utiles : sqrt, cos, sin (angles en radians), et la constante Float.pi.

let x = 2. *. Float.pi /. 3.   (* et non 2 * Float.pi / 3 *)

Rappel : les n-uplets

---

Un point est un couple de flottants. Pour récupérer ses composantes : on peut le déstructurer directement, dans un let ou dans les arguments d'une fonction.

let p = (1., 2.);;
let (x, y) = p in x +. y;;          (* vaut 3. *)
let scalaire (x, y) (z, w) = x *. z +. y *. w;;  (* float * float -> float * float -> float *)

Question 1

---

Écrivez une fonction milieu : point -> point -> point qui renvoie le milieu d'un segment (représenté par ses deux extrémités).

Question 2

---

Écrivez une fonction distance : point -> point -> float qui renvoie la distance séparant deux points.

Rappel :

---

unit et la séquence segment ne renvoie rien d'intéressant : elle a un effet (dessiner). Son résultat est (), l'unique valeur du type unit.

Pour faire plusieurs choses à la suite, on utilise la séquence e1; e2 : on évalue e1 (qui doit être de type unit), puis e2. La séquence e1; e2 prend la valeur de son dernier élément, ici e2. Attention, ; sépare deux expressions : pas de ; après la dernière.

let deux_segments () =
  segment (0., 0.) (1., 0.);
  segment (1., 0.) (1., 1.)

Question 3

---

Écrivez une fonction carre : point -> float -> unit telle que carre (x, y) c dessine le carré de côté c dont le coin en bas à gauche est le point (x, y).

Question 4

---

Écrivez une fonction avance : point -> float -> float -> point telle que avance p l a renvoie le point obtenu en partant de p et en avançant d'une longueur l dans la direction d'angle a (en radians, mesuré depuis l'axe des abscisses et dans le sens direct).

Question 5

---

En utilisant avance, écrivez une fonction hexagone : point -> float -> unit qui dessine un hexagone régulier de côté l partant du point p. Pour cette question, écrivez simplement les 6 segments à la main : on fera mieux juste après.

Rappel : fonctions récursives

---

Une fonction récursive se déclare avec let rec. Il faut toujours :

• un (ou des) cas de base, qui s'arrête sans appel récursif (sans quoi on boucle à l'infini)
• des appels récursifs sur des arguments « plus petits », qui se rapprochent du cas de base.

Quand une fonction ne fait que dessiner, le cas de base ne fait rien : il renvoie (). Un if sans else est autorisé quand la branche then est de type unit (le else sous-entendu renvoie ()). Pour mettre une séquence dans un then, on l'entoure de parenthèses (ou de begin ... end) :

let rec compte_a_rebours n =
  if n >= 0 then begin
    print_int n;
    print_string " ";
    compte_a_rebours (n - 1)
  end

Sans le begin ... end, seul le print_int n serait dans le if : tout le reste serait exécuté quoi qu'il arrive... et la fonction ne s'arrêterait jamais.

Question 6

---

1. Écrivez une fonction récursive cotes : int -> float -> point -> float -> float -> unit telle que cotes k t p l a dessine k segments de longueur l à la suite : le premier part de p dans la direction a, chaque segment suivant part de la fin du précédent, et on tourne de t entre deux segments.
2. En déduire une fonction polygone_regulier : int -> point -> float -> unit telle que polygone_regulier n p l dessine un polygone régulier à n côtés de longueur l, partant de p. Dessinez un triangle, un carré, un hexagone et un polygone à 50 côtés (les appels pour ces tests vous sont donnés à la fin du bloc).

Question 7

---

Écrivez une fonction spirale : int -> point -> float -> float -> unit telle que spirale n p l a dessine n segments : le premier part de p, a la longueur l et la direction a, et chaque segment suivant part de la fin du précédent, est 5 % plus court et tourne de (à gauche). Testez avec spirale 40 (0., 0.) 1. 0. puis changez l'angle.

Question 8 : l'ensemble de Cantor

---

On part d'un segment horizontal. À chaque étape, on retire le tiers central de chaque segment, et on dessine ce qui reste juste en dessous.

Écrivez une fonction cantor : int -> float -> float -> float -> unit telle que cantor n x1 x2 y dessine le segment de à , puis, si n > 0, appelle cantor (n - 1) sur le tiers gauche et sur le tiers droit, à la hauteur y -. 0.1.

Question 9 : un arbre

---

Écrivez une fonction arbre : int -> point -> float -> float -> unit telle que arbre n p l a dessine un arbre de profondeur n :

• si n = 0, on ne dessine rien ;
• sinon, on dessine un tronc de longueur l, qui part de p dans la direction a, puis deux arbres de profondeur n - 1 qui partent du bout du tronc : un tourné de vers la gauche, l'autre de vers la droite, avec une longueur multipliée par .

Dessinez arbre 10 (0., 0.) 1. (Float.pi /. 2.), puis utilisez le bouton « Rejouer le tracé » : dans quel ordre les branches sont-elles dessinées ?

Question 10

---

Combien de segments dessine arbre n ? Démontrez-le par récurrence, puis vérifiez avec le compteur affiché sous le dessin.

Question 11 : le triangle de Sierpiński

---

Écrivez une fonction sierpinski : int -> point -> point -> point -> unit telle que sierpinski n a b c :

• si n = 0, dessine le triangle ;
• sinon, calcule les milieux des trois côtés, et dessine récursivement les trois « petits » triangles de Sierpiński qui ont chacun un sommet en commun avec (le triangle du milieu est laissé vide).

Question 12 (un peu plus dur) : l'arbre en H

---

Un « H » est formé d'une barre horizontale de longueur , et de deux barres verticales de longueur centrées sur ses extrémités. L'arbre en H de profondeur est un H, avec un arbre en H de profondeur , deux fois plus petit, centré sur chacune des quatre extrémités des barres verticales.

Écrivez une fonction arbre_h : int -> point -> float -> unit telle que arbre_h n centre l le dessine (rien si n = 0).

Rappel : les listes

---

• Une liste est soit vide [], soit de la forme x :: reste (un premier élément x, suivi d'une liste reste). La notation [a; b; c] est un raccourci pour a :: b :: c :: [].
• Tous les éléments ont le même type : une liste de points a le type point list.
• On les parcourt par filtrage (match), récursivement :

let rec longueur l = match l with
  | [] -> 0
  | _ :: reste -> 1 + longueur reste

• Les motifs peuvent être plus précis : [x] (exactement un élément), x :: y :: reste (au moins deux éléments)... Les motifs sont essayés dans l'ordre, et doivent couvrir tous les cas (sinon, OCaml affiche un avertissement : lisez-le !).
• l1 @ l2 concatène deux listes. Attention : son coût est proportionnel à la longueur de l1 (il faut recopier l1).

Question 13

---

Écrivez une fonction récursive ligne : point list -> unit qui dessine la ligne brisée passant par les points de la liste, dans l'ordre : ligne [p1; p2; p3] trace les segments et . Une liste de 0 ou 1 point ne dessine rien.

Question 14

---

Écrivez une fonction polygone : point list -> unit qui dessine la ligne brisée fermée : on revient au premier point à la fin. Utilisez ligne et @.

Question 15

---

1. Exprimez les coordonnées de et en fonction de celles de et .
2. Le point s'obtient en partant de , et en avançant de dans la direction de tournée de . Écrivez une fonction sommet : point -> point -> point qui renvoie à partir de et .

Question 16

---

Écrivez la fonction récursive koch : int -> point -> point -> point list, puis dessinez koch 4 (0., 0.) (1., 0.) @ [(1., 0.)] avec ligne.

Question 17

---

1. Combien de points contient koch n p q ? Vérifiez avec List.length pour quelques valeurs de n.
2. Dessinez le flocon de Koch : trois courbes de Koch sur les côtés d'un triangle équilatéral. Dans quel sens faut-il parcourir le triangle pour que les pointes soient vers l'extérieur ?

Question 18 : complexité

---

On note le coût de koch n p q. On rappelle que l1 @ l2 coûte un temps proportionnel à la longueur de l1.

1. Établissez une relation de récurrence sur , et déduisez-en que .
2. La taille du résultat est : on aimerait un coût en . Pour cela, on écrit une fonction auxiliaire koch_acc : int -> point -> point -> point list -> point list telle que koch_acc n p q acc renvoie les points de la courbe de Koch (sans ) suivis des éléments de la liste acc. Ainsi, koch n p q = koch_acc n p q []. Écrivez cette fonction sans utiliser @.

Rappel : fonctions d'ordre supérieur

---

En OCaml, les fonctions sont des valeurs comme les autres : on peut les passer en argument, les renvoyer, les stocker dans une liste...

• fun x -> e est la fonction (anonyme) qui à x associe e. let f x = e est un raccourci pour let f = fun x -> e.
• Les fonctions à plusieurs arguments sont curryfiées : let f x y = e est en fait let f = fun x -> (fun y -> e). On peut donc appliquer partiellement une fonction : si avance : point -> float -> float -> point, alors avance (0., 0.) 1. est une fonction de type float -> point.

Question 19

---

Écrivez une fonction récursive applique : (point -> point) -> point list -> point list telle que applique f l renvoie la liste des images par f des points de l. Testez-la en déplaçant le flocon de 1 vers la droite, avec une fonction anonyme.

Question 20

---

Écrivez les transformations suivantes, de type point -> point une fois tous leurs arguments donnés sauf le dernier :

• translation : float -> float -> point -> point : translation dx dy p déplace p de ;
• homothetie : float -> point -> point : homothetie k p multiplie les coordonnées de p par k ;
• rotation : float -> point -> point : rotation a p tourne p d'un angle a autour de l'origine. On rappelle que l'image de est .

Question 21 : une rosace

---

En utilisant List.iter sur une liste d'angles, List.map et rotation, dessinez 8 copies de la courbe koch 3 (0., 0.) (1., 0.) @ [(1., 0.)], tournées de autour de l'origine.

Bonus : construisez la liste des angles avec une fonction récursive plutôt qu'à la main, et ajoutez des copies de plus en plus petites avec homothetie.

D'autres fonctions du module

---

List

• List.for_all f l : est-ce que f x vaut true pour tous les éléments x de l ?
• List.exists f l : est-ce que f x vaut true pour au moins un élément ?
• List.filter f l : la liste des éléments x de l tels que f x vaut true.
• List.mem x l : est-ce que x est un élément de l ?

Question 22

---

Le centre du flocon flocon n est le point .

1. Avec List.for_all, vérifiez que tous les points de flocon 5 sont à une distance au plus de .
2. Avec List.filter, dessinez seulement les points de flocon 5 qui sont à une distance au moins de , chacun sous la forme d'un petit segment (de p à translation 0.005 0. p).
3. Avec List.exists, vérifiez que le flocon passe bien par le point .

Rappel : le type

---

option Une valeur de type 'a option est soit None (« pas de valeur »), soit Some x avec x de type 'a. On s'en sert pour les fonctions qui ne peuvent pas toujours renvoyer un résultat, et on l'utilise avec un match :

match resultat with
| None -> ...
| Some x -> ...

Question 23

---

Écrivez une fonction récursive plus_haut : point list -> point option qui renvoie le point de plus grande ordonnée d'une liste (None si la liste est vide). Testez-la sur flocon 3 et sur [].

Rappel : types sommes

---

• Un type somme, ou union, liste les différentes formes possibles d'une valeur. Chaque forme a un constructeur (qui commence par une majuscule), éventuellement suivi d'arguments (of ...).
• Le type est récursif quand certains constructeurs contiennent des valeurs du type lui-même : une figure contient des figures. Ici, Groupe en contient même une liste.
• On l'utilise par filtrage, avec un cas par constructeur :

match f with
| Trait (p, q) -> ...
| Groupe l -> ...
| Deplace (dx, dy, g) -> ...
| Zoom (k, g) -> ...
| Tourne (a, g) -> ...

Rappel : fonctions mutuellement récursives

---

Pour parcourir une figure, on a besoin d'une fonction sur les figures et d'une fonction sur les listes de figures (pour Groupe), qui s'appellent l'une l'autre. On les définit ensemble, avec let rec ... and ... :

let rec f x = ... g ... 
and g y = ... f ...

Question 24

---

Écrivez deux fonctions mutuellement récursives nb_traits : figure -> int et nb_traits_liste : figure list -> int, qui comptent le nombre de traits d'une figure (resp. d'une liste de figures). nb_traits exemple doit valoir 8.

Question 25 : dessiner une figure

---

Pour dessiner une figure, on la parcourt en retenant la transformation à appliquer à ses points : au départ, c'est l'identité ; quand on rentre dans un Zoom (k, g), les points de g doivent d'abord être agrandis d'un facteur k, puis subir la transformation qu'on avait déjà.

Écrivez une fonction dessine_avec : (point -> point) -> figure -> unit telle que dessine_avec t f dessine l'image de la figure f par la transformation t, puis dessine : figure -> unit. Utilisez List.iter pour les groupes.

Question 26 : Sierpiński, le retour

---

Avec ce type, une fractale se décrit très simplement : le triangle de Sierpiński de profondeur (dans le triangle de sommets , , ) est formé de trois copies de celui de profondeur , réduites de moitié, dont deux sont déplacées.

Écrivez une fonction sierpinski_fig : int -> figure. Pour , c'est le triangle lui-même (un Groupe de trois Trait).

Question 27

---

Dans votre sierpinski_fig, combien d'appels récursifs faites-vous pour construire la figure de profondeur ? Si vous en faites trois, modifiez votre fonction pour n'en faire qu'un.

Combien de constructeurs (Trait, Groupe, ...) sont alors créés en mémoire pour construire sierpinski_fig n ? Comparez avec nb_traits (sierpinski_fig n).

Question 28 (plus difficile) : l'arbre de Pythagore

---

L'arbre de Pythagore de profondeur est formé du carré unité, sur le côté supérieur duquel on pose deux arbres de Pythagore de profondeur , réduits d'un facteur et tournés de , de façon à ce que leurs carrés de base forment un triangle rectangle isocèle avec le côté supérieur du carré. (Pour , il n'y a que le carré.)

Écrivez pythagore : int -> figure et dessinez pythagore 10.

Rappel : tableaux

---

• Un tableau a une taille fixée à sa création, et ses cases sont modifiables. Son type est 'a array.
• [| 1; 2; 3 |] est un tableau. Array.make n x crée un tableau de taille n dont toutes les cases valent x, Array.init n f crée le tableau [| f 0; f 1; ...; f (n-1) |].
• Array.length t est sa taille, t.(i) sa case d'indice i (de 0 à Array.length t - 1), et t.(i) <- v modifie cette case (c'est une expression de type unit).
• Array.iter, Array.map, Array.for_all, Array.exists, Array.mem... fonctionnent comme pour les listes.

Rappel : boucles

---

• for i = a to b do ... done exécute le corps pour i valant a, a + 1, ..., b (les deux bornes sont incluses). Il n'y a rien à faire si b < a.
• while condition do ... done répète le corps tant que la condition est vraie.
• Le corps d'une boucle est de type unit, et la boucle aussi.

Question 29

---

Écrivez une fonction retourne_inverse : bool array -> bool array qui renvoie un nouveau tableau : le tableau donné, lu de droite à gauche, avec ses valeurs inversées. Écrivez-en deux versions : une avec Array.make et une boucle for, une avec Array.init (sans boucle).

Question 30

---

Écrivez une fonction récursive plis : int -> bool array qui renvoie la suite des plis après n pliages (le tableau vide [||] pour ). Si le tableau de l'étape a cases, celui de l'étape en a : créez-le avec Array.make, puis remplissez-le avec une boucle.

Rappel : références

---

Une référence est une « boîte » dont on peut changer le contenu :

• let r = ref 0 crée une référence (de type int ref) contenant 0 ;
• !r est son contenu, et r := 5 le remplace (expression de type unit) ;
• incr r et decr r ajoutent ou retirent 1 à une référence entière.

Les variables créées par let ne changent jamais : let x = 1 in ... x = x + 1 compare x à x + 1 (et vaut false), il ne modifie rien !

Question 31

---

On travaille avec des coordonnées entières : la tortue va dans l'une des 4 directions [| (1, 0); (0, 1); (-1, 0); (0, -1) |] (droite, haut, gauche, bas), et on retient seulement l'indice de sa direction dans ce tableau. Tourner à gauche revient à ajouter 1 à cet indice, tourner à droite à retirer 1, modulo 4.

Écrivez une fonction dragon : bool array -> unit qui dessine la courbe correspondant à une suite de plis : la tortue part de vers la droite, avance, puis pour chaque pli, tourne et avance. Utilisez deux références (position et direction), et float_of_int pour appeler segment. Dessinez dragon (plis 12), et rejouez le tracé.

Attention au modulo

---

En OCaml, a mod b a le signe de a : (-1) mod 4 vaut -1, pas 3. Pour tourner à droite, calculez plutôt (d + 3) mod 4.

Rappel : tables de hachage (module

---

Hashtbl) Un dictionnaire associe des valeurs à des clés. Le module Hashtbl en fournit une version mutable, efficace (opérations en temps constant en moyenne) :

• let h = Hashtbl.create 100 crée une table vide (le nombre n'a pas d'importance) ;
• Hashtbl.add h cle valeur ajoute une association, Hashtbl.remove h cle la supprime ;
• Hashtbl.mem h cle teste si la clé est présente ;
• Hashtbl.find h cle renvoie la valeur associée (et lève une exception si la clé est absente), Hashtbl.find_opt h cle renvoie une option ;
• Hashtbl.iter (fun cle valeur -> ...) h parcourt toutes les associations.

Les clés peuvent être de presque n'importe quel type : entiers, chaînes, couples de points...

Attention : n'ajoutez pas deux fois la même clé avec Hashtbl.add (utilisez Hashtbl.remove d'abord, ou Hashtbl.mem pour tester).

Question 32

---

Écrivez une fonction sommets_visites : bool array -> (int * int, int) Hashtbl.t qui renvoie une table associant à chaque point (à coordonnées entières) par lequel passe la tortue le nombre de fois où elle y passe (le point de départ compte pour une fois). Reprenez le code de dragon, sans dessiner.

Utilisez-la pour répondre aux questions suivantes, pour plis 12 :

1. La courbe passe-t-elle plusieurs fois par un même point ? Combien de points sont visités deux fois ? Plus de deux fois ?
2. (plus dur) Passe-t-elle plusieurs fois par un même segment ? Pour le savoir, écrivez une fonction similaire, dont les clés sont les segments parcourus. Comment faire pour que le segment de à et celui de à aient la même clé ?

Rappel : caractères et chaînes

---

• Un caractère (char) s'écrit entre apostrophes : 'F', '+'. Une chaîne (string) entre guillemets : "F+F".
• String.length s est la longueur de s, et s.[i] son caractère d'indice i (de 0 à String.length s - 1). Les chaînes ne sont pas modifiables.
• s1 ^ s2 concatène deux chaînes (en recopiant les deux : à éviter dans une boucle).

Question 33

---

Écrivez une fonction liste_de_chaine : string -> char list qui renvoie la liste des caractères d'une chaîne, dans l'ordre (par exemple avec une fonction auxiliaire récursive qui prend en argument un indice).

Question 34

---

1. Écrivez une fonction regles : (char * string) list -> (char, char list) Hashtbl.t qui crée la table des règles à partir d'une liste de couples (lettre, mot de remplacement). Par exemple regles [('F', "F+F-F-F+F")].
2. Écrivez une fonction récursive reecrit : (char, char list) Hashtbl.t -> char list -> char list qui applique une étape de réécriture à un mot. Utilisez Hashtbl.find_opt.
3. Écrivez une fonction iteree : int -> (char, char list) Hashtbl.t -> char list -> char list qui applique n étapes de réécriture.

Question 35

---

Que vaut le coût de reecrit r mot, en fonction de la longueur de mot et des longueurs des règles ? Est-ce que l'utilisation de @ pose ici un problème ?

Question 36 : la tortue

---

Écrivez une fonction tortue : float -> char list -> unit telle que tortue delta mot interprète le mot comme expliqué plus haut. La tortue part de , vers la droite, et avance d'une longueur 1. Utilisez des références pour la position et l'angle, avance, et List.iter.

Dessinez la courbe de Koch carrée de profondeur 4 (avec ), puis le flocon de Koch : axiome F--F--F, règle F → F+F--F+F, .

match dans une fonction anonyme Dans List.iter (fun c -> match c with ... ) mot, les parenthèses autour de la fonction anonyme sont indispensables : sinon, le dernier cas du match « avalerait » la suite.

Rappel : piles (module

---

Stack)

• let p = Stack.create () crée une pile vide ;
• Stack.push x p empile x ;
• Stack.pop p dépile et renvoie l'élément du sommet (exception si la pile est vide) ;
• Stack.is_empty p teste si la pile est vide.

(Le module Queue fournit les mêmes fonctions pour une file : Queue.create, Queue.push, Queue.pop, Queue.is_empty.)

Question 37

---

Écrivez une fonction tortue_branches : float -> float -> char list -> unit qui gère aussi les crochets. Le premier argument est l'angle de départ de la tortue (pour que les plantes poussent vers le haut).

Dessinez ensuite la plante d'axiome X, de règles X → F+[[X]-X]-F[-FX]+X et F → FF, avec , un angle de départ de , et 5 étapes. Rejouez le tracé !

Rappel : récursivité terminale

---

Un appel récursif est terminal quand son résultat est directement le résultat de la fonction : il n'y a plus rien à faire après. Une fonction dont tous les appels récursifs sont terminaux n'utilise pas la pile : elle s'exécute comme une boucle.

Pour rendre une fonction récursive terminale, on utilise en général un accumulateur : un argument supplémentaire qui contient le résultat « en cours de construction ».

(* pas terminale : il reste à faire 1 + ... après l'appel *)
let rec longueur l = match l with
  | [] -> 0
  | _ :: reste -> 1 + longueur reste

(* terminale : acc contient la longueur de ce qui a déjà été parcouru *)
let rec longueur_acc l acc = match l with
  | [] -> acc
  | _ :: reste -> longueur_acc reste (acc + 1)

Question 38 (plus difficile) : récursivité terminale

---

1. Écrivez une fonction récursive terminale ajoute_envers : 'a list -> 'a list -> 'a list telle que ajoute_envers l acc renvoie les éléments de l dans l'ordre inverse, suivis des éléments de acc. Par exemple, ajoute_envers [1; 2; 3] [4; 5] vaut [3; 2; 1; 4; 5]. En déduire une fonction renverse : 'a list -> 'a list qui renverse une liste.
2. Écrivez une version récursive terminale reecrit_t de reecrit, et la fonction iteree_t correspondante. Dessinez la plante avec 6 étapes.

Question 39 : à vous de jouer

---

Voici quelques L-systèmes classiques. Pour certains, plusieurs lettres font avancer la tortue : modifiez votre tortue pour qu'elle prenne en argument la liste des lettres qui tracent (et utilisez List.mem).

Nom	Axiome	Règles		Lettres qui tracent
Dragon	FX	X → X+YF+, Y → -FX-Y		F
Pointe de flèche de Sierpiński	A	A → B-A-B, B → A+B+A		A, B
Courbe de Gosper	A	A → A-B--B+A++AA+B-, B → +A-BB--B-A++A+B		A, B
Buisson	F	F → FF+[+F-F-F]-[-F+F+F]		F

Utilisez iteree_t si vous l'avez écrite. Comparez la courbe du dragon obtenue avec celle de la partie V. Puis inventez votre propre fractale !