Le langage fonctionnel Caml

Pour construire un n-uplet, Caml offre le constructeur multiinfixé « , ». Par exemple :

#("Jean" ^ "-Paul", 25 + 1, true);;
- : string * int * bool = "Jean-Paul", 26, true

La sémantique de ce constructeur est la suivante :

Attention ! l'expression «  e ₁ , e ₂  » construit une paire, l'expression «  e ₁ , e ₂ , e ₃  » construit un triplet, et l'expression «  e ₁ , e ₂ , e ₃ , …, e _n  » construit un n-uplet. Ce ne sont pas des valeurs de même type. Les constructeurs * et, ne sont donc pas associatifs comme le montre le programme suivant :

#(1, 2), 3;;
- : (int * int) * int = (1, 2), 3
#1, (2, 3);;
- : int * (int * int) = 1, (2, 3)
#1, 2, 3;;
- : int * int * int = 1, 2, 3

La première expression a pour valeur une paire formée d'une paire d'entiers et d'un entier, la seconde une paire formée d'un entier et d'une paire d'entiers et la troisième un triplet d'entiers.

En Caml l'égalité n'est définie que sur des valeurs de même type. Deux n-uplets de même type sont structurellement égaux si leurs éléments de même rang sont structurellement égaux.

L'accès aux éléments d'un n-uplet se fait normalement par filtrage comme nous le verrons au §III.C. Cependant, dans le cas des paires, deux fonctions prédéfinies sont disponibles fst et snd qui permettent d'accéder respectivement à la première et à la seconde composante. En voici un exemple :

#fst ("un", "deux");;
- : string = "un"
#snd ("un", "deux");;
- : string = "deux"

Ces deux fonctions étant polymorphes nous les étudierons au §IV.B consacré au polymorphisme.

Les filtres peuvent être utilisés dans les clauses let des définitions globales ou locales. Les noms définis sont les identificateurs présents dans les filtres et les liaisons sont obtenues par filtrage.

Soit F ₁ , …, F_n des filtres, une définition globale a la forme générale suivante :

let F1 = e1 and … and Fn = en ;;

Et une expression à définitions locales a la forme générale suivante :

let F1 = e1 and … and Fn = en in e;;

Par exemple :

#let (lon, lar, haut) = (15, 5, 20);;
haut : int = 20
lar : int = 5
lon : int = 15
#let (lon, lar, haut) = (15, 5, 20) in lon * lar * haut;;
- : int = 1500

On notera que ces nouvelles clauses let généralisent celles étudiées au §I.E, puisqu'un identificateur est un cas particulier de filtre. Les règles d'évaluation et de typage sont elles-mêmes généralisées de la façon suivante :

Le filtrage fournit un moyen élégant de définir une fonction : la définition par cas , qui généralise le mode de définition que nous avons présenté au chapitre 2. Si F ₁ , …, F_n sont des filtres et e ₁ , …, e_n sont des expressions, l'expression :

function F1 -> e1 | … | Fn -> en

définit une fonction qui appliquée à un argument x rend la valeur de l'expression e_i associée au premier filtre F_i qui filtre x , en essayant successivement les filtres F ₁ , …, F_n dans cet ordre. Pour des raisons de symétrie, on peut placer une | devant le premier cas. Par exemple :

#let nul_ou_non_nul =
    function
        | 0 -> "nul"
        | _ -> "non nul";;
nul_ou_non_nul : int -> string = <fun>
#nul_ou_non_nul 0;;
- : string = "nul"
#nul_ou_non_nul 1;;
- : string = "non nul"

On remarquera que le mode de définition que nous avons présenté au chapitre 2 (function x -> e ) n'est qu'un cas particulier de définition par cas puisqu'un nom de variable est un filtre.

Lorsque la définition ne comporte qu'un seul cas on peut écrire :

let n F = e

au lieu de ;

let n = function F -> e

Par exemple :

#let moyenne (x, y) = (x +. y) /. 2.;;
moyenne : float * float -> float = <fun>

Les règles de typage et d'évaluation d'une définition de fonction énoncées au §II.A, sont généralisées de la façon suivante :

Une opération classique, dans la plupart des langages de programmation, est la sélection qui choisit l'action à réaliser en fonction de la valeur d'une expression (par exemple l'instruction « switch » de C). En Caml, cette opération se traduit par l'application d'une fonction définie par cas :

(function F1 -> e1 | … | Fn -> en) e

qui s'écrit aussi :

match e with F1 -> e1 | … | Fn -> en

La valeur calculée dépend de la valeur de e et les filtres F ₁ , …, F_n jouent le rôle de sélecteur.

Par exemple la fonction suivante donne la traduction en anglais des 4 saisons :

#(match x with
    | "printemps" -> "spring"
    | "été" -> "summer"
    | "automne" -> "autumn"
    | "hiver" -> "winter"
    | _ -> "Ce n'est pas une saison !") automne;;
