Retour au sommaire.
Grammaires, écriture et lecture.
Considérons maintenant le type suivant, pour les arbres binaires :
type 'elt bintree =
| Leaf
| Node of 'elt bintree * 'elt * 'elt bintree
On peut facilement écrire un formatteur pour ce type :
let rec format_bin_tree elt_formatter fmt = function
| Leaf ->
Format.fprintf fmt "Leaf"
| Node (left,root,right) ->
Format.fprintf fmt
"(@[<v 2>@ left: %a,@ root:%a,@ right:%a@])"
(format_bin_tree elt_formatter) left
elt_formatter root
(format_bin_tree elt_formatter) right
let format_int_tree = format_bin_tree Format.pp_print_int
On observe donc l'arbre et on utiliser deux formatteurs différents selon la nature de l'arbre, nœud ou feuille. Cette solution, toute valide qu'elle soit, n'utilise pas uniquement des combinateurs : nous sommes forcés de prendre l'arbre en argument et de l'observer. Soyons curieux, et bien que cela semble inutile à première vue, demandons-nous s'il est possible de faire une fonction de conversion sans référencer l'arbre ?
Reprenons le module de la section précédente, et ajoutons-y quelques fonctions, de sorte qu'on obtient le module suivant :
module Print :
sig
type 'value t
val to_string : 'any t -> 'any -> string
val int : int t
val float : float t
val char : char t
val bool : bool t
val string : string t
val cst : string -> 'any t
val (++) : 'value t -> 'value t -> 'value t
val comap : 'im t -> f:('value -> 'im) -> 'value t
val (=|>) : 'im t -> ('value -> 'im) -> 'value t
type 'value conditional
val (||) : 'value conditional -> 'value t -> 'value t
val optionnally : ('value -> 'im option) -> 'im t -> 'value conditional
val ( =? ) : ('value -> 'im option) -> 'im t -> 'value conditional
val pair : 'left t -> 'right t -> ('left * 'right) t
val triple : 'left t -> 'middle t -> 'right t -> ('left * 'middle * 'right) t
val list : 'elt t -> 'elt list t
val fix : ('value t -> 'value t) -> 'value t
end
Le principal ajout est le type conditional et les fonctions (||) et (=?). Nous allons voir par l'exemple comment ils s'utilisent. Ajoutons deux fonctions pour l'arbre binaire; ces deux fonctions sont des sortes d'accesseurs soit aux valeurs de la feuille (rien) soit au valeurs du nœud (un triplet).
type 'elt bin_tree =
| Leaf
| Node of 'elt bin_tree * 'elt * 'elt bin_tree
let observe_leaf = function
| Leaf -> Some ()
| Node _ -> None
let observe_node = function
| Leaf -> None
| Node (left,root,right) -> Some (left,root,right)
Maintenant :
let bin_tree_to_string elt =
let open Print in
let tree =
fix @@ fun tree ->
observe_node =? cst "Node " ++ triple tree elt tree
|| observe_leaf =? cst "Leaf"
|| cst "not possible"
in
Print.to_string tree
let () =
Node (Node (Leaf,1,Leaf), 2, Node (Node (Leaf,3,Leaf),4,Leaf))
|> bin_tree_to_string Print.int
|> Printf.printf "%s"
En fait ...=?... || ... s'utilise comme un opérateur ternaire, le type conditional est là uniquement pour pouvoir attribuer un type à la première partie. On comprend donc que le premier terme permet de trouver une représentation de l'objet à écrire, mais peut échouer à le représenter. Le deuxième terme définit comment écrire la représentation, et le troisième terme est la solution de repli : comment écrire si l'objet n'est pas ainsi représentable.
À quoi bon ? on est ici dans le domaine de l'astuce et cette solution n'apporte pas grand chose de plus par rapport à prendre l'objet et faire un filtrage par motif, comme avec Printf. Certes, mais cette solution met en évidence la grammaire des chaînes de caractères encodant des arbres :
tree :=
"Node" "(" tree "," elt "," tree ")"
| "Leaf"
Et comme on a des actions associés à chaque règle de la grammaire lorsqu'on écrit un analyseur syntaxique, ici on a aussi une sorte d'action (inversée, une observation du coup) pour chaque règle : observe_node et observe_leaf. Il n'y a plus qu'une question à se poser : peut-on utiliser la même technique, non pour écrire, mais pour lire ? Pourrait-on avoir un lecteur d'arbre dont le programme soit le suivant ?
let make_node (left,root,right) = Node (left,root,right)
let make_leaf () = Leaf
let bin_tree_to_string (elt: 'elt Read.t) : 'elt bin_tree Read.t =
let open Read in
fix @@ fun tree ->
(make_node *> cst "Node " ++ triple tree elt tree)
|| (make_leaf *> cst "Leaf")
Affirmatif, et c'est ce que nous allons étudier par la suite.
Notons que la lecture de séquence de caractères peut être faite avec Scanf, qui est assez puissant pour par exemple lire des arbres :
let rec read_tree read_elt in_chan =
let create_node left root right = Node (left root right) in
try
Scanf.bscanf in_chan " Node (%r, %r, %r)"
(read_tree read_elt)
read_elt
(read_tree read_elt)
create_node
with Scanf.Scan_failure _ -> Scanf.bscanf in_chan " Leaf" Leaf
Retour au sommaire.
