Laurent Le Brun

Notes sur le typage

Certaines fonctions sont génériques (polymorphes) et peuvent avoir n'importe quel type en entrée. Par exemple, l'opérateur < et la fonction min prennent 2 arguments, de n'importe quel type. Ce « n'importe quel type » se note 'a, 'b, 'c (ou 'autrenom).

Observons quelques types :

[fsharp]
> (<);;
val it : ('a -> 'a -> bool) = <fun:it@6>

< prend deux arguments de type 'a. Ce type peut être n'importe quoi (un entier, une chaine de caractères, une liste, une fonction...) mais représente un unique type. Cela signifie que les deux arguments de l'opérateur < doivent avoir le même type.

[fsharp]
> min;;
val it : ('a -> 'a -> 'a) = <fun:it@7>

C'est le même principe pour min. Juste en regardant le type de la fonction, on sait ce qu'elle renverra : si on lui donne deux entiers ('a = int), alors elle renverra forcément un entier. Si on lui donne deux caractères elle renverra un caractère.

Le typage est quelque chose de très important, c'est un outil qui permet de vérifier la cohérence d'un programme (il y a des limitations, mais c'est très puissant). Dans bien des cas, on peut deviner en partie le comportement d'une fonction en lisant simplement son type. On peut également vérifier que le compilateur a compris ce qu'on a voulu faire (il suffit de comparer le type déduit avec le type que l'on attendait).

[fsharp]
> let fct x y = x, y;;
val fct : 'a -> 'b -> 'a * 'b

Cette fonction prend deux arguments, l'un de type 'a, l'autre de type b. Les deux arguments peuvent donc avoir un type différent (ils peuvent aussi avoir le même type). Le type de retour est 'a * 'b : c'est un tuple (un couple ici). Cette fonction permet donc de regrouper deux valeurs discinctes en une seule valeur (sans avoir à déclarer explicitement une nouvelle structure).

Fonctions d'ordre supérieur

On appelle fonction d'ordre supérieur toute fonction qui prend une autre fonction en argument. C'est quelque chose de très puissant qui peut grandement augmenter la généricité du code.

Supposons que l'on souhaite écrire une fonction de tri générique. On pourrait écrire une fonction pour l'ordre croissant et une autre pour l'ordre décroissant, mais c'est trop limité. On peut vouloir trier une liste d'entiers par valeur absolue croissante, ou bien trier une liste de couples selon le deuxième élément.

L'idée est donc d'avoir une fonction de tri qui prend en argument une liste et une fonction de comparaison.

Dans le module List, il existe une fonction de tri (sortWith). Voici son type :

[fsharp]
> List.sortWith;;
val it : (('a -> 'a -> int) -> 'a list -> 'a list) = <fun:clo@0>

Son premier argument est une fonction de comparaison. Cette fonction de comparaison prend deux arguments de même type 'a et renvoie un entier. Le deuxième argument est une liste dont les éléments ont tous le type 'a. Le type de retour est une liste, elle aussi paramétrée par 'a. Le typage est très précis, ce qui permet de détecter les erreurs dans le code dès la phase de compilation.

La fonction de comparaison doit renvoyer une valeur négative, nulle ou positive, selon que la première valeur est inférieure, égale ou supérieure à la deuxième valeur.

Par exemple, on peut comparer la valeur absolue de deux entiers :

[fsharp]
> let compare_int x y =
    if abs x < abs y then -1
    elif abs x = abs y then 0
    else 1;;

> List.sortWith compare_int [1; 4; -2; 7; 0; 4];;
val it : int list = [0; 1; -2; 4; 4; 7]

Puisque c'est un besoin très fréquent, la bibliothèque standard définit une fonction générique "compare" (pour un ordre croissant).

[fsharp]
> List.sortWith compare [1; 4; -2; 7; 0; 4];;
val it : int list = [-2; 0; 1; 4; 4; 7]

Pour faire un tri par valeur absolue, on aurait pu réutiliser cette fonction en utilisant une fonction anonyme (ce qui raccourcit le code) :

[fsharp]
> List.sortWith (fun x y -> compare (abs x) (abs y)) [1; 4; -2; 7; 0; 4];;
val it : int list = [0; 1; -2; 4; 4; 7]

> List.sortWith (fun x y -> - compare (abs x) (abs y)) [1; 4; -2; 7; 0; 4];;
val it : int list = [7; 4; 4; -2; 1; 0]

Pour déclarer une fonction d'ordre supérieur, il n'y a rien de spécial à faire. C'est le système d'inférence de type qui va se débrouiller. Par exemple, on écrit une fonction min, paramétrée par une fonction de comparaison :

[fsharp]
> let minWith cmp x y =
   if cmp x y <= 0 then x
   else y;;

val minWith : ('a -> 'a -> int) -> 'a -> 'a -> 'a

> minWith compare 3 5;;
val it : int = 3

Voici un exemple assez intéressant qui combine application partielle et fonctions d'ordre supérieur. On désire pouvoir paramétrer la fonction de comparaison.

[fsharp]
> let compareBy fct x y = compare (fct x) (fct y);;
val compareBy : ('a -> 'b) -> 'a -> 'a -> int

Notez bien le type : la fonction fct prend un argument quelconque et peut renvoyer le type qu'elle désire. Par exemple, avec abs (int -> int) :

[fsharp]
> List.sortWith (compareBy abs) [1; 4; -2; 7; 0; 4];;
val it : int list = [0; 1; -2; 4; 4; 7]

Ou bien, si l'on souhaite trier des chaines selon leur longueur (la fonction String.length renvoie la longueur de la chaine) :

[fsharp]
> List.sortWith (compareBy String.length) ["hello"; "world"; "i"; "love"; "F#"];;
val it : string list = ["i"; "F#"; "love"; "hello"; "world"]

Par chance, la bibliothèque standard définit deux fonctions très utiles pour les tris : List.sort qui utilise la fonction de comparaison par défaut ; List.sortBy qui trie la liste à l'aide d'une fonction de transformation. Dans la vraie vie, le dernier exemple s'écrit plutôt :

[fsharp]
> List.sortBy String.length ["Hello"; "world"; "i"; "Love"; "F#"];;
val it : string list = ["i"; "F#"; "Love"; "Hello"; "world"]

Opérateurs sur les fonctions

Plusieurs opérateurs permettent de travailler sur des fonctions. L'un d'eux est << qui sert pour la composition.

f << g correspond à « f rond g » en maths.

Par exemple :

[fsharp]
> let f = (fun x -> x * x) << (max 0);;
val f : (int -> int)

> f 4;;
val it : int = 16

> f (-4);;
val it : int = 0

La fonction f applique d'abord la fonction max 0 (max 0 est la fonction identité si l'argument est positif, sinon elle renvoie 0) puis renvoie le résultat au carré.

L'opérateur >> fait la même chose, mais applique d'abord la première fonction, puis la deuxième.

En résumé :

  f << g        g >> f        fun x -> f(g(x))

Ce sont trois expressions équivalente. Les deux opérateurs sont redondants : il est fort à parier que vous n'utiliserez qu'un seul des deux (pour ma part, je préfère le deuxième).

Il existe deux autres opérateurs utiles définis dans la bibliothèque standard :

[fsharp]
let (|>) x f = f x
let (<|) f x = f x

Cela peut sembler curieux, mais ils rendent service. Le deuxième opérateur correspond à $ en Haskell. Le premier opérateur ressemble, dans sa philosophie, au pipe des Shells Unix.

[fsharp]
> let sub5 x = x - 5;;
> let cube x = x * x * x;;

Voici 2 façons d'écrire le même calcul :

[fsharp]
> 3 |> sub5 |> cube |> abs;;
val it : int = 8

> abs(cube(sub5(3)));;
val it : int = 8

La deuxième écriture est celle que l'on a souvent dans les autres langages, mais je trouve la première bien plus simple à relire : on voit mieux l'enchainement des fonctions. Cela permet de chainer beaucoup de fonctions, de la même façon que l'on peut chainer des commandes en shell.

L'intérêt de l'opérateur <| est simplement sa faible priorité. Il permet d'éviter des parenthèses et de séparer clairement les arguments d'une fonction.

[fsharp]
printfn "Le résulat est %d" <| 3 * 2 + 5