Programmation Fonctionnelle, TP5

Figure
Version & licenses
Creative Commons License

Programmation Fonctionnelle, TP5 : dessin d'arbres binaires.

Guyslain Naves

Dans ce TP, nous définissons et manipulons des arbres binaires et écrivons des algorithmes simples pour les dessiner. La semaine prochaine, nous verrons un algorithme plus complexe pour obtenir des dessins de qualité pour les arbres binaires, nous réutiliserons donc le code de cette semaine.

Vous pouvez utiliser Core.Std pour les modules List et Option. On utilisera Gg et Vg pour dessiner les arbres, QCheck pour tester.

Types des arbres binaires.

Recopiez ce type algébrique pour représenter les arbres binaires, paramêtré par le type de l'information associée à chaque nœud. On définit aussi un générateur aléatoire d'arbres binaires, de sorte à pouvoir utiliser QCheck pour tester les fonctions d'arbres. Il est paramétré par le type des nœuds, on fournit aussi deux générateurs pour des arbres avec des nœuds entiers ou des nœuds sans information.

  1. type 'elt t =
  2. | Leaf
  3. | Node of 'elt t * 'elt * 'elt t


  4. module Arbitrary : sig

  5. val tree : 'elt QCheck.arbitrary -> 'elt t QCheck.arbitrary

  6. val int_tree : int t QCheck.arbitrary
  7. val unit_tree : unit t QCheck.arbitrary

  8. end = struct

  9. let rec print (elt_print : 'elt QCheck.Print.t) : 'elt t QCheck.Print.t =
  10. function
  11. | Leaf -> "Leaf"
  12. | Node (left,root,right) ->
  13. Printf.sprintf "Node (%s, %s, %s)"
  14. (print elt_print left)
  15. (elt_print root)
  16. (print elt_print right)


  17. let rec shrink (elt_shrink : 'elt QCheck.Shrink.t) : 'elt t QCheck.Shrink.t =
  18. let open QCheck.Iter in
  19. function
  20. | Leaf -> empty
  21. | Node (left,root,right) ->
  22. of_list [ left; right]
  23. <+> (shrink elt_shrink left >|= fun left_red -> Node (left_red,root,right))
  24. <+> (shrink elt_shrink right >|= fun right_red -> Node (left,root,right_red))
  25. <+> (elt_shrink root >|= fun root_red -> Node (left,root_red,right))


  26. let rec gen (elt_gen : 'elt QCheck.Gen.t) (size : int) : 'elt t QCheck.Gen.t =
  27. let open QCheck.Gen in
  28. if size <= 0 then return Leaf
  29. else
  30. 0 -- (size-1) >>= fun size_left ->
  31. let size_right = size - size_left - 1 in
  32. gen elt_gen size_left >>= fun left ->
  33. gen elt_gen size_right >>= fun right ->
  34. elt_gen >>= fun root ->
  35. return (Node (left,root,right))


  36. let tree (elt_arbitrary : 'elt QCheck.arbitrary) :
  37. 'elt t QCheck.arbitrary =
  38. let open QCheck in
  39. QCheck.make
  40. ?print:Option.(elt_arbitrary.print >>| print)
  41. ?shrink:Option.(elt_arbitrary.shrink >>| shrink)
  42. QCheck.Gen.(sized (gen elt_arbitrary.gen))

  43. let int_tree = tree QCheck.small_int
  44. let unit_tree = tree QCheck.unit

  45. end

Quelques arbres binaires particuliers.

Écrivez plusieurs fonctions, qui étant donné un entier $n$, construisent les arbres suivants. Tous les nœuds contiendront une valeur de type unit.

  • l'arbre complet de hauteur $n$,
  • le chemin gauche et le chemin droit de hauteur $n$,
  • la chenille gauche et la chenille droite de hauteur $n$.

Arbre complet de hauteur 3 Chemin gauche de hauteur 6 Chemin droit de hauteur 6 chenille gauche de hauteur 7 chenille droite de hauteur 7

  1. val complete : int -> unit bintree
  2. val left_path : int -> unit bintree
  3. val right_path : int -> unit bintree
  4. val left_caterpillar : int -> unit bintree
  5. val right_caterpillar : int -> unit bintree

Hauteur d'un arbre.

Écrivez la fonction calculant la hauteur d'un arbre binaire.

  1. val height : 'node bintree -> int

Testez que les arbres créés précédemment ont bien la hauteur souhaitée.

Image miroir d'un arbre.

Écrivez une fonction calculant l'image miroir d'un arbre, comme illustré par le dessin ci-dessous.

Un arbre quelconque euqnocleuq erbra nU
  1. val mirror : 'node bintree -> 'node bintree

Testez que les chemins gauches et droits sont miroirs l'un de l'autre, que les chenilles gauches et droite sont miroirs l'un de l'autre, que l'arbre complet est miroir de lui-même.

Map.

Écrivez la fonction map des arbres binaires. map ~f construit une image de l'arbre en remplaçant chaque nœud par son image par la fonction f.

  1. val map : 'node bintree -> f:('node -> 'im) -> 'im bintree

Reduce.

Écrivez une fonction fold des arbres binaires. Elle doit correspondre à faire un List.fold_left sur une liste des nœuds de l'arbre, en ordre infixe.

  1. val fold : f:('state -> 'node -> 'state) -> 'state -> 'node bintree -> 'state

Lister les nœuds.

Écrivez une fonction retournant une liste de nœuds d'un arbre binaire, en ordre infixe. Pour cela, on utilisera une fonction annexe insert_nodes_of tree accu, ajoutant tous les nœuds de tree dans l'accumulateur accu.

  1. val insert_nodes_of : 'node bintree -> 'node list -> 'node list
  2. val nodes_of_tree : 'node bintree -> 'node list

Lister les arêtes.

Écrivez une fonction retournant la liste des paires (parent,enfant) d'un arbre binaire (observer l'arbre sur ces deux premiers niveaux).

  1. val edges_of_tree : 'node bintree -> ('node * 'node) list

Pour des raisons d'efficacité, il est préférable d'utiliser une fonction avec un argument supplémentaire qui contient la liste des arêtes au fur et à mesure qu'elle est construite.

Dessin d'arbres.

Dessin vectoriel de l'arbre.

Pour dessiner un arbre, il faut donner une position à chaque nœud. Nous allons donc écrire une fonction :

  1. val draw : Gg.p2 tree -> Vg.img

Le principe est simple : chaque sommet est dessiné avec un cercle de même rayon (disons $0.1$), chaque arête est dessinée par un segment entre les deux nœuds correspondant.

Voici un petit rappel de Vg, cela ne remplace pas la documentation mais vous permet de savoir de quelles fonctions vous avez besoin :

  1. type image

  2. (* module for paths, describing shapes to be cut in colored papers *)
  3. module P : sig
  4. type t
  5. (* an empty shape, to start with. *)
  6. val empty : t

  7. (* moves the path to a given point, starting a new shape. *)
  8. val sub : Gg.p2 -> t -> t

  9. (* adds a segment in the current shape to a given point. *)
  10. val line : Gg.p2 -> t -> t

  11. (* adds a circular shape to the current path *)
  12. val circle : Gg.p2 -> float -> t -> t
  13. end

  14. (* module for images, can be glued on each others *)
  15. module I : sig
  16. (* a color-uniform image, infinite in all direction, in the given color. *)
  17. val const : Gg.Color -> image

  18. (* cuts an image along a given shape, this gives a new image. *)
  19. val cut : ?area:Vg.P.area -> Gg.P.t -> image -> image

  20. (* [blend foreground background] glues an image on top of another image. *)
  21. val blend : image -> image -> image
  22. end

Commencez par écrire une fonction pour le dessin d'un sommet, et pour le dessin d'une arête.

  1. val draw_node : Gg.p2 -> Vg.image
  2. val draw_edge : Gg.p2 * Gg.p2 -> Vg.image

Puis, utilisez les fonctions sur les arbres pour obtenir la liste des images de chaque nœud et de chaque arête. Utilisez Vg.I.blend pour aggréger toutes ces images en une seule image (Vg.I définit un monoïde, quel est le zéro et quel est l'opérateur binaire ?).

Vous obtenez alors :

  1. val draw_tree : Gg.p2 bintree -> Vg.image

Ajoutez le code pour l'export au format svg, en récupérant le module ExportSvg du premier TP. (L'image produite est centrée sur le point (0,5) et est un carré de longueur 20, vous pouvez changer ces paramètres en modifiant la valeur view du module.)

Positionnement des nœuds.

Il nous faut maintenant convertir notre arbre portant des informations quelconques dans ses nœuds, en un arbre dont chaque nœud contient la position du nœud dans le dessin.

Attribuons la position $(0,0)$ à la racine. Donnez un algorithme qui dessine toutes les arêtes comme des diagonales de longueur 1. Ainsi, si la position du père est $(x,y)$, la position de ses enfants est $(x-1,y-1)$ et $(x+1,y-1)$.

Testez votre fonction avec quelques arbres. Qu'en pensez-vous ?

Avec cet algorithme, la distance entre deux frères est toujours de $2$, ce qui provoque des chevauchements. Donnez un autre algorithme qui divise par deux la distance entre deux frères pour chaque profondeur, afin d'interdire les chevauchements. Plus des frères sont profonds, plus ils sont proches.

Ajoutez un troisième algorithme qui divise aussi la distance verticale entre deux profondeurs par deux à chaque niveau de l'arbre. Avec cet algorithme, tout arbre aura un dessin contenu dans un rectangle de dimension $4 \times 2$.