Les fonctions en F#

Date de publication : 14 juin 2008

F# est un langage basé sur le framework .Net. Toutefois il se distingue des langages tels que C# par son caractère fortement fonctionnel. C'est pour cette raison qu'un article complet est dédié pour introduire la notion de fonctions dans F#.

Avant-propos

Dans les langages fonctionnels, les fonctions sont des objets de "premier ordre". Cela signifie qu'une fonction est une valeur comme les autres, au même titre que les entiers ou les caractères. En pratique, on remarque en particulier que, comme les autres, les fonctions :

peuvent être nommées ;
peuvent être anonymes ;
peuvent être passées en argument à une fonction (on appelle cela une fonction d'ordre supérieur) ;
peuvent être renvoyées par une fonction.

Les fonctions sont réellement des valeurs de base et, tout comme on a les opérateurs +, -, *, etc. sur les nombres, il existe un certain nombre d'opérateurs pour combiner des fonctions et en créer des nouvelles.

I. Définition de fonctions

Pour définir une fonction, on utilise la même syntaxe que pour les autres déclarations de valeurs. Il suffit juste d'ajouter les arguments après le nom de la fonction.


let <ident> <arg> = <expression>

Par exemple :


> let sqr x = x * x;;
val sqr : int -> int

Remarquez le type de sqr : int -> int. Cela signifie qu'il prend en argument un entier et renvoie un entier. Encore une fois : il n'y a généralement pas besoin de préciser le type, le compilateur le déduit tout seul. En l'absence de contexte, le compilateur choisit le type int pour les opérateurs numériques, notamment pour la compatibilité avec OCaml. Le contexte utilisé est large : si on utilise sqr sur des nombres flottants 10 lignes plus loin, c'est le type float qui sera utilisé. Toutefois, en mode interactif, le contexte disponible est très restreint : si vous souhaitez définir la fonction sqr sur les flottants, vous pouvez aussi ajouter une information de type :


> let sqrf (x: float) = x * x;;
val sqrf : float -> float

Le type de retour est alors déduit en conséquence. Si vous voulez faire une fonction sqr générique, qui accepte aussi bien des entiers que des flottants, il faudra attendre. J'en parlerai plus tard dans le cours, puisque cela fait appel à des fonctionnalités avancées¹.
Pour appeler une fonction, il suffit de mettre ses arguments à la suite (il ne faut pas mettre de parenthèses ou de virgules) :


> sqr 4;;
val it : int = 16

Le seul but des parenthèses est de fixer la priorité :


> sqr (5 + 3);;
val it : int = 64
> sqr 5 + 3;;
val it : int = 28
> sqr (-3)
val it : int = 9

Pour le dernier cas, les parenthèses sont obligatoires. Sinon, le compilateur essaie de soustraire 3 à sqr (ce qui provoque une erreur de typage)².
Les fonctions à plusieurs arguments sont utilisées de la même façon :


> let distance x y =
    if x < y then
      y - x
    else
      x - y;;
val distance : int -> int -> int

Encore une fois, le type est clair : la fonction prend 2 entiers en argument et renvoie un entier.


> distance 4 7;;
val it : int = 3
> distance (sqr 2) (sqr 4);;
val it : int = 12

II. Fonctions locales

De la même façon que l'on peut déclarer localement un entier, on peut déclarer localement une fonction. Soit on utilise le mot-clé "in", soit on utilise le mode #light comme dans l'exemple qui suit :


> let x =
    let abs x =
      if x < 0 then
        -x
      else
        x
    abs (-4) * abs 5;;
val x : int
 
> x;;
val it : int = 20

Ici, une valeur simple (x) a été définie. Pour calculer sa valeur, on a défini localement une fonction. Cette fonction n'est pas globale et est inaccessible dès la fin de la déclaration de x.
Dans les beaucoup de langages, on peut seulement définir des variables locales au sein d'une fonction ; ici, nous venons de définir une fonction locale au sein d'une valeur simple. Les fonctions sont en effet des valeurs comme les autres (ce qui est beaucoup plus simple, quand on y réfléchit).
Autre exemple :


> [|0 .. 2 .. 10|].[ let f x = x + 1 in f 3];;
val it : int = 8

En pratique, ce genre de code n'est pas vraiment conseillé pour des raisons de clarté. Je voulais surtout attirer l'attention sur le fait que l'on peut vraiment déclarer ce que l'on veut, à l'endroit que l'on souhaite. L'intérêt est de pouvoir limiter la portée des déclarations et de ne pas polluer l'espace de noms global.
De la même façon que l'on considère souvent qu'une variable globale est dangereuse dans certains langages, on peut aimer limiter au maximum les déclarations. Cela peut favoriser la relecture (une fonction qui n'est utilisée qu'une ou deux fois pourra être déclarée près du code). De plus, plus la portée est restreinte, plus on peut se permettre d'utiliser des identifiants courts. En pratique, cela peut réduire considérablement la longueur du code (sans en réduire la clarté).

III. Fonctions récursives

Par défaut, une déclaration de valeur n'est pas récursive. C'est-à-dire, dans la déclaration suivante :


  let x = x + 1

le x de l'expression fait référence à un ancien x (défini avant).
Si l'on veut définir une valeur récursivement, il faut utiliser le mot-clé rec :


> let rec fact x =
    if x < 2 then
      1
    else
      x * fact (x - 1)
val fact : int -> int
> fact 5;;
val it : int = 120

Voici un exemple plus complet (relisez l'article précédent en cas de doute) :


> let rec square_list n =
    let sqr x = x * x
    if n = 0 then []
    else (sqr n) :: square_list (n - 1);;
 
val square_list : int -> int list
 
> square_list 5;;
val it : int list = [25; 16; 9; 4; 1]

IV. Fonctions anonymes

La syntaxe des fonctions anonymes est : fun <arg1> <argn> -> <expression>
Ainsi :


> fun x -> x + 1;;
val it : int -> int = <fun:clo@0_3>

est une fonction anonyme qui ajoute 1 à son argument. Elle peut s'utiliser partout où une fonction classique peut être appelée.


> (fun x -> x + 1) 5;;
val it : int = 6

Une fonction anonyme est une expression comme une autre.


> if 4 < 5 then
    fun x -> x + 1
else
    fun x -> x - 1;;
val it : (int -> int) = <fun:it@18>
 
> (if 4 < 5 then
    fun x -> x + 1
else
    fun x -> x - 1) 6;;
val it : int = 7

Les deux définitions suivantes sont donc équivalentes :


> let next = fun x -> x + 1;;
val next : int -> int
 
> let next' x = x + 1;;
val next' : int -> int

On peut voir la deuxième définition comme étant du sucre syntaxique pour la première.

V. Application partielle

Regardons la définition suivante :


> let add x = fun y -> x + y;;
val add : int -> int -> int

La fonction a pour type int -> int -> int. La flèche est associative à droite, le type peut aussi s'écrire : int -> (int -> int). Une fonction qui prend un argument un entier et renvoie une fonction de type int -> int peut aussi être vue comme une fonction qui prend deux entiers en argument et renvoie un entier.


> let add x y = x + y;; // ce code est équivalent au précédent
val add : int -> int -> int

Quelques exemples :


> let add' = add 4;;
val add' : (int -> int)
 
> add' 5;;
val it : int = 9
 
> add 4 5;;
val it : int = 9

D'une manière générale, toute fonction qui prend n arguments peut être appelée avec k arguments, k < n. Le résultat est une fonction qui prend k - n arguments. Cela s'appelle l'application partielle.
Les fonctions min et max sont définies dans la bibliothèque standard.


> let m = min 4;;
val m : (int -> int)
 
> m 6;;
val it : int = 4
 
> m 2;;
val it : int = 2

Les définitions suivantes sont équivalentes :


> let add x y = x + y;;
val add : int -> int -> int
 
> let add x = fun y -> x + y;;
val add : int -> int -> int
 
> let add = fun x -> fun y -> x + y;;
val add : int -> int -> int
 
> let add = fun x y -> x + y;;
val add : int -> int -> int

VI. Opérateurs

Si l'on a besoin d'utiliser un opérateur comme une expression classique, il suffit de le mettre en parenthèses :


> (+);;
val it : (int -> int -> int) = <fun:it@46>

Un opérateur étant une fonction, on peut l'utiliser en notation préfixe (pour les nostalgiques de Lisp) :


> (+) 4 6;;
val it : int = 10

Ou utiliser l'application partielle :


> (+) 4;;
val it : (int -> int) = <fun:it@47>

On constate aussi que (+) est le nom de l'opérateur, c'est en effet un identifiant comme un autre. Il est donc possible, si on le souhaite, de redéfinir l'opérateur (+). C'est cependant fortement déconseillé.
On redéfinit (+) localement :


> let (+) x y = x - y in 3 + 4;;
val it : int = -1
 
> let (-) = (+) in 5 - 3;;
val it : int = 8

Plus utile, et moins dangereux, on peut définir ses propres opérateurs :


> let (--) x y = abs (x - y);;
val ( -- ) : int -> int -> int
 
> 3 -- 5;;
val it : int = 2

Je détaillerai plus tard les règles précises pour définir ses opérateurs (concernant les noms valides, les priorités, la notion de préfixe/infixe), mais voici quelques exemples plus ou moins utiles :


> let (@-@) x y = x + " " + y;;
val ( @-@ ) : string -> string -> string
 
> "hello" @-@ "world";;
val it : string = "hello world"
 
> let (+) = 42 in 4 - (+);;
val it : int = -38

VII. 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 :


> (<);;
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...) mais représente un unique type. Cela signifie que les deux arguments de l'opérateur < doivent avoir le même type.


> 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). Juste un regardant le typage d'une fonction, on peut deviner ce qu'elle fait. Ou alors, on peut 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 avait en tête).