- : string = "autumn"

La construction if…then…else que nous avons étudiée au §1.4 n'est pas une construction de base de Caml. Elle est un cas particulier d'application d'une fonction de type de départ bool. On a :

if e1 then e2 else e3
≡ (function true -> e2 | false -> e3) e1
≡ match e1 with true -> e2 | false -> e3

Lorsqu'une fonction est définie par filtrage, toutes les occurrences du type de départ de cette fonction doivent être prises en compte. Si l'on ne le fait pas, la définition sera acceptée mais le message suivant sera affiché :

> Warning: pattern matching is not exhaustive.

Par exemple :

#let un_deux_trois = function
    | 1 -> "un"
    | 2 -> "deux"
    | 3 -> "trois";;
Toplevel input:
>....................function
>     | 1 -> "un"
>     | 2 -> "deux"
>     | 3 -> "trois"..
Warning: this matching is not exhaustive.
un_deux_trois : int -> string = <fun>

On veut définir une fonction applicable à tout entier mais seuls les entiers 1, 2 et 3 ont été considérés. Il faut donc définir la valeur de cette fonction pour les autres entiers. Par exemple :

#let un_deux_trois = function
    | 1 -> "un"
    | 2 -> "deux"
    | 3 -> "trois"
    | _ -> "pas un, pas deux, pas trois";;
un_deux_trois : int -> string = <fun>

Le constructeur de liste est l'opérateur infixé et associatif à droite :: qui construit une liste à partir de sa tête et de sa queue (c'est l'opérateur cons de Lisp). Par exemple :

#"printemps" :: "été" :: "automne" :: "hiver" :: [];;
- : string list = ["printemps"; "été"; "automne"; "hiver"]
#("un", 1) :: ("deux", 1 + 1) :: ("trois", 2 + 1) :: [];;
- : (string * int) list = ["un", 1; "deux", 2; "trois", 3]

La sémantique du constructeur de liste est la suivante :

L'équivalence syntaxique suivante permet d'améliorer la lisibilité de la construction d'une liste de longueur connue :

[e1; … ; en]  e1 :: … :: en :: []

Par exemple :

#[("un", 0 + 1); ("deux", 1 + 1); ("trois", 2 + 1)];;
- : (string * int) list = ["un", 1; "deux", 2; "trois", 3]

Deux listes vides sont structurellement égales. Deux listes non vides de même type, sont structurellement égales si leurs têtes et leurs queues sont structurellement égales.

La tête et la queue d'une liste peuvent être extraites par les fonctions prédéfinies hd et tl ou bien par filtrage comme nous le verrons ci-dessous. La concaténation de deux listes est réalisée par l'opérateur prédéfini et infixé @. Par exemple :

#let les_saisons = ["printemps"; "été"; "automne"; "hiver"];;
les_saisons : string list = ["printemps"; "été"; "automne"; "hiver"]
#hd;; (* tête *)
- : 'a list -> 'a = <fun>
#hd les_saisons;;
- : string = "printemps"
#tl;; (* queue *)
- : 'a list -> 'a list = <fun>
#tl les_saisons;;
- : string list = ["été"; "automne"; "hiver"]
#prefix @;; (* concatenation *)
- : 'a list -> 'a list -> 'a list = <fun>
#[hd les_saisons] @ (tl les_saisons);;
- : string list = ["printemps"; "été"; "automne"; "hiver"]

Trois filtres sont disponibles pour les listes : le premier pour la liste vide, le second pour accéder à la tête et à la queue d'une liste et le troisième pour accéder aux éléments d'une liste de longueur connue :

1. [] filtre []. On a env_filtré ([], []) = {}.
2. F ₁ :: F ₂ filtre toute liste l dont la tête t est filtrée par F ₁ et la queue q est filtrée par F ₂ . On a env_filtré ( F ₁ :: F ₂ , l ) = env_filtré ( F ₁ , t )  env_filtré ( F ₂ , q ).
3. [ F ₁ ; …; F _n ] filtre toute liste [ v ₁ ; … ; v _n ] telle que, pour tout i de 1 à n , F_i filtre v i . On a env_filtré ([ F ₁ ; …; F _n ], l ) = env_filtré ( F ₁ , v ₁ )  …  env_filtré ( F _n , v _n ).

Par exemple :

#match ["Le"; "langage"; "Caml"] with
    | [] -> "Liste vide !"
    | m::_ -> "Le premier mot est " ^ m;;
- : string = "Le premier mot est Le"
#match les_saisons with
    | [] -> "Y a plus de saisons !"
    | [s1; s2; s3; s4] → "Le " ^ s1 ^ ", l'" ^ s2 ^ ", l'" ^ s3 ^ " et l'" ^ s4;;
- : string = "Le printemps, l'été, l'automne et l'hiver"

