Structures de données polymorphes

    Toutes les données ne sont pas forcément d'un type de base. Certaines sont polymorphes c'est-à-dire qu'elles possèdent un type dont certaines composantes ne sont pas complètement déterminées mais comporte des variables de type. L'exemple le plus simple est la liste vide, qui est évidemment une liste d'entiers (int list) ou une liste de booléens (bool list) et plus généralement une liste de ``n'importe quel type'', ce que Caml symbolise par 'a (et la liste vide polymorphe est du type 'a list).

On définit des structures de données polymorphes en faisant précéder le nom de leur type par la liste de ses paramètres de type. Par exemple:

type 'a liste =
   | Nulle
   | Cons of 'a * 'a liste;;

ou encore pour des tables polymorphes:

type ('a, 'b) table = {nb_entrées : int; contenu : ('a * 'b) vect};;

Les listes prédéfinies en Caml forment le type list et sont équivalentes à notre type liste. La liste vide est symbolisée par [] et le constructeur de liste est noté ::, et correspond à notre constructeur Cons. Pour plus de commodité, l'opérateur :: est infixe: x :: l représente la liste qui commence par x, suivi des éléments de la liste l. En outre, on dispose d'une syntaxe légère pour construire des listes littérales: on écrit les éléments séparés par des point-virgules, le tout entre crochets [ et ].

#let l = [1; 2; 3];;
l : int list = [1; 2; 3]
#let ll = 0 :: l;;
ll : int list = [0; 1; 2; 3]

Les listes sont munies de nombreuses opérations prédéfinies, dont les fonctionnelles de parcours ou d'itération, map, do_list ou it_list, ou encore la concaténation @. À titre d'exemple emblématique de fonction définie sur les listes, nous redéfinissons la fonctionnelle map qui applique une fonction sur tous les éléments d'une liste.

#let print_list l = do_list print_int l;;
print_list : int list -> unit = <fun>
#print_list l;;
123- : unit = ()
#let rec map f l =
  match l with
  | [] -> []
  | x :: rest -> f x :: map f rest;;
map : ('a -> 'b) -> 'a list -> 'b list = <fun>
#let succ_l = map (function x -> x + 1) ll;;
succ_l : int list = [1; 2; 3; 4]
#print_list succ_l;;
1234- : unit = ()
#let somme l = it_list (function x -> function y -> x + y) 0 l;;
somme : int list -> int = <fun>
#somme ll;;
- : int = 6
#somme succ_l;;
- : int = 10

La manipulation des listes est grandement facilitée par la gestion automatique de la mémoire, puisque l'allocation et la désallocation sont prises en charge par le gestionnaire de mémoire et son programme de récupération automatique des structures devenues inutiles (le ramasse-miettes, ou glaneur de cellules, ou GC (garbage collector)).

En Caml, la gestion mémoire est automatique.