> let couple x y = x, y;;
val couple : '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).

VIII. 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 (sort). Voici son type :


> List.sort;;
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 soit inférieure, égale ou supérieure à la deuxième valeur.
Par exemple, on peut comparer la valeur absolue de deux entiers :


> let compare_int x y =
    if abs x < abs y then -1
    elif abs x = abs y then 0
    else 1;;
 
> List.sort 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).


> List.sort 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) :


> List.sort (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.sort (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 qui va se débrouiller. Par exemple, on écrit une fonction min, paramétrée par une fonction de comparaison :


> let min_gen cmp x y =
   if cmp x y <= 0 then x
   else y;;
 
val min_gen : ('a -> 'a -> int) -> 'a -> 'a -> 'a
 
> min_gen 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.


> let compare_by fct x y = compare (fct x) (fct y);;
val compare_by : ('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) :


> List.sort (compare_by 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) :


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

Ou alors, un tri de chaines en ignorant la casse :


> List.sort compare ["Hello"; "world"; "i"; "Love"; "F#"];;
val it : string list = ["F#"; "Hello"; "Love"; "i"; "world"]
 
> List.sort (compare_by String.lowercase) ["Hello"; "world"; "i"; "Love"; "F#"];;
val it : string list = ["F#"; "Hello"; "i"; "Love"; "world"]

On remarque maintenant que compare_by et sort sont souvent utilisés ensemble. Il est donc possible de factoriser encore plus ce code. Définissons la fonction sort_by.


> let sort_by fct list = List.sort (compare_by fct) list;;
val sort_by : ('a -> 'b) -> 'a list -> 'a list
> sort_by String.length ["Hello"; "world"; "i"; "Love"; "F#"];;
val it : string list = ["i"; "F#"; "Love"; "Hello"; "world"]

Bonne nouvelle : la fonction sort_by sera ajoutée dans la bibliothèque standard de F#, lors de la prochaine version.

IX. Opérateurs sur les fonctions

Plusieurs opérateurs permettent de travailler sur des fonctions. Le premier opérateur est << qui sert pour la composition.
f << g correspond à "f rond g" en maths.
Par exemple :


> 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) et elle met 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))

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


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 du shell (mais attention, il n'y a pas de fork ici !).


> let sub5 x = x - 5;;
> let cube x = x * x * x;;

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


> 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. Reprenons le dernier exemple de compare_by. On aurait pu l'écrire :


> min 42 <| 2 + 4;;
val it : int = 6
> max 42 <| cube (6 - 2);;
val it : int = 64

(1)	De plus, une simplification de ce mécanisme est prévu dans F#. Je préfère attendre la nouvelle syntaxe avant d'en parler ici.
(2)	Cependant, la syntaxe "sqr -3" est étudiée actuellement et pourrait être acceptée prochainement, en tant qu'application de fonction (en se basant sur les espaces pour désambiguiser)

Copyright (c) 2008 Laurent Le Brun. Permission is granted to copy and distribute under the terms of the Creative Commons licence, Version 3.0 or any later version published by the Creative Commons Corporation; with Attribution, No Commercial Use and No Derivs. Read the full license here : http://creativecommons.org/licenses/by-nc-nd/3.0/legalcode