Laurent Le Brun

Ceci est un exemple de code F# pour manipuler facilement du XML. Ce billet est un "hors-série" : il ne fait pas partie du cours et peut être ignoré sans problème. De plus, il utilise plusieurs concepts qui seront détaillés plus tard. Néanmoins, ça peut intéresser tout le monde.

L'objectif est de manipuler simplement du XML. Imaginons que l'on ait un fichier XML qui représente un arbre arithmétique et que l'on souhaite l'évaluer. Prenons le contenu suivant :

<arith>
<expr>
  <node op="+">
    <val>42</val>
    <val>18</val>
    <node op="*">
      <val>10</val>
      <val>20</val>
    </node>
  </node>
</expr>

<expr>
  <node op="-">
    <val>4</val>
  </node>
</expr>

</arith>

Commençons d'abord par définir les opérateurs arithmétiques. On associe à chaque chaine une fonction. Par souci de simplicité, les fonctions utilisent un nombre quelconque d'arguments (c'est un tableau). Comme en Lisp, + 2 3 4 correspond à 2 + 3 + 4. Les opérateurs sont stockés dans une map : c'est un arbre binaire (entièrement fonctionnel), qui garantit un accès en temps logarithmique. On s'en fiche un peu ici, puisque l'on a peu d'éléments, mais soyons extensibles. Au passage, remarquez comment l'indentation désambiguise le code : les éléments de la liste sont simplement alignés. L'élément "" correspond à la balise "expr". Puisqu'elle n'a qu'un seul node, on le renvoie directement.

[fsharp]
#light

open System.IO
open System.Xml.Serialization

// List of operators
let ops =
 Map.of_seq
  [ "-", fun l ->
           if Seq.length l = 1 then - l.[0]
           else Seq.fold1 (-) l
    "+", fun l -> Seq.fold (+) 0 l
    "*", fun l -> Seq.fold ( *) 1 l
    "", fun l -> l.[0] ]

Il faut ensuite définir la structure de l'arbre. Un nœud possède un opérateur, une liste d'entiers et une liste de fils. Cette représentation est discutable, mais c'est pour l'exemple. L'avantage est d'être proche de la structure XML. Pour associer les identifiants aux balises XML, on utilise les attributs de sérialisation .NET. XmlAttribute correspond à l'attribut d'une balise et XmlElement à un élément XML. Le type ResizeArray est nécessaire pour stocker plusieurs éléments (c'est une convention dans .NET).

[fsharp]
// expression tree
type expr =
  new() = {operator = ""; values = null; expr = null}
  [<XmlAttribute("op")>]
  val mutable operator: string
  [<XmlElement("val")>]
  val values: int ResizeArray
  [<XmlElement("node")>]
  val expr: expr ResizeArray

On définit ensuite la racine du document XML. Arith est un objet qui contient l'ensemble des expr du fichier.

[fsharp]
// xml root (contains a list of expressions)
[<XmlRoot("arith")>]
type arith =
  [<XmlElement("expr")>]
  val expr: expr ResizeArray
  new() = {expr = null}

Vient ensuite la fonction d'évaluation. Elle est relativement simple : on évalue récursivement tous les fils, puis on récupère les valeurs simples et on applique la fonction correspondant à l'opérateur.

[fsharp]
// Evaluate an expression
let rec eval (e: expr) =
  e.expr |> ResizeArray.map eval
         |> ResizeArray.append e.values
         |> ops.[e.operator]

Et enfin, le point d'entrée du programme. On charge le fichier XML, on le dé-sérialise (cela créera un objet du type défini, tous les champs seront remplis automagiquement). On itère sur les éléments de expr. Chacun d'eux est évalué puis affiché.

[fsharp]
// Main : load the XML and print results
let () =
  use xmlDoc = new StreamReader("data.xml")
  let xml: arith = XmlSerializer(typeof<arith>).Deserialize(xmlDoc) |> unbox
  xml.expr |> Seq.iter (eval >> printfn "%d")

De la même façon, il existe une méthode .NET pour sérialiser un objet. Si on avait effectué des modifications sur l'objet, ou si on en avait créé un autre, il aurait été possible de l'enregistrer au format XML.

Évidemment, tout l'exemple est écrit en fonctionnel pur. Il y a des fonctions d'ordre supérieur, de l'application partielle, de la composition de fonctions, etc. Tout n'est pas parfait, puisque l'outil de dé-sérialisation m'a obligé à déclarer operator en mutable. Il m'a aussi obligé à définir un constructeur sans argument (d'où utilisation de null). Mais au final, ça m'a semblé intéressant de le montrer ici.

PS : je ne sais pas si on peut utiliser cette technique sur un type somme. Je pense que oui, mais il faut que je regarde la syntaxe exacte.