Introduction à CAML Cours de Programmation Fonctionnelle

Expressions fonctionnelles

Application d’une fonction a un element

#(fun x -> x*x) 4;;
– : int = 16
#square 4;;
– : int = 16
L’op´erateur d’application est note simplement par un nombre ¿0 d’espaces. C’est l’op´erateur de plus forte priorit´e.
#square 2+3;;
– : int = 7
#square (2+3);;
– : int = 25

Ordre superieur

 Curryfication

Toute fonction Caml est une fonction a un seul argument. Consid´erons la fonction math´ematique :
f : ZxZ – Z
(x, y) – f(x, y) = x ∗ y
Cette fonction a 2 arguments peut se repr´esenter a l’aide de la fonction unaire F d´efinie par :
F : Z -(Z⇒Z)
x – F (x) = f x
ou la fonction fx est d´efinie par
f x : Z – Z
y – f x(y) = x ∗ y
La fonction F est une fonction d’ordre sup´erieur puisque pour tout x, F(x) est une fonction. F d´efinit en fait une famille de fonctions (fx), index´ee sur Z. Elle est appel´ee ”curryfiee” de f (du nom du math´ematicien Curry).
#let F = fun x -> fun y-> x*y;;
F : int -> int -> int = <fun>
Autres ´ecritures strictement ´equivalentes a la pr´ec´edente :
#let F = fun x y -> x*y;;
F : int -> int -> int = <fun>
#let F x = fun y -> x*y;;
F : int -> int -> int = <fun>
#let F x y = x*y;;
F : int -> int -> int = <fun>
Le type int -> int -> int est par defaut parenth`ese de droite a gauche :
int -> (int -> int)
Applications successives de F a 2 arguments :
#F 2 34;;
– : int = 68
Dans les applications successives le parenthesage se fait par defaut de gauche a droite. L’ex-pression calcul´ee ci-dessus est en fait ainsi parenth´es´ee : ((F 2)34).
On peut utiliser F pour d´efinir par exemple la fonction ”triple”.
#let triple = F 3;;
triple : int -> int = <fun>
#triple 21;;
– : int = 63
Remarque. La curryfication introduit une dissym´etrie dans les arguments. On aurait pu curryfier de la fa¸con suivante :
G : Z -(Z⇒Z)
y – (x – f(x, y))

Fonctions en argument

Nous venons de voir que la fonction F renvoie une valeur fonctionnelle. De fa¸con analogue une expression fonctionnelle peut ˆetre l’argument d’une fonction. Il est ainsi possible de d´efinir la fonction ”comp” qui prend en arguments 2 fonctions et qui renvoie leur compos´ee.
#let comp f g x = f (g x);;
comp : (’a -> ’b) -> (’c -> ’a) -> ’c -> ’b = <fun>
#comp square triple 4;;
– : int = 144
#comp square;;
– : (’_a -> int) -> ’_a -> int = <fun>
#let f = comp square int_of_float;;
f : float -> int = <fun>
# f 4.1;;
– : int = 16

Eta-r´eduction

La fonction ”triple” aurait pu aussi ˆetre ainsi d´efinie :
#let triple = fun x -> F 3 x;;
triple : int -> int = <fun>
Les 2 formes sont ´equivalentes. En fait, si f est l’expression d’une fonction,
(fun x -> f x) et f
sont des expressions ´equivalentes. On dit que la seconde est obtenue a partir de la premi`ere par eta-r´eduction.

Op´erateurs infixes

& est un op´erateur infixe. L’op´erateur pr´efixe correspondant est note prefix &.
#prefix &;;
– : bool -> bool -> bool = <fun>
#prefix & true false;;
– : bool = false
#prefix & true;;
– : bool -> bool = <fun>
#& true false;;
Toplevel input:
>& true false;;
>^
Syntax error.
#prefix <;;
– : ’a -> ’a -> bool = <fun>
L’utilisateur peut d´efinir ses propres op´erateurs infixes par la commande #infix « … ».
Exemple.
#let o = fun f g x->f(g(x));;
o : (’a -> ’b) -> (’c -> ’a) -> ’c -> ’b = <fun>
l’op´erateur o est pr´efixe.
#o sq sq 2.;;
– : float = 16.0 ##infix « o »;;
A partir de ce moment la, il devient infixe et ne peut plus ˆetre utilise sous forme pr´efixe :
#(sq o sq) 2.;;
– : float = 16.0
#sq o sq 2.;;
Toplevel input:
>sq o sq 2.;;
> ^^^^^
This expression has type float, but is used with type ’a -> float.
car l’application a la plus forte priorit´e.
#o sq sq 2.;;
Toplevel input:
>o sq sq 2.;;
>^
Syntax error
car il n’est plus pr´efixe.
##uninfix « o »;;
Il redevient pr´efixe :
#o sq sq 2.;;
– : float = 16.0