Laurent Le Brun

Types simples

On déclare les nouveaux types avec le mot-clé "type" :

[fsharp]
type <nom> = <définition>

Dans sa forme la plus simple, la définition peut être simplement le nom d'un type existant. Cela crée alors un alias.

[fsharp]
type ilist = int list
type ilist = list<int>  // équivalent

Les types, à l'instar des valeurs, peuvent être définis de façon simultanée avec le mot-clé "and". En revanche, nul besoin du mot-clé "rec" : tous les types peuvent être récursifs, par défaut. Il y a deux syntaxes pour noter les paramètres : après le type, avec des chevrons, ou avant le type. Par héritage de Caml, on voit souvent "int list" et "string array". Cependant, pour les types plus complexes, l'autre syntaxe est à préférer car elle est moins ambigüe.

[fsharp]
type a = b list
and b = int

De la même façon qu'une fonction peut prendre une valeur en argument, un type peut être paramétré par un autre type. Un paramètre de type commence par le caractère '. Sauf pour les types primitifs comme list et array, les paramètres de type s'écrivent

[fsharp]
type 'a foo = 'a list array // lire : ('a list) array
type 'a foo = array<'a list>

S'il y a plusieurs paramètres, la syntaxe avec les chevrons est obligatoire.

[fsharp]
type foo<'a,'b> = 'a array * 'b
type bar = foo<int, string>

> let a : bar = [|3; 5|], "test";;
val a : bar

Types somme

À l'inverse des tuples qui correspondent à un produit cartésien, la déclaration d'un type somme correspond à une union d'ensembles. Les valeurs de ce type possèdent un constructeur, qui est défini en même temps que le type. Par exemple :

[fsharp]
type foo = A | B

Le type foo possède deux constructeurs : A et B. Ces deux constructeurs sont constants (il n'ont pas d'argument).

[fsharp]
> A;;
val it : foo = A
> B;;
val it : foo = B

Ce sont les deux seules valeurs possibles ici. Cette construction se rapproche donc des enums de certains langages

Les constructeurs peuvent aussi prendre un argument :

[fsharp]
type mytype =
   | A of int
   | B of string;;

> A 4;;
val it : mytype = A 4
> B "test";;
val it : mytype = B "test"

Voici maintenant comment définir le type option que l'on a déjà rencontré :

[fsharp]
type 'a option =
  | Some of 'a
  | None

> Some "test";;
val it : string option = Some "test"
> Some 3.2;;
val it : float option = Some 3.2
> None;;
val it : 'a option = None

Arbre binaire (et pattern matching)

Voici une définition d'un arbre binaire :

[fsharp]
type 'a tree =
 | Node of 'a * 'a tree * 'a tree
 | Leaf of 'a

Un arbre est soit un nœud (composé d'un élément et de deux sous-arbres), soit une feuille (qui possède une valeur). Il existe d'autres façons de définir un arbre, on aurait par exemple pu ne pas mettre de valeur aux feuilles (et autoriser ainsi l'arbre vide).

Le pattern matching peut être utilisé sur les types somme. On utilise alors les constructeurs du type pour décomposer la valeur. Voici une façon de calculer le maximum d'un arbre :

[fsharp]
let rec max_tree = function
 | Node (elt, left, right) ->
     elt |> max (max_tree left) |> max (max_tree right)
 | Leaf elt -> elt

Et voici une façon de définir la fonction map sur un arbre. Map appelle la fonction la fonction donnée en argument sur chacun des éléments de l'arbre. La fonction ne fait pas d'effet de bord : à la place, elle duplique l'arbre.

[fsharp]
let rec map_tree f = function
 | Node (elt, left, right) ->
     Node (f elt, map_tree f left, map_tree f right)
 | Leaf elt -> Leaf (f elt)

Arbre général (et réutilisation de code)

Définissons un arbre général : chaque nœud peut avoir un nombre quelconque de fils.

[fsharp]
type 'a gtree =
 | Node of 'a gtree list
 | Empty

C'est une structure de données comme une autre et l'on souhaiterait réutiliser certains algorithmes. Par exemple, trouver le maximum de cet arbre, n'afficher que certains éléments ou savoir si un élément vérifie le prédicat donné.

Une façon de faire est de convertir l'arbre en énumérable (type seq) :

[fsharp]
let rec seq_of_tree = function
 | Node li -> [for i in li do yield! seq_of_tree i]
 | Empty -> []

On n'a écrit que 6 lignes de code dans cet exemple, mais on peut déjà faire beaucoup de choses. Par exemple, si t est un arbre de type gtree, on peut trouver son élément maximum de cette façon :

[fsharp]
t |> seq_of_tree |> Seq.max

Si on veut savoir s'il existe au moins un élément négatif, on écrira :

[fsharp]
t |> seq_of_tree |> Seq.exists (fun x -> x < 0)

Ce qui est intéressant dans ce dernier exemple, c'est que la conversion de l'arbre en énumérable est paresseuse. Dès qu'un élément négatif sera trouvé, le parcours s'arrêtera.

Si l'on préfère n'effectuer le parcours d'arbre qu'une seule fois, on peut convertir le seq en liste (resp. tableau), avec la fonction Seq.to_list (resp. Seq.to_array). Un tableau étant plus rapide à parcourir qu'un arbre, cette conversion peut améliorer les performances si les parcours sont fréquents. Mais cela a un coût en mémoire.