Les listes sont associées aux langages fonctionnels depuis la naissance de ceux-ci (le nom du premier des langages fonctionnels, Lisp, est un acronyme pour « List processing »). Un grand nombre d'opérations sur cette structure de données sont devenues des classiques. La plupart sont d'ailleurs prédéfinies en Caml (dans le module list de la bibliothèque de base ). Nous allons en étudier quelques unes afin de mettre en évidence la technique de traitement des listes qui est basée sur la récurrence structurelle :

PRINCIPE DE RECURRENCE STRUCTURELLE SUR LES LISTES. Si une propriété P est vraie pour [] et si dès que P est vraie pour l alors P est vraie pour x :: l , alors P est vraie pour toutes les listes.

Compter les éléments d'une liste

Pour compter les éléments d'une liste on utilise la propriété suivante : le nombre d'éléments d'une liste vide est égal à 0 et le nombre d'éléments d'une liste non vide est égal à 1 plus le nombre d'éléments de la queue de cette liste. Ce qui donne :

#let rec compter l =
    match l with
        | [] -> 0
        | _ :: q -> 1 + (compter q);;
compter : 'a list -> int = <fun>
#compter les_saisons;;
- : int = 4

Appartenance d 'un élément à une liste

Pour vérifier qu'une valeur appartient à une liste on utilise la règle suivante : si cette liste est vide, cette valeur ne lui appartient pas, si elle n'est pas vide cette valeur lui appartient soit si elle est égale à la tête de cette liste, soit si elle appartient à la queue de cette liste. Ce qui donne :

#let rec membre v l =
    match l with
        | [] -> false
        | t::q -> if t = v then true else membre v q;;
membre : 'a -> 'a list -> bool = <fun>
#membre "automne" les_saisons;;
- : bool = true
#membre "winter" les_saisons;;
- : bool = false

Select …from…where

Le langage SQL a popularisé l'opérateur « select…from…where », qui appliqué à un ensemble de tables : (i) en construit le produit cartésien, (ii) le restreint aux lignes qui vérifient une condition donnée, et enfin (iii) le projette sur certaines colonnes. Nous en donnons ici une version simplifiée, la fonction select_from_where qui appliquée à une fonction f , à une liste l et à un prédicat p extrait la liste formée par l'application de la fonction f à chaque élément de l qui vérifie le prédicat p .

Pour définir la fonction select_from_where nous utiliserons deux fonctions intermédiaires filter et map. La fonction filter élimine d'une liste les éléments qui ne vérifient pas un prédicat donné. Par exemple :

filter [1; 2; 3; 4; 5; 6; 7; 8; 9] est_pair = [2; 4; 6; 8]

Elle peut se définir de la façon suivante :

• le filtrage d'une liste vide produit une liste vide ;
• le filtrage d'une liste l de tête x par un prédicat p produit :

• la liste ayant pour tête x et pour queue le résultat du filtrage de la queue de l par p , si x vérifie p (on garde x ),
• le résultat du filtrage de la queue de l par p , si x ne vérifie pas p (on élimine x ).

La fonction map applique une fonction à chaque élément d'une liste. Par exemple :

map [1; 2; 3] est_pair = [false; true; false]

Elle peut se définir de la façon suivante :

• le « mapping » d'une liste vide produit une liste vide ;
• le « mapping » d'une liste l de tête x par une fonction f produit la liste ayant pour tête f x et pour queue le « mapping » de la queue de l par f .

En utilisant ces deux fonctions on obtient :

select_from_where f l p = map (filter l p) f.

D'où la définition complète de select_from_where en Caml :

let select_from_where f l p =
    let rec
        filter l p =
            match l with
                | [] -> []
                | t::q -> if p t then t::(filter q p) else (filter q p)
    and
        map l f =
            match l with
                | [] -> []
                | t::q -> (f t)::(map q f)
    in
        map (filter l p) f;;
    select_from_where : ('a -> 'b) -> 'a list -> ('a -> bool) -> 'b list = <fun>

Considérons maintenant une liste d'enfants, où chaque enfant est représenté par son prénom et son âge :

#let les_enfants = [("Claire", 13); ("Alain", 8); ("Paul", 12); ("Marie", 5)];;
les_enfants : (string * int) list = ["Claire", 13; "Alain", 8; "Paul", 12; "Marie", 5]

La requête « Quels sont les prénoms des enfants de plus de 10 ans » peut s'exprimer de la façon suivante :

#let prénom = function (p, a) -> p
    and plus_de_10_ans = function (p, a) -> a > 10
in
    select_from_where prénom les_enfants plus_de_10_ans;;
- : string list = ["Claire"; "Paul"]

Remarquons enfin, que la fonction select_from_where aurait pu être définie directement de la façon suivante :

#let rec select_from_where f l p =
    match l with
        | [] -> []
        | t::q -> if p t then
                (f t)::(select_from_where f q p)
            else
                (select_from_where f q p);;
select_from_where : ('a -> 'b) -> 'a list -> ('a -> bool) -> 'b list = <fun>