L'approche qualité avec OCaml

La programmation en OCaml consiste essentiellement à évaluer des expressions. Lorsqu'une expression valide suivie de ;; est entrée :

1. OCaml synthétise son type ;
2. Si la synthèse de type échoue, un message d'erreur de type est affiché ;
3. Sinon OCaml affiche son type et sa valeur.

Exemple :

# 1 + 3;;
- : int = 4

Ce qui signifie : l'expression était entière et valait 4.
Pour tirer le meilleur parti de OCaml il est de la plus grande importance de saisir la stratégie utilisée pour la synthèse de type.
Le type des opérandes doit toujours être conforme au type attendu par les opérateurs.
Ainsi l'expression suivante est mal typée et ne peut pas être évaluée :

# 1.0 + 3;;
Characters 0-3:
  1.0 + 3;;
  ^^^
This expression has type float but is here used with type int

Parce que + est l'addition entière et attend deux arguments entiers.
Dans ce cas il faut utiliser +. qui est l'addition réelle :

# 1. +. 3.;;
- : float = 4.

Remarque : contrairement à d'autres langages OCaml infère le type des opérandes à l'aide du type des opérateurs.

OCaml distingue les minuscules et les majuscules.
Les commentaires sont ouverts par (* et sont fermés par *) et ils peuvent être imbriqués.

Les types atomiques sont les nombres entiers (int), les booléens (bool), les chaînes de caractères (string), les caractères (char) et les nombres réels à virgule flottante (float). Voici la liste de ces types accompagnés de leurs opérateurs les plus courants. Ce tableau est suivi de quelques exemples d'utilisation :

Le typage remonte l'arbre d'expression, il s'applique d'abord aux constantes, puis à l'échelle des expressions élémentaires et enfin il se propage à travers toutes les expressions englobantes.

Règles de typage (expressions simples)

La règle de typage d'une expression abs n, -n, lnot n, float_of_int n, char_of_int n, ou string_of_int n distingue deux cas possibles :

• ou bien le type de n est int alors l'expression est de type (respectivement) int, int, int, float, char, string ;
• ou bien l'expression est mal typée.

La règle de typage d'une expression a + b, a - b, a * b, a mod b, a land b, a lor b, a lsl b, a lsr b, distingue deux cas possibles :

• ou bien le type de a est int et le type de b est int alors l'expression est de type int ;
• ou bien l'expression est mal typée.

La règle de typage d'une expression a = b, a <> b, a < b et a <= b, a >= b, ou a > b distingue deux cas possibles :

• ou bien a et b ont un même type E alors l'expression est de type bool ;
• ou bien l'expression est mal typée.

La règle de typage d'une expression min a b ou max a b distingue deux cas possibles :

• ou bien a et b ont un même type E alors l'expression est de type E ;
• ou bien l'expression est mal typée.

La règle de typage d'une expression a && b, a || b ou a or b distingue deux cas possibles :

• ou bien le type de a est bool et le type de b est bool alors l'expression est de type bool ;
• ou bien l'expression est mal typée.

La règle de typage d'une expression sqrt x, sin x, cos x, tan x, log x, exp x, asin x, acos x ou atan x distingue deux cas possibles :

• ou bien le type de x est float alors l'expression est de type float ;
• ou bien l'expression est mal typée.

En OCaml les notions d'expression et de valeur ont un sens assez large puisqu'elles englobent aussi les fonctions qui sont des valeurs à part entière.
Une fonction d'une seule variable se déclare à l'aide du mot-clé fun et d'une flèche, par exemple la fonction de n qui renvoie n + 1 se déclare comme ceci :

# fun n -> n + 1;;
- : int -> int = <fun>

L'interpréteur a bien évalué cette expression comme une valeur et lui a attribué le type int → int, c'est-à-dire une fonction d'un entier qui renvoie un entier.
Cette attribution de type se fait grâce au soutien des règles de typage, au niveau le plus élevé, celui de la fonction, le système de typage a réuni suffisamment d'informations de typage pour en déduire le type complet d'une fonction.
La flèche est un constructeur infixe pour les types fonctionnels, elle prend à gauche le type d'un argument et à droite le type d'une application à un argument. Un type fonctionnel est le correspondant OCaml d'une signature dans d'autres langages. Dans ces autres langages, une signature n'est pas un type parce que les fonctions ne sont pas des valeurs à part entière.

L'application de fonction est une opération tellement élémentaire qu'en OCaml on l'écrit par simple juxtaposition, par exemple le successeur de l'entier 2 est l'entier 3 :

# (fun n -> n + 1) 2;;
- : int = 3

Une fonction à plusieurs arguments se construit en imbriquant plusieurs fonctions à un seul argument, par exemple cette fonction réalise l'addition de deux entiers a et b :

fun a -> (fun b -> a + b);;

Son type est int → (int → int), car la flèche est associative à droite, si on lui passe en entier comme argument alors le résultat est de type int → int. Comme la flèche est associative à droite et que l'application de fonction est associative à gauche, pour additionner 1 et 2 on pourra écrire :

(fun a -> fun b -> a + b) 1 2;;

La valeur 1 est alors associée à la variable a puis la valeur 2 est associée à la variable b dans l'expression 1 + b ce qui donne 1 + 2 = 3.
On peut écrire en plus condensé :

(fun a b -> a + b) 1 2;;

Cette abréviation n'altère en rien le mécanisme d'évaluation qui reste exactement le même, en particulier, comme le suggérait le type int → (int → int), on peut construire une fonction d'incrémentation en appliquant 1 à cette fonction :

(fun a b -> a + b) 1;;

Règle de typage (construction d'une fonction)
La règle de typage d'une expression fun v → expr distingue trois cas possibles :

• ou bien toutes les occurrences de v dans expr ont un même type T alors l'expression est de type T → E où E est le type de expr ;
• ou bien il n'y a aucune occurrence de v dans expr alors l'expression est de type 'a → E où E est le type de expr, ce cas ne nous intéresse pas pour l'instant, nous définirons le type 'a au moment opportun ;
• ou bien l'expression est mal typée.

Règle de typage (application d'une fonction)
La règle de typage d'une application f x distingue deux cas possibles :

• ou bien l'expression f est du type X → Y et l'expression x est du type X alors l'application f x est de type Y ;
• ou bien l'application f x est mal typée.

Les déclarations se font avec le mot-clé let qui associe une valeur à une variable, la constante pi pourra être définie ainsi :

let pi = 3.1415926535898;;

L'addition entière pourra être définie ainsi :

let add = fun a b -> a + b;;

Attention: les variables ainsi définies sont liées, elles ne sont pas modifiables, leur valeur est fixée, elles ne peuvent pas en changer en utilisant une assignation.

Les mots-clés if ... then ... else ... permettent un choix parmi deux expressions possibles selon la valeur d'une condition :

let abs = fun z -> if z >= 0 then z else -z;;
let minimum = fun a b -> if a < b then a else b;;
let maximum = fun a b -> if a > b then a else b;;

Le if ... then ... else ... n'est pas une instruction, mais une expression qui peut prendre deux valeurs possibles.

Règle de typage (expression conditionnelle)
La règle de typage d'une expression if cond then expr1 else expr2 distingue deux cas possibles :

• ou bien le type de cond est bool et les expressions expr1 et expr2 ont un même type E alors l'expression est de type E ;
• ou bien l'expression est mal typée.

Le mot-clé rec permet la récursion c'est-à-dire l'utilisation d'une variable pendant sa définition avec let :

let rec factorial =
  fun n -> if n=0 then 1 else n * factorial (n - 1);;

let rec power =
  fun x n -> if n=0 then 1. else x *. power x (n-1);;

let rec binomial =
  fun n p -> if (p=0) or (p=n) then 1 else binomial (n-1) p + binomial (n-1) (p-1);; 

let rec fibonacci =
  fun n -> if n < 2 then 1 else fibonacci (n - 1) + fibonacci (n - 2);;

Remarque : pour donner une idée intuitive de cette dernière fonction fibonacci disons que si une grenouille pouvait sauter au maximum deux marches d'escalier alors fibonacci n serait le nombre de façons différentes pour cette grenouille de monter n marches à l'aide d'une combinaison de sauts d'une ou deux marches.

Les déclarations suivantes sont, par abus de langage, appelées déclarations de fonctions :

let rec factorial n = if n=0 then 1 else n * factorial (n - 1);;

let rec power x n = if n=0 then 1. else x *. power x (n-1);;

let rec binomial n p = if (p=0) or (p=n)  then 1 else binomial (n-1) p + binomial (n-1) (p-1);; 

let rec fibonacci n = if n < 2 then 1 else fibonacci (n - 1) + fibonacci (n - 2);;

Leur sémantique est exactement la même que leurs précédentes versions respectives. factorial, power, binomial et fibonacci restent des variables liées à des valeurs fonctionnelles.

Il existe une façon alternative de définir des fonctions récursives: au lieu d'effectuer le calcul au plus tard on l'effectue au plus tôt, pour cela on rajoute un paramètre dit accumulateur qui enregistre le résultat partiel du calcul en cours :

let rec factorial acc n =
  if n=0 then acc else factorial (acc*n) (n-1);;

L'expression factorial 1 correspond alors à la fonction factorielle recherchée.

Remarque : on a bien renversé le sens du calcul, cette version itérative calcule n×(n-1)×(n-2)×…×2 alors que la version sans accumulation calculait 2×…×(n-2)×(n-1)×n, bien sûr cela n'a pas d'intérêt ici, car la multiplication est commutative, mais cet effet peut se révéler très utile lors d'applications plus concrètes comme nous aurons l'occasion d'en donner des exemples.

Nombre de fonctions récursives (mais pas toutes) peuvent être réécrites à l'aide d'un ou plusieurs accumulateurs :

let rec power acc x n =
  if n=0 then acc else power (acc *. x) x (n-1);;

L'expression power 1.0 correspond à la fonction puissance ordinaire.

Pour la fonction fibonacci on aura besoin de deux accumulateurs :

let rec fibonacci acc0 acc1 n =
  if n < 2 then acc1 else fibonacci acc1 (acc0 + acc1) (n - 1);;

L'expression fibonacci 1 1 correspond à la fonction fibonacci ordinaire.

Cette définition de fibonacci est beaucoup plus efficace que la version purement récursive. Pour faire une comparaison imaginons qu'avec la version à accumulateurs la grenouille se contente de monter n marches, alors avec la version récursive la grenouille expérimenterait toutes les façons possibles de monter ces mêmes n marches.

Dans toutes ces implémentations avec accumulateurs la branche then renvoie le résultat final tandis que la branche else n'est qu'une réapplication de la fonction avec de nouveaux arguments. Comme nous le verrons plus loin, cette propriété dite de récursion terminale a aussi son importance dans les performances des calculs intensifs.

Avouons-le, les versions à accumulateur(s) sont moins confortables à l'usage, à cause de leur(s) paramètre(s) supplémentaire(s). Il serait plus commode de camoufler les paramètres-accumulateurs pour n'utiliser que les paramètres significatifs. Pour ce faire nous allons utiliser les mots-clés let v = expr1 in expr2. Cette construction autorise une définition locale, elle agit comme un let ordinaire sauf que la variable v n'est définie que dans expr2 où elle vaudra expr1. La variable v n'est pas définie dans le reste du programme. La construction let rec v = expr1 in expr2 autorise la récursion sur une définition locale de la variable v, c'est-à-dire que v pourra être présente dans expr1.

Nous avons besoin d'un let pour créer le raccourci ainsi que d'un let rec qui définira la fonction récursive locale à accumulateur :

let factorial n =
  let rec loop acc n =
    if n=0 then acc else loop (acc*n) (n-1)
  in loop 1 n;;

let power x n =
  let rec loop acc n =
    if n=0 then acc else loop (acc *. x) (n-1)
  in loop 1. n;;

let fibonacci n =
  let rec loop acc0 acc1 n =
    if n < 2 then acc1 else loop acc1 (acc0 + acc1) (n - 1)
  in loop 1 1 n;;

Il existe une autre raison, plus profonde que celle de la commodité, pour laquelle un changement dans l'expression d'une fonction ne doit pas modifier la façon d'appliquer cette fonction. Cette raison tient à l'approche de componentisation systématique sur laquelle nous nous sommes engagés dès notre présentation de la notion de complexité dans les programmes. Les fonctions sont un de nos meilleurs atouts, si nous voulons préserver leur composabilité il nous faut préserver leur type, car il est le connecteur qui permet de les emboîter les unes avec les autres.

Règle de typage (déclaration locale)
La règle de typage d'une expression let v = expr1 in expr2 distingue trois cas possibles :

• ou bien toutes les occurrences de v dans expr2 ont le même type que expr1 alors l'expression est de type E où E est le type de expr2 ;
• ou bien il n'y a aucune occurrence de v dans expr2 alors l'expression est de type E où E est le type de expr2 ;
• ou bien l'expression est mal typée.

Parfois le domaine de définition d'une fonction est strictement inclus dans son type, on utilisera alors le mot-clé assert pour garantir qu'une fonction n'est toujours appliquée que sur son domaine de définition :

let factorial n =
  assert(n >= 0);
  let rec loop acc n =
    if n=0 then acc else loop (acc*n) (n-1)
  in loop 1 n;;

let power x n =
  assert(n >= 0);
  let rec loop acc n =
    if n=0 then acc else loop (acc *. x) (n-1)
  in loop 1. n;;

let fibonacci n =
  assert(n >= 0);
  let rec loop acc0 acc1 n =
    if n < 2 then acc1 else loop acc1 (acc0 + acc1) (n - 1)
  in loop 1 1 n;;

let rec binomial n p =
  assert(0 <= p && p <= n);
  if (p=0) or (p=n)  then 1 else binomial (n-1) p + binomial (n-1) (p-1);;

Lorsqu'une fonction sera appliquée hors de son domaine de définition OCaml terminera l'évaluation par une erreur Assert_failure telle que celle-ci :

# factorial (-1);;
Exception: Assert_failure ("", 5, 1).

Une assertion ne fait que rendre explicite une indication d'usage que vous auriez autrement mis en commentaire. Expliciter ce qui autrefois était implicite c'est un thème récurrent du principe quality first.

Le respect du principe quality first prescrit d'écrire systématiquement les assertions nécessaires, avant même d'écrire le corps de la fonction. Vous vous remercierez de l'avoir fait pendant le débogage. Anticiper les phases suivantes du développement c'est un autre thème récurrent du principe quality first. N'effacez jamais une assertion, au pire mettez-la en commentaire.

Les assertions font également partie de notre panoplie d'outils pour préserver la composabilité, elles doivent être considérées comme des types, la contrainte qu'elles ajoutent a du sens, elle capture une restriction de domaine que notre système de type n'est pas assez expressif pour imposer à la compilation.

Règle de typage (assertion)
La règle de typage d'une expression assert (cond) distingue deux cas possibles :

• ou bien le type de cond est bool alors l'expression est de type unit (nous reparlerons de ce type unit au moment opportun) ;
• ou bien l'expression est mal typée.

Un type énuméré est un ensemble fini qui correspond au domaine de définition d'une fonction. De cette façon on n'aura pas à ajouter d'assertion, car le type de la fonction correspondra à son domaine de définition.

type day =
  | Monday
  | Tuesday
  | Wednesday
  | Thursday
  | Friday
  | Saturday
  | Sunday
  ;;

Chaque jour ainsi énuméré devient un constructeur pour le type day.

Remarque : le nom de chacun des membres (on dit variants) d'un type énuméré doit commencer par une majuscule, c'est une obligation, au contraire les autres identificateurs habituels (les types, fonctions, variables et étiquettes) doivent toujours commencer par une lettre minuscule.

Règle de typage (constructeur)
La règle de typage d'une expression Constructeur ne contient qu'un seul cas possible :

• le type d'un Constructeur est le type dans lequel il a été énuméré.

Le filtrage (pattern matching) permet une analyse de cas en distinguant chacun des motifs (patterns) possibles. Une variable dans un motif prend la valeur à laquelle elle est associée dans ce motif. Les motifs sont ordonnés, ils sont confrontés tour à tour à la valeur filtrée, le premier motif filtrant cette valeur sélectionne la valeur renvoyée par l'expression filtrante. Les variables dans les motifs filtrent toutes les valeurs.

let rec fibonacci n =
  assert(n >= 0);
  match n with
  | 0 -> 1
  | 1 -> 1
  | m -> fibonacci(m-1) + fibonacci(m-2) ;;

La sémantique de l'expression filtrante match dans cette fonction est la suivante :

• si n = 0 alors l'expression vaut 1 ;
• si n = 1 alors l'expression vaut 1 ;
• sinon l'expression vaut let m = n in fibonacci(m-1) + fibonacci(m-2).

Comme les motifs sont ordonnés, un motif plus général pourra cacher un motif plus spécifique, dans ce cas OCaml délivrera un avertissement à prendre au sérieux comme dans l'exemple suivant où les motifs ont été clairement mal ordonnés :

# let rec factorial n =
    match n with
    | m -> m * factorial (m - 1)
    | 0 -> 1;;
Characters 80-81:
Warning U: this match case is unused.
    | 0 -> 1;;
      ^
val factorial : int -> int = <fun>

De même qu'il existe des fonctions anonymes (introduites par le mot-clé fun) il existe également des variables anonymes.
La variable anonyme est notée "_", la fonction fibonacci peut donc être réécrite :

let rec fibonacci n =
  assert(n >= 0);
  match n with
  | 0 -> 1
  | 1 -> 1
  | _ -> fibonacci(n-1) + fibonacci(n-2) ;;

Le filtrage multiple, c'est-à-dire sur plusieurs valeurs, est possible à l'aide de la virgule :

let rec binomial n p =
  assert(0 <= p && p <= n);
  match n,p with 
  | _,0 -> 1
  | _,_ -> if p = n then 1
           else binomial (n-1) p + binomial (n-1) (p-1) ;;

Les schémas autorisés dans un motif sont :

• une nouvelle variable ;
• un constructeur ;
• une constante immédiate ;
• une nouvelle variable anonyme.

Les expressions et les applications de fonction ne sont pas autorisées dans les motifs, car un motif n'est pas une valeur, mais un schéma de valeurs.
OCaml vérifie l'exhaustivité du filtrage, si un cas n'est pas filtré, un message d'alerte vous invite à intégrer ce cas ou à reconsidérer votre fonction :

# let string_of_day d =
    match d with
    | 1 -> "Monday"
    | 2 -> "Tuesday"
    | 3 -> "Wednesday"
    | 4 -> "Thursday"
    | 5 -> "Friday"
    | 6 -> "Saturday"
    | 7 -> "Sunday";;
Characters 23-97:
Warning: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
0

Vous devez prendre cet avertissement au sérieux, dans le cas ci-dessus le filtrage a peu de sens, car il y a une infinité d'entiers pour seulement 7 jours de la semaine. L'avertissement concernant la fonction string_of_day est le symptôme d'une erreur sur le domaine de définition, dans notre cas un type énuméré ferait davantage l'affaire :

let string_of_day d =
  match d with
  | Monday    -> "Monday"
  | Tuesday   -> "Tuesday"
  | Wednesday -> "Wednesday"
  | Thursday  -> "Thursday"
  | Friday    -> "Friday"
  | Saturday  -> "Saturday"
  | Sunday    -> "Sunday";;

let tomorrow d =
  match d with
  | Monday    -> Tuesday
  | Tuesday   -> Wednesday
  | Wednesday -> Thursday
  | Thursday  -> Friday
  | Friday    -> Saturday
  | Saturday  -> Sunday
  | Sunday    -> Monday;;

Remarque : OCaml rejette la définition multiple d'une même variable dans un même motif.

# let equal a b =
    match a,b with
    | x,x -> true
    | _,_ -> false;;
Characters 43-44:
      | x,x -> true
          ^
This variable is bound several times in this matching

Ici, ce qui semble une contrainte d'égalité est en fait une tentative de définir la même variable avec deux valeurs différentes.

Règle de typage (filtrage)
La règle de typage d'une expression match expr with pat1 → expr1 | ... | patn → exprn comportant n clauses distingue deux cas possibles :

• ou bien l'expression expr et les motifs pat1 à patn ont un même type T et les expressions expr1 à exprn ont un même type E alors l'expression est de type E ;
• ou bien l'expression est mal typée.

La liste chaînée est le type conteneur-extensible le plus simple, tellement simple qu'en OCaml ce type est prédéfini.
Il existe deux façons distinctes d'exprimer une liste chaînée :

• ou bien par énumération, en encadrant les éléments par des crochets, séparés par des points-virgules

# [2;3;4];;
- : int list = [2; 3; 4]

• ou bien par construction à l'aide du constructeur infixe ::

# 2::3::4::[];;
- : int list = [2; 3; 4]

Dans le cas du constructeur :: l'argument à gauche est appelé la tête (head) et celui à droite la queue (tail) de la liste.

Les fonctions qui manipulent des listes utilisent abondamment le filtrage :

• une liste énumérée pour le (ou les) cas de base ;
• une liste construite pour les cas composites.

Par exemple, la fonction sum_list renvoie la somme des entiers d'une liste, la somme des éléments d'une liste vide étant nulle, et la somme des éléments d'une liste non vide étant égale à sa tête n plus la somme des éléments de sa queue t :

let rec sum_list l =
  match l with
  | []   -> 0
  | n::t -> n + sum_list t;;

Il s'agit là d'un raisonnement par cas qui sera souvent utilisé sur les listes :

• ou bien on est dans le cas trivial de la liste vide ;
• ou bien on déconstruit la liste et on applique le traitement adéquat sur sa tête et sa queue, souvent on aura une récursion sur la queue.

Plus rarement il faudra traiter le cas de la liste à un seul élément ou alors il faudra considérer les deux premiers éléments en tête de la liste. Nous aurons bien assez tôt l'occasion de voir maints exemples de fonctions sur les listes.

Règle de typage (liste)
La règle de typage d'une expression a::l ne contient qu'un seul cas possible :

• le type de l'expression a est T ;
• le type de l'expression l est T list ;
• le type de l'expression a::l est T list.

On se propose de donner deux exemples plus avancés avec les listes.
En premier on déterminera toutes les vues sur un tétromino.
En second on donnera la liste des coordonnées des sommets du cube unité en dimensions quelconques.

Un polyomino est une congruence orthogonale de n carrés. Le jeu Tetris tire son nom du fait qu'il se joue avec les congruences orthogonales de quatre carrés, ce sont les cinq tétrominos surnommées I.L.O.S.T. :

On représentera un polyomino par une edge list, une liste des arêtes (edge) orientées dans le sens des aiguilles d'une montre où le type edge est défini par :

type edge =
  | Up
  | Down
  | Left
  | Right
  ;;

Voici les cinq tétrominos I.L.O.S.T. :

let tetro_I = [Up;Up;Up;Up;Right;Down;Down;Down;Down;Left];;
let tetro_L = [Up;Up;Up;Right;Down;Down;Right;Down;Left;Left];;
let tetro_O = [Up;Up;Right;Right;Down;Down;Left;Left];;
let tetro_S = [Up;Right;Up;Right;Right;Down;Left;Down;Left;Left];;
let tetro_T = [Up;Left;Up;Right;Right;Right;Down;Left;Down;Left];;

On voudra pouvoir les tourner (d'un quart de tour dans le sens horaire) :

let rec rotate p =
  match p with
  | [] -> []
  | Up::t    -> Right::rotate t 
  | Down::t  -> Left::rotate t
  | Left::t  -> Up::rotate t
  | Right::t -> Down::rotate t
  ;;

On voudra également pouvoir les miroiter (échange gauche-droite) :

let mirror p =
  let rec loop l a =
    match l with
    | [] -> a
    | Up::t    -> loop t (Down::a) 
    | Down::t  -> loop t (Up::a)
    | Left::t  -> loop t (Left::a)
    | Right::t -> loop t (Right::a)
  in loop p [];;

Remarque : pour pouvoir retourner la liste, on a utilisé une fonction avec un accumulateur.

Nous allons maintenant représenter le vecteur unité par la liste [[0];[1]] :

# [[0];[1]];;
- : int list list = [[0]; [1]]

Et le carré unité par la liste [[0;0]; [0;1]; [1;0]; [1;1]]. Pour généraliser en dimension n on s'aidera de la fonction mult_unit qui multiplie un cube c par l'intervalle unité lui ajoutant ainsi une dimension. Il suffit alors d'utiliser cette multiplication pour calculer la puissance nième de l'intervalle unité, c'est ce que fait la fonction power_cube :

let rec power_cube n =
  assert(n >= 1);
  let rec mult_unit c =
    match c with
    | []   -> []
    | h::t -> (0::h)::(1::h)::mult_unit t 
  in
    if n=1 then [[0];[1]]
    else mult_unit (power_cube (n-1));;

Nous avons déjà vu qu'une fonction n'a qu'un seul paramètre (sur son domaine) et ne renvoie qu'un résultat (sur son codomaine).

Une conséquence logique c'est qu'une fonction n'a que deux schémas de type possibles :

• ou bien le codomaine est identique au domaine, alors le type de la fonction est de la forme α → α ;
• ou bien le codomaine est différent du domaine, alors le type de la fonction est de la forme α → β.

Ou encore, dit autrement, l'opérateur infixe → est le constructeur du type fonctionnel α → β.

En OCaml les schémas de type α et β sont notés respectivement 'a et 'b :

# let f x = x in f;;
- : 'a -> 'a = <fun>

# let rec f x = f x in f;;
- : 'a -> 'b = <fun>

Un type paramétré par un schéma de type est dit polymorphe.
Un tel type n'est pas une curiosité, nous en avons déjà rencontré un :

# [];;
- : 'a list = []

Le type list est un type paramétré, une liste est homogène, tous ses éléments sont forcément du même type 'a. Ce paramètre de type 'a peut être fixé librement d'où le nom de polymorphisme paramétrique donné à cette capacité.
Ce polymorphisme paramétrique s'applique aussi bien aux types qu'aux fonctions :

• un type polymorphe permet de séparer le type conteneur du type contenu ;
• une fonction polymorphe permet de séparer le type de la fonction du type de ses paramètres.

Les deux vont de pair, la définition d'un type polymorphe s'accompagnant des fonctions polymorphes qui agissent sur lui.
Par exemple des fonctions sur une liste qui ne présagent pas du contenu de cette liste si bien qu'elles sont utiles sur tous les types de liste possibles.
C'est en premier lieu le cas du constructeur de liste, qui n'est pas une fonction puisqu'on ne peut pas l'appliquer, mais dont on va faire apparaître le type de la façon suivante :

# fun h t -> h::t;;
- : 'a -> 'a list -> 'a list = <fun>

La distinction entre fonctions et constructeurs se justifie par le filtrage, une fonction est faite pour être appliquée, un constructeur est fait pour être instancié et filtré.

L'opérateur infixe @ de concaténation de liste est également polymorphe :

# (@);;
- : 'a list -> 'a list -> 'a list = <fun>

Il est temps maintenant de profiter de la pleine fonctionnalité. Nous allons encore écrire des fonctions jouets, mais dorénavant elles seront plus amusantes que jamais. Alors, écrivons sept fonctions polymorphes sur les listes.

La première s'appelle filter, elle est du type :

('a -> bool) -> 'a list -> 'a list

Son 1er paramètre est donc un prédicat (une fonction qui teste un élément), son 2d paramètre est une liste et la fonction renvoie également une liste. Et le type nous dit encore plus que ceci. En effet regardons les paramètres de type, ils nous disent que le prédicat peut tester tous les éléments de la liste donnée en paramètre et que si on appliquait un prédicat à filter, c'est-à-dire si on ne lui fournissait que le premier de ses deux arguments (on appelle ceci une application partielle), alors filter serait un endomorphisme (une fonction de type α → α), elle aurait donc le même type que la fonction identité.

À partir de là, sur la seule foi de son type, il est possible d'imaginer ce que fait la fonction filter: elle renvoie la liste donnée en paramètre à laquelle ont été ôtés tous les éléments qui ne satisfont pas le prédicat ('a -> bool). Nous allons maintenant l'implémenter, voilà comment nous procédons, en raisonnant par cas :

• ou bien la liste est vide alors, la liste filtrée est vide ;
• ou bien la liste a une tête et une queue alors on filtre la queue et on lui ajoute la tête (si elle satisfait le prédicat) ou pas (si elle ne satisfait pas le prédicat).

Ce qui nous donne :

let rec filter p l =
  match l with
  | [] -> []
  | h::t -> if p h then h::filter p t
            else filter p t;;

Passons à notre deuxième fonction polymorphe, elle s'appelle exists et elle est du type :

('a -> bool) -> 'a list -> bool

Raisonnons sur son type, c'est encore une fonction qui attend un prédicat et une liste, encore une fois le prédicat teste les éléments de cette liste (puisque lui et la liste ont le même paramètre de type 'a), mais cette fois-ci la fonction exists est elle-même un prédicat (sur la liste donnée en argument), car si on lui applique un prédicat (par application partielle) alors son type devient α → bool. La fonction exists fait l'union logique de l'application du prédicat sur tous les éléments de la liste. Avec ce type elle pourrait faire la conjonction au lieu de l'union (c'est d'ailleurs le rôle de la fonction for_all que nous verrons plus tard). Le type d'une fonction ne la caractérise donc pas totalement, mais il en dit déjà assez long et il serait désavantageux d'ignorer cette information.

Raisonnons par cas :

• ou bien la liste est vide, elle ne contient alors aucun élément qui puisse satisfaire le prédicat, nous renvoyons false ;
• ou bien la liste a une tête et une queue alors nous renvoyons la conjonction logique du prédicat sur la tête et de la récursion sur la queue.

Ce qui nous donne :

let rec exists p l =
  match l with
  | [] -> false
  | h::t -> p h or exists p t;;

Passons à notre troisième fonction polymorphe, elle s'appelle mapi et elle est du type :

(int -> 'a -> 'b) -> int -> 'a list -> 'b list

Imaginons que les int soient absents de ce type alors le type serait celui-ci :

('a -> 'b) -> 'a list -> 'b list

Et c'est tout de suite plus clair : nous comprenons que la fonction mapi applique la fonction ('a → 'b) sur tous les éléments de la liste ('a list) et renvoie une liste ('b list). Alors que viennent faire les int ? C'est simple, il s'agit d'un argument supplémentaire qui croit avec la position de l'élément 'a dans la liste ('a list).

Raisonnons à nouveau par cas :

• ou bien la liste est vide alors la fonction f ne s'applique jamais et la liste renvoyée est vide ;
• ou bien la liste a une tête et une queue alors nous appliquons (f n h) et nous ajoutons le résultat à la transformation de la queue.

Ce qui nous donne :

let rec mapi f n l =
  match l with
  | [] -> []
  | h::t -> f n h::mapi f (n+1) t;;

Notre quatrième fonction polymorphe utilisera notre fonction exists, elle s'appelle exists_commutative et elle est du type :

('a -> 'a -> bool) -> 'a list -> bool

Ce type ressemble beaucoup à celui de exists sauf que cette fois-ci le prédicat teste deux éléments de la liste donnée en paramètre. Cette fonction nous dira donc s'il existe deux éléments dans la liste qui vérifient le prédicat donné en paramètre.

Raisonnons par cas :

• ou bien la liste est vide alors elle ne contient pas deux éléments, nous renvoyons false ;
• ou bien la liste a une tête et une queue alors, nous renvoyons la conjonction logique du prédicat (duquel on a fixé le premier argument avec la tête) appliqué à toute la queue et de la récursion sur la queue.

let rec exists_commutative p l =
  match l with
  | []   -> false
  | h::t -> (exists (p h) t) or exists_commutative p t;;

Notez que le prédicat doit être commutatif, car pour chaque couple d'éléments il n'est appliqué qu'une seule fois, si le prédicat était non commutatif il faudrait également l'appliquer en échangeant l'ordre des deux éléments.

Notre cinquième fonction polymorphe est la fonction flatten qui renvoie la concaténation de plusieurs listes :

let rec flatten l =
  match l with
  | [] -> []
  | h::t -> h @ flatten t;;

Notre sixième fonction polymorphe est distribute qui utilise mapi pour renvoyer la liste des listes l dans lesquelles on a inséré l'élément a à toutes les positions possibles :

let rec distribute a l =
  match l with
  | []   -> [[a]]
  | h::t -> (a::l) :: (mapi (fun _ x -> h::x) 0 (distribute a t));;

Enfin notre septième et dernière fonction est permute qui utilise flatten, mapi et distribute pour renvoyer la liste de toutes les permutations d'une liste :

let rec permute l =
  match l with
  | []   -> [[]]
  | h::t -> flatten (mapi (fun _ -> distribute h) 0 (permute t));;

Remarque :

Les opérations sur les listes sont toujours non destructives, la structure des listes passées en arguments est toujours préservée, les listes retournées en résultat sont fraîchement allouées dans le tas (la mémoire globale) par le constructeur (::), on dit que la liste est une structure de données immutable. D'une façon générale, la programmation fonctionnelle privilégie plutôt les données immutables alors que la programmation impérative privilégie plutôt les données mutables. Les données immutables bénéficient de la propriété dite de substituabilité qui facilite un raisonnement équationnel assez similaire à celui utilisé en mathématiques. Cette facilité de raisonner sur le texte du programme et non sur son exécution améliore grandement la lisibilité du code. De plus la rigueur du raisonnement par récurrence fait que le texte du programme se rapproche naturellement du raisonnement qui établit la preuve de sa correction.

Remarques :

• toute fonction de type 'a → 'a est isomorphe à la fonction identité ;
• toute fonction de type 'a → 'b → 'a est un opérateur associatif à gauche ;
• toute fonction de type 'a → 'b → 'b est un opérateur associatif à droite.

Règle de typage (liaison d'une variable de type)
Cette règle explicite l'instanciation d'un type polymorphe par un autre type monomorphe ou polymorphe :

• la variable 'a peut être liée à n'importe quel type T ne contenant pas d'occurrence libre de la variable 'a ;
• la variable 'a peut être liée à deux types T1 et T2 si et seulement si le type T1 est identique au type T2.

Les couples (pairs) correspondent à un produit cartésien de valeurs, ils combinent deux valeurs de types quelconques sous la forme d'une seule paire. Les deux éléments d'un couple sont séparés par une virgule. Les couples sont utilisés notamment :

• comme des containers ;
• pour retourner deux valeurs ;
• pour le filtrage multiple (nous avons déjà parlé du filtrage sur plusieurs valeurs).

La virgule est un constructeur, mais nous allons exposer son type comme nous l'avons fait pour le constructeur de listes :

# fun a b -> (a,b);;
- : 'a -> 'b -> 'a * 'b = <fun>

Deux remarques :

• le résultat contient deux paramètres de type 'a et 'b, un couple peut donc être hétérogène ;
• les parenthèses ne sont pas indispensables, mais elles sont souvent utiles surtout si on ne connaît pas bien la priorité des opérateurs OCaml.

On retiendra que l'opérateur infixe * est le constructeur du type produit α * β .

Le let, le let rec et les déclarations de fonctions peuvent filtrer les couples.

En tant que conteneurs, les couples peuvent représenter les nombres complexes :

let add_z (a1,b1) (a2,b2) = (a1+.a2,b1+.b2);;
let mul_z (a1,b1) (a2,b2) = (a1*.a2-.b1*.b2,a1*.b2+.a2*.b1);;

Un couple peut également être utilisé pour retourner deux valeurs, c'est par exemple le cas de la fonction predefinie modf qui renvoie un couple de float :

# modf;;
- : float -> float * float = <fun>

Les deux composantes du couple renvoyé peuvent être récupérées par un let-filtrant, par exemple cette expression extrait la partie décimale de pi :

# let pi = 3.14159 in
  let (d,i) = modf pi in d;;
- : float = 0.14158999999999988

Parfois un couple cumule les deux utilités, une fonction renvoie deux valeurs, mais ces valeurs peuvent être interprétées comme une seule valeur composite, par exemple ces valeurs peuvent être les deux bornes d'un intervalle à une dimension.

Règle de typage (construction d'un couple)
La règle de typage d'une expression a,b ne contient qu'un seul cas possible :

• le type d'un couple a,b est A * B où A est le type de l'expression a et B est le type de l'expression b

Pour finir, tout ce qui a été dit sur les couples est généralisable aux triplets ainsi qu'aux n-uplets (tuples) quelconques.

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

Le problème des 8 reines est un problème classique, l'exercice consiste à générer toutes les façons de positionner 8 reines sur un échiquier sans qu'aucune ne puisse en prendre une autre. Nous allons résoudre ce problème plus facilement qu'il n'y paraît.

Supposons qu'une reine soit sur la case (xa,ya) et une autre sur la case (xb,yb), alors le prédicat check_queens nous dit si ces deux reines sont en position de prise :

let check_queens (xa,ya) (xb,yb) =
  (xa = xb) or (ya = yb) or
  (xa - xb) = (ya - yb)  or
  (ya - yb) = (xb - xa);;

Cela résout-il notre problème, apparemment non. Mais réfléchissez un instant aux fonctions polymorphes que nous venons de développer, elles ont le pouvoir d'étendre la sémantique d'une fonction aussi loin qu'il est nécessaire pour la résolution de notre problème.

En effet, considérez que :

• il n'y a forcément qu'une reine par colonne ;
• il n'y a forcément qu'une reine par ligne ;
• nous appelons reine n la reine placée sur la nième ligne, alors permute [1;2;3;4;5;6;7;8] place les reines 1 à 8 sur toutes les permutations de colonnes possibles ;
• nous pouvons alors utiliser mapi pour créer les couples de coordonnées (colonne,ligne) ;
• pour détecter une liste de reines qui ne serait pas une solution, nous pouvons appliquer le test exists_commutative check_queens car le prédicat check_queens est commutatif ;
• nous pouvons utiliser filter pour ne garder que les listes de reines qui sont des solutions du problème.

Ce qui nous donne :

let safe_boards queens =
  filter
    (fun l -> exists_commutative check_queens l = false) 
    (mapi
      (fun _ l -> mapi (fun a b -> a,b) 1 l)
      1
      (permute queens)
    );;

safe_boards [1;2;3;4;5;6;7;8];;

Et comme la permutation nous garantit que chaque reine est sur un couple (colonne,ligne) unique nous pouvons simplifier le prédicat check_queens comme ceci :

let check_queens (xa,ya) (xb,yb) =
  (xa - xb) = (ya - yb) or
  (ya - yb) = (xb - xa) ;;

Remarque : les opérateurs logiques or et && sont semi-stricts, si la valeur de leur premier argument suffit à établir le résultat alors ils n'évaluent pas leur second argument. De ce fait la fonction check_queens ci-dessus est aussi efficace que la fonction check_queens ci-dessous.

let check_queens (xa,ya) (xb,yb) =
  if (xa - xb) = (ya - yb) then true
  else (ya - yb) = (xb - xa) ;;

Encore un exemple, pour illustrer la récursion et la démarche diviser pour régner, et encore une fonction polymorphe sur les listes. Celle-ci trie une liste par ordre croissant. Elle tire son polymorphisme de celui de la fonction (>) :

# (>);;
- : 'a -> 'a -> bool = <fun>

En OCaml toutes les fonctions de comparaison sont des prédicats polymorphes, en effet, si 'a est int ou float alors la comparaison a son sens mathématique habituel, avec les types char et string les données sont comparées suivant l'ordre alphabétique, sinon les données sont comparées selon une méthode structurelle (voir la documentation en ligne du module Pervasives pour plus de détails).

Le tri-fusion polymorphe nécessite trois fonctions auxiliaires.
La fonction merge_list fusionne deux listes a et b déja triées et renvoie leur union, c'est-à-dire une liste triée qui contient à la fois les éléments de a et ceux de b :

let rec merge_list a b =
  match a,b with 
  | [],_ -> b
  | _,[] -> a
  | ha::ta,hb::tb ->
      if ha < hb then ha::(merge_list ta b)
      else hb::(merge_list a tb);;

Le premier élément d'une liste est l'élément de rang zéro.
La fonction odd_list renvoie la liste des éléments de rang impair de la liste l :

let rec odd_list l =
  match l with
  | []  -> []
  | [a] -> []
  | a::b::l -> b::odd_list l;;

La fonction even_list renvoie la liste des éléments de rang pair de la liste l :

let rec even_list l =
  match l with
  | []   -> []
  | a::l -> a::odd_list l;;

Enfin, la fonction merge_sort est la fonction du tri-fusion d'une liste l.
Elle procède en trois étapes :

• elle scinde la liste l en deux listes ;
• elle trie ces deux listes ;
• elle fusionne les deux listes triées en une seule.

Cette décomposition récursive du processus de tri s'arrête nécessairement puisque l'on sait trier une liste vide et une liste qui contient un seul élément. Sinon la liste contient au moins deux éléments et alors on applique le procédé décrit ci-dessus. Voici le code de cette fonction :

let rec merge_sort l =
  match l with
  | [] -> []
  | [a] -> [a]
  | _ ->
      let p = even_list l in
      let q = odd_list  l in
      merge_list (merge_sort p) (merge_sort q);;

Remarque : on aurait pu effectuer la scission d'une liste en une seule étape, à l'aide de couples, comme ceci

let rec split_list l =
  match l with
  | [] -> [],[]
  | [a] -> [a],[]
  | a::b::l -> let p,q = split_list l in (a::p,b::q);;

let rec merge_sort l =
  match l with
  | [] -> []
  | [a] -> [a]
  | _ ->
      let p,q = split_list l
      in merge_list (merge_sort p) (merge_sort q);;

Remarque : il existe également un prédicat compare a b, qui effectue une comparaison plus complète que (<), qui est lui aussi polymorphe, et qui renvoie un entier dont le signe dépend de a < b et a > b

# compare;;
- : 'a -> 'a -> int = <fun>

Ce prédicat pourrait être implémenté ainsi pour les entiers :

# let compare_int a b = a - b;;
val compare_int : int -> int -> int = <fun>

Bien sûr cette version est monomorphe, elle n'accepte que les entiers, mais elle donne une bonne idée du comportement du compare polymorphe.

Bien entendu OCaml permet de gérer les gros projets et les projets en équipe, pour cela il fournit un mécanisme de modularité qui offre un espace de nommage (et même beaucoup plus, mais cela n'est pas le sujet de ce paragraphe). Ce mécanisme de modularité est d'autant plus indispensable que certaines fonctions sont "trop" polymorphes. Par exemple la fonction compare (celle du module Pervasives) est définie d'une façon trop générique, pour des types composites elle ne renverra pas forcément le résultat escompté, il faudra alors définir une fonction compare plus spécialisée qui renvoie le résultat attendu pour ce nouveau type. Il devient alors logique, pour ne pas écraser le compare habituel, de réunir la définition du nouveau type composite et la définition de sa fonction compare dans un même module.

Le mot-clé module permet de limiter la portée du let. Ainsi, en introduisant un module List on pourra limiter la portée des fonctions filter, exists, flatten sur les listes, ceci permettrait par exemple de réutiliser ces noms dans un hypothétique module Tree. Choisir des noms identiques pour des fonctionnalités identiques est une bonne pratique qui participe à augmenter la lisibilité des programmes.

La bonne nouvelle c'est que ce module List existe déjà, c'est le fichier Objective Caml/libs/list.ml, et il contient les fonctions List.filter, List.exists, et List.flatten telles que nous les avons défines, avec des implémentations récursives terminales quand cela est possible. Pour une spécification plus complète du module List veuillez consulter sa documentation en ligne.

Parfois la récursion terminale n'est pas directement possible, c'est le cas de la fonction List.append qui est la version préfixe de l'opérateur de concaténation de listes (@) que nous avons déjà utilisé. Il est possible d'écrire une version récursive terminale de la concaténation, en ajoutant un accumulateur, mais comme nous l'avons vu ceci peut avoir pour effet de renvoyer un résultat qui est le miroir du résultat voulu, dans le cas de la concaténation de liste ceci nous donne la fonction List.rev_append :

# List.rev_append;;
- : 'a list -> 'a list -> 'a list = <fun>

Cette fonction a le même type que List.append, elle est récursive terminale et elle concatène bien ses deux arguments, mais son résultat est renversé, nous verrons néanmoins que cette fonction n'est pas inutile, car nous n'aurons pas forcément besoin de renverser son résultat à l'aide de List.rev.

Vous l'avez deviné, List.rev l est la fonction qui renverse la liste l, elle est récursive terminale :

let rev l = rev_append l [];;

Voilà bien un premier exemple qui montre que List.rev_append n'est pas l'aberration qu'on pourrait croire.

Le module List contient également les fonctions List.map, List.for_all et List.sort.

La fonction List.map ressemble à notre fonction mapi à la différence près que List.map ne tient pas compte de la position des éléments dans la liste :

# List.map;;
- : ('a -> 'b) -> 'a list -> 'b list = <fun>

La fonction List.map applique la fonction ('a → 'b) sur tous les éléments de la liste ('a list) et renvoie une liste ('b list).
Cette fonction n'est pas récursive terminale, sa version récursive terminale (mais renversée) est List.rev_map.

La fonction List.for_all ressemble fort à la fonction List.exists et d'ailleurs on pourrait l'implémenter ainsi :

let for_all p l = List.exists (fun x -> p x = false) l = false;;

Elle dit simplement si les éléments d'une liste l vérifient tous le prédicat p.

Enfin la fonction List.sort ressemble fort à notre fonction merge_sort à la différence qu'en plus elle attend pour premier argument une fonction similaire à compare et c'est cette fonction qui lui sert de critère pour le tri :

# List.sort;;
- : ('a -> 'a -> int) -> 'a list -> 'a list = <fun>

Il reste le cas de nos fonctions mapi, exists_commutative et permute, et comme elles ont déjà prouvé leur utilité nous les conserverons dans un nouveau module que l'on nommera ListXP :

module ListXP = struct
  let rec mapi f n l = ...
  let rec exists_commutative p l = ...
  let rec permute l = ...
end;;

La portée de leurs déclarations est alors délimitée par les mots-clés struct et end.
Nous en profitons pour améliorer leurs implémentations en fournissant une version récursive terminale rev_mapi et en utilisant les fonctions du module List :

module ListXP = struct

  let rec mapi f n l =
    match l with
    | []   -> []
    | h::t -> f n h::mapi f (n+1) t;;

  let rev_mapi f n l =
    let rec loop l n acc = 
      match l with
      | []   -> acc
      | h::t -> loop t (n+1) (f n h::acc)
    in loop l n [];;

  let rec exists_commutative p l =
    match l with
    | []   -> false
    | h::t -> (List.exists (p h) t) or exists_commutative p t;;

  let rec distribute a l =
    match l with
    | []   -> [[a]]
    | h::t -> (a::l) :: (List.map (fun x -> h::x) (distribute a t));;

  let rec permute l =
    match l with
    | []   -> [[]]
    | h::t -> List.flatten (List.map (distribute h) (permute t));;

end;;

Notons qu'un module est une expression et a donc un type (qu'on appelle aussi signature), voici la signature de notre module ListXP telle que l'interpréteur OCaml l'a inférée :

module ListXP :
  sig
    val mapi : (int -> 'a -> 'b) -> int -> 'a list -> 'b list
    val rev_mapi : (int -> 'a -> 'b) -> int -> 'a list -> 'b list
    val exists_commutative : ('a -> 'a -> bool) -> 'a list -> bool
    val distribute : 'a -> 'a list -> 'a list list
    val permute : 'a list -> 'a list list
  end

Remarque : le nom d'un module doit obligatoirement commencer par une majuscule.

Parfois une fonction ne peut pas renvoyer de résultat parce que ses arguments sont incompatibles avec le calcul à effectuer.
Il existe trois façons simples de régler ces cas, par ordre de préférence :

• la fonction assert, déjà vue ;
• la fonction invalid_arg appliquée à une chaîne de message d'erreur ;
• la fonction failwith appliquée à une chaîne de message d'erreur.

Voici un cas où l'on privilégiera la fonction assert parce qu'il n'y pas de filtrage :

# abs min_int;;
- : int = -1073741824
# let safe_abs n =
    assert(n > min_int);
    abs n;;
val safe_abs : int -> int = <fun>

Voici un cas où l'on privilégiera au contraire la fonction invalid_arg parce que le cas à éliminer est déjà pris en compte par un filtrage exhaustif :

# let maximum l =
    let rec loop a l =
      match l with
      | []   -> a
      | b::t -> if a > b then loop a t else loop b t
    in match l with
    | []   -> invalid_arg "maximum"
    | a::t -> loop a t;;
val maximum : 'a list -> 'a = <fun>

On réservera l'usage de la fonction failwith aux cas où les arguments sont bien dans le domaine de définition.

Remarque : les fonctions failwith et invalid_arg sont de type string → 'a, un type à l'évidence totalement dépourvu de sémantique, avec pour seul avantage qu'il trouve sa place n'importe où.
La bonne nouvelle c'est qu'un déclenchement d'erreur pourra se substituer à n'importe quelle expression.
La mauvaise nouvelle c'est que n'importe quelle expression suffisamment obscure pourra cacher un déclenchement d'erreur.

Les enregistrements (records) correspondent eux aussi à un produit cartésien de valeurs et ont la même utilité que les couples ou n-uplets. La principale différence c'est qu'avec un n-uplet un élément est identifié par sa position alors qu'avec un enregistrement un élément est identifié par son étiquette (label).

Une autre différence c'est le typage, OCaml doit pouvoir typer la totalité d'un couple alors que pour un enregistrement il lui suffit de typer chacune de ses composantes. Nous étudierons plus tard en quoi le typage limite parfois les couples et avantage les enregistrements.

Typiquement la déconstruction d'un couple se fait plutôt par filtrage alors que la déconstruction d'un enregistrement se fait plutôt par ses accesseurs. Le filtrage est plus naturel pour le calcul symbolique, les accesseurs sont plus naturels pour les calculs numériques.

En voici un exemple, nous déclarons d'abord les types vector et point, en trois dimensions :

type vector = {x: float; y: float; z: float};;
type point  = vector;;

Le type point n'est qu'un alias (un synonyme) pour le type vector, parce qu'un point peut être désigné par le vecteur qui le sépare de l'origine. Nous pouvons maintenant implémenter les opérations vectorielles classiques, l'addition, la soustraction, le produit scalaire et le carré scalaire :

let add a b =
  {x = a.x +. b.x; y = a.y +. b.y; z = a.z +. b.z;};;    

let sub a b =
  {x = a.x -. b.x; y = a.y -. b.y; z = a.z -. b.z;};;    

let scalar_dot a b =
  a.x *. b.x +.
  a.y *. b.y +.
  a.z *. b.z;;

let scalar_sqr v =
  v.x *. v.x +.
  v.y *. v.y +.
  v.z *. v.z;;

Nous ajoutons également un constructeur qui fabrique un vecteur à partir de deux points :

let make (a: point) (b: point) =
  {x = b.x -. a.x; y = b.y -. a.y; z = b.z -. a.z;};;

On remarquera la notation (expr: type) qui demande explicitement au compilateur d'essayer d'inférer le type mentionné. Ceci n'a rien à voir avec le transtypage dans les langages pourvus d'un typage moins fort que celui d'OCaml, si le compilateur ne parvient pas à inférer le type demandé alors une erreur de typage sera reportée. Ici on demande au compilateur d'inférer le type point plutôt que le type vector. Cette façon d'orienter le typage s'appelle une annotation de type.

Nous voilà prêts pour affronter la problématique de base du lancé de rayons. Un rayon est une demi-droite paramétrée s + tv , elle a pour source le point s et pour direction le vecteur v.
Une sphère a pour centre un point c et pour rayon un réel r. L'intersection d'un rayon avec une sphère est soit vide, soit un intervalle (t1,t2) de paramètres du rayon s + tv.

# let ray_sphere (s: point) v (c: point) r =
    (* Carré du rayon de la sphère: *)
    let r2 = r *. r   in
    (* Vecteur de la source au centre de la sphère: *)
    let sc = make s c in
    (* Carré de la distance de la source au centre de la sphère: *)
    let sc2 = scalar_sqr sc   in
    let v2  = scalar_sqr v    in
    let p   = scalar_dot sc v in
    let p2  = p *. p    in
    (* Carré de la distance du rayon au centre de la sphère: *)
    let d2 = sc2 -. p2 /. v2 in
    let delta = r2 -. d2 in
    if delta <= 0. then
      failwith "empty"
    else
      let sq = sqrt (delta /. v2) in
      let t1 = p /. v2 -. sq in
      let t2 = p /. v2 +. sq in
      if t2 < 0. then
        failwith "empty"
      else
        (max 0. t1, t2);;
val ray_sphere : point -> vector -> point -> float -> float * float = <fun>

Règle de typage (synonymie de type)
Cette règle précise le sens de la condition "même type" en présence d'aliasing de type :

• un type est le même type qu'un type qui est son alias.

Règle de typage (typage explicite)
La règle de typage d'une expression explicitement typée (expr: E) distingue deux cas possibles :

• ou bien le type de expr est le même type que E alors l'expression est de type E ;
• ou bien l'expression est mal typée.

Bien que les langages fonctionnels soient plus proches de la spécification que les langages impératifs ils n'en sont pas moins exempts des considérations de performances. Il y trois types de ressources à économiser :

• la pile est une ressource mémoire locale et limitée ;
• le tas désigne la mémoire globale ;
• les processeurs désignent les ressources d'exécution.

Du fait de leur système de typage bien plus avancé, les langages fonctionnels peuvent mieux capitaliser sur la modularité pour réutiliser les meilleurs algorithmes et les meilleures structures de données les plus adaptés aux spécificités du domaine. Du coup le programmeur fonctionnel est généralement moins sous pression quant aux gains de performances liés à l'économie des ressources d'exécution.

Il faudra tout de même prendre garde à partager les calculs autant que possible, par exemple

let square f x = f x *. f x;;

devra s'écrire :

let square f x = let y = f x in y *. y;;

Sinon le calcul, potentiellement long, de f x se fera deux fois au lieu d'une seule.

La contrepartie d'une meilleure maîtrise des ressources d'exécution c'est que le programmeur fonctionnel doit faire davantage attention à économiser les ressources mémoire, les langages fonctionnels sont des langages de haut niveau, ils ont une tendance naturelle à consommer plus de pile et de tas que les langages de bas niveau.

L'astuce principale pour économiser la pile consiste à privilégier la récursion terminale, par exemple si l'on veut concaténer deux listes et que seuls comptent les éléments (pas leur ordonnancement) alors on utilisera List.rev_append plutôt que List.append parce que List.rev_append est récursive terminale et pas List.append. Il en va de même pour List.rev_map comparée à List.map.

Dans d'autres cas, il faudra utiliser l'accumulation si cela est nécessaire, notamment si l'on envisage de traiter des chaînes de longueur potentiellement élevée. Souvent il sera plus aisé de faire l'implémentation en deux étapes, d'abord écrire une version récursive, la tester, puis ensuite écrire une nouvelle version avec accumulation.

Une astuce de nature similaire s'applique au tas, elle consiste à remplacer les listes normales par des listes paresseuses, ces listes sont détruites au fur et à mesure qu'elles sont construites de sorte que seule leur tête est présente dans le tas au lieu de toute leur longueur. Nous n'aborderons pas les listes paresseuses dans ce chapitre.

Une autre astuce appréciable pour économiser le tas consiste à éviter la duplication des listes et des couples quand elle n'est pas strictement indispensable.

Pour les listes cela peut se faire en cumulant deux fonctionnalités en une seule, par exemple si on effectue des grandes quantités de ce traitement :

List.rev_map f (List.filter p l);;

Alors on pourra avantageusement le remplacer par :

let rev_map_filter p f l =
  let rec loop l acc =
    match l with
    | [] -> acc
    | h::t ->
        if p h then loop t (f h::acc)
        else loop t acc
  in loop l [];;

Ce qui permet d'économiser la production de listes par filter qui seraient aussitôt consommées par rev_map.

Une situation similaire concerne les couples, dans les cas où soit on veut pouvoir à la fois les détruire et les conserver.
Supposons que nous voulions ordonner tous les couples d'une liste, que le second élément du couple soit toujours supérieur au premier, voici une façon de faire :

let ordered_pair (a,b) = if a < b then (a,b) else (b,a);;
let list_ordered_pairs l = List.map ordered_pair l;;

Le cas dérangeant c'est le cas a < b, car alors nous détruisons le couple pour en construire un autre en tous points identique, en conséquence le tas est davantage sollicité qu'il ne le devrait. Afin d'éviter ces cas il existe le mot-clé as qui permet d'apparier une variable (ici p) à la totalité d'un motif (ici a,b) :

let ordered_pair (a,b as p) = if a < b then p else (b,a);;

Avec cette version, seuls les "nouveaux" couples sont alloués, les anciens sont réutilisés.