INFO421 : Programmation fonctionnelle

Ce wiki est un complément de cours pour le cours « info-401 : programmation fonctionnelle ». La participation au wiki est fortement encouragée, et deviendra peut-être obligatoire...

Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Utilisez votre vrai nom...)

Je vous conseille d'aller voir ce guide pour vous familiariser avec les wikis.

Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fôtes d'aurtograffe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)

Détails techniques

Nouvelles

Les nouvelles récentes sont en haut de la liste...

• Hyvernat 9 février 2009 à 14:58 (CET) : le changement de jours pour le TP est confirmé : mercredi 11/02 à 13h30 en salle Maurienne 60.

• Hyvernat 9 février 2009 à 10:57 (CET) : oups... La manifestation nationale est prévue pour mardi, et non pas mercredi comme je le pensais. Le TP sera probablement déplacé pour mercredi après-midi. (Je vous enverrais un email, et essaierais de venir vous voir en cours pour vous prévenir...)

• Hyvernat 8 février 2009 à 15:59 (CET) : bien que je sois mobilisé contre les projets actuels du gouvernement, nous ferons la séance de TP prévue le mardi 10 février. (Sinon, ca sera compliqué à rattraper...) Je vous encourage à aller faire un peu de lecture ici (Sauvons la recherche) ou là (liens centralisés par F. Mangolte.

• Hyvernat 8 février 2009 à 15:53 (CET) : comme je vous l'avais annoncé, la séance de contrôle continu prévue dans Planète est supprimée : cette note sera remplacé par une note de participation aux corrections des TD/TP sur le wiki.

• Hyvernat 22 janvier 2009 à 19:05 (CET) : la DSI a modifié des trucs qui devraient supprimer certains des problèmes qu'on a eu en TP. Contactez-moi si vous rencontrez des problèmes en utilisant Emacs et Caml...

• Hyvernat 22 janvier 2009 à 19:05 (CET) : j'ai rajouté une page correction des TD / TP.

• Hyvernat 12 janvier 2009 à 09:59 (CET) : création du wiki.

Organisation des séances

• séance 1 (12/01/2009). Cours : introduction, programmation fonctionnelle, le langage Caml.
• séance 2 et 3 (19/01/2009).
  1. Cours : les valeurs, les types atomiques et fonctionnels (section Les fonctions).
  2. TD1
• séance 4 (21/01/2009) : TP0 : prise en main de Caml.
• séance 5 et 6 (26/01/2009).
  1. Cours : les tuples, les listes, un peu de filtrage et de polymorphisme
  2. TD2 : tuples et listes, un peu de filtrage, questions 1.1, 1.2 et 1.4.
• séance 7 et 8 (26/12/2009) : suite du TD2.

Compléments de cours, TD et TP

Corrections (partielles) des TD / TP

Les travaux dirigés

• feuille de TD1 : premières expressions en Caml

• feuille de TD2 : tuples, listes, un peu de filtrage

Les travaux pratiques

Ocaml

Si vous voulez installer OCaml sur votre ordinateur.

• Sous Linux : c'est la solution idéale. Il existe probablement des paquets pour votre distribution. Pour Ubuntu, pour avoir un environnement similaire à ce que vous aurez dans les salles informatiques, installez les paquets ocaml, ocaml-core, ocaml-mode, tuareg-mode et emacs.

• Sous Windows : je vous renvoie au tutoriel de Jean-Paul Roy : Installation de OCaml (sur Windows XP). Je n'ai malheureusement (??) pas accès à une machine avec Windows (98/2000/XP/Vista/7), je ne pourrais donc pas beaucoup vous aider.

Contactez moi si vous avez des problèmes.

J'ai créé une petite page dédiée pour la syntaxe de Caml et son utilisation.

TP0 : prise en main de Caml

Le TP0 prise en main de Caml, au format pdf.

• le petit fichier pour lancer l'interprète Caml : interprete-caml. (Pour le sauvegarder : clique droit sur le lien, "Enregistrer la cible du lien sous..." ; mettez le sur le bureau, et ne modifiez pas le nom du fichier...)

• la documentation de la librairie graphics.

Références supplémentaires

• Le livre d'Emmanuel Chailloux, Pascal Manoury et Bruno Pagano : Développement d'applications avec Ocaml. (Ce livre utilise une vieille version de Ocaml, mais reste pertinent.)

• La documentation de Caml, version 3.09 (utilisé en TP) : Documentation and user's manual.

Introduction

Pour paraphraser un collègue dont je ne retrouve pas le nom :

Attention : il ne s'agit pas d'un cours de programmation fonctionelle

Il s'agit plutôt d'un cours de programmation fonctionnelle...

Petit historique censuré

Je ne parlerais pas des langages pré-historiques (cartes perforées, λ-calcul, machines de Turing, ...)

D'après ce site, qui recense la plupart des langages de programmation, il y aurait plus de 2500 langages ! Voici donc une petite liste de langages importants :

• années 40 : langages d'assemblage (assembleurs). Aussi vieux que les ordinateurs eux-mêmes. Chaque langage d'assemblage est spécifique à une famille de processeurs, ce qui rend les programmes difficiles à porter. (Càd à modifier pour les faire marcher sur d'autres ordinateurs.)
• FORTRAN (1957, toujours utilisé par les numériciens et physiciens) et COBOL (1960, toujours utilisé en gestion). Ces langages ont connus des évolutions mais restent archaïques par leur conception.
• LISP : inventé par John McCarthy en 1958. C'est le premier langage fonctionnel. Toujours utilisé (sous différentes formes), en particulier en intelligence artificielle. Ce langage est basé directement sur le λ-calcul de Church.
• ALGOL (1958, a inspiré de nombreux langages depuis : C, pascal, ...) Le but était de réparer certains défauts des langages de type FORTRAN. (Programmation structurée, blocs, ...)
• Pascal (1975).
• C (1972). Toujours très utilisé, sous différentes variantes (notamment C++).
• Prolog (1972) : programmation logique, paradigme nouveau de programmation. Toujours utilisé par une petite communauté.
• ML (fin des années 1970 ?), qui ajoute une notion de type que LISP n'avait pas.
• Smalltalk (fin des année 1983), début de la programmation objet.
• 1983 : ADA.
• 1983 : Miranda un langage fonctionnel « pur ».
• 1985 : Caml, développé à l'INRIA.
• 1990 : Haskell, inspiré de Miranda.

Je vous conseille d'aller voir le graphique suivant : Computer Languages Timeline (ou découpé en pages A4).

Fonctionnel ??

L'adjectif fonctionnel a au moins deux sens :

1. qui fonctionne, en état de marche,
2. qui se rapporte aux fonctions.

Les langages fonctionnels sont bien entendus fonctionnels dans le premier sens, mais c'est surtout le second sens qui nous intéresse. Les langages tels que Pascal, Ada ou C sont qualifié, par opposition, d'impératifs.

Un des slogans de la programmation fonctionnelle en général est

Les fonctions sont des valeurs comme les autres

et c'est de là que vient la terminologie...

Comme nous le verront, cela a de nombreuses conséquences sur l'expressivité du langage et la manière de programmer.

Le langage (O)Caml

Le langage OCaml est développé par l'INRIA (Institut national de recherche en informatique et automatique). C'est un successeur de CamlLight.

Le nom Caml est formé des initiales de "Categorical Abstract Machine Language", et le langage lui même appartient à la famille de ML ("Meta Language"). C'est un langage fonctionnel strict (nous verrons ce que cela veut dire), typé (nous verrons ce que cela veut dire) qui supporte plusieurs styles de programmation :

• fonctionnel bien sûr,
• mais aussi impératif,
• objet également (c'est le « O » de OCaml).

Dans ce cours, nous utiliserons seulement le style fonctionnel.

Voici quelques aspects importants du langages que nous verrons peut-être pendant le cours :

• fonctions comme valeurs valeurs,
• polymorphisme,
• système d'exceptions,
• système de modules et de foncteurs,
• support pour des références et des données mutables (programmation « impure »),
• ...

Un aspect intéressant du langage est que c'est soit :

• un langage interprété (avec l'interpréteur OCaml),
• soit un langage compilé en bytecode (code binaire indépendant de l'architecture),
• soit un langage compilé optimisé en binaire (dépendant de l'architecture).

On peut donc choisir ce que l'on veut pour ces applications.

Autres langages fonctionnels

Il existe de nombreux autres langages fonctionnels. Je vous montrerais peut-être des exemples en cours. Voici quelques exemples importants :

• SML (Standard ML) : Wikipedia, autre dialecte de la famille ML.
• LISP, dont les deux dialectes principaux sont :

Common LISP : Wikipedia, Scheme : Wikipedia.

• Haskell : Wikipedia (inspiré en grande partie de Miranda).

Applications concrètes

Voici quelques exemples de logiciels développés en OCaml :

• Ocsigen, un serveur web,
• Unison, un logiciel de synchronisation de fichiers entre ordinateurs,
• MLDonkey, un logiciel de Peer-to-peer multiréseaux,
• Active DVI un visualisateur pour le format de fichier DVI.

La viabilité du paradigme fonctionnel se retrouve également dans le langage Erlang (Wikipedia), un langage fonctionnel développé par Ericsson pour la programmation concurrente de systèmes temps réels.

D'autre part, l'efficacité des langages fonctionnels peut être constatée sur le The Computer Language Benchmarks Game, où différents langages de programmation sont comparés (temps d'exécution, taille du code source et utilisation de la mémoire) sur des taches différentes. Les langages fonctionnels sont toujours bien représentés...

Objectifs du cours

1. être capable de définir des fonctions récursives, et comprendre ce qu'elles font
2. comprendre le typage et le polymorphisme à la ML
3. pouvoir définir des fonction d'ordre supérieur pour modulariser votre code
4. être capable de décomposer un problème
5. comprendre et utiliser la notion de type récursif
6. commencer à réfléchir à la complexité de vos programmes

Premiers pas en Caml

Les valeurs

Un des slogans de la programmation fonctionnelle est tout est une valeur, ou plus précisément,

Tout programme a une valeur.

Cette idée n'est pas présente en C, et encore moins en Pascal, où l'on distingue les expressions ("3*x+f(2)" par exemple) et les instructions ("if (n>22) then a:=12 else a:=13" par exemple). En Pascal, les instructions sont en général séparées par des ";" et sont exécutées en séquence. Les expressions sont juste calculées, et ne peuvent pas être séquentialisées.

Dans un langage purement fonctionnel, le ";" n'existe pas, et il n'y a que des valeurs...

Les valeurs sont formées en utilisant :

• les fonctions du langage (addition, multiplication)
• les opérateurs logiques (qui sont juste des fonctions des booléens vers les booléens),
• les relations mathématiques (égalité, plus grand, ... qui sont juste des fonctions dont le type de retour est le type des booléens),
• les constantes,
• les variables,
• des constructions du langage (if ... then ... else ...) par exemple).

Bien entendu, comme Caml est typé, il faut respecter les types.

Les valeurs de type atomique

Voici quelques exemples d'expressions bien formées : on suppose que n est de type entier, x est de type flottant et s de type chaîne de caractères. <source lang="ocaml">

17

</source>

<source lang="ocaml">

n

</source>

<source lang="ocaml">

n+(3*2)

</source>

<source lang="ocaml">

(n+3)*2

</source>

<source lang="ocaml">

n+3*2                  (* --> même valeur que  n+(3*2) *)

</source>

<source lang="ocaml">

length ("Bonjour")     (* --> valeur 7 *)

</source>

<source lang="ocaml">

length "Bonjour"       (* --> valeur 7 *)

</source>

<source lang="ocaml">

if (x>0) then n
         else (n+1)    (* --> suivant la valeur de x, c'est soit la valeur de n, soit la valeur de n+1 *)

</source>

<source lang="ocaml">

(if (x>0) then n
          else n) + 1  (* --> (presque) la même chose que n+1 *)

</source>

Voici des exemples de valeurs mal formées : <source lang="ocaml">

x+1                    (* --> x et 1 n'ont pas le meme type *)

</source>

<source lang="ocaml">

x+1.0                  (* --> le "+" ne fonctionne que sur des entiers (Pour les flottants, il faut utiliser "+." "*.", ...) *)

</source>

<source lang="ocaml">

length x               (* --> length a un argument de type chaine, mais x est de type flottant *)

</source>

<source lang="ocaml">

if (x=0) then x
         else n        (* --> le type d'une valeur doit etre connu, mais x et n n'ont pas le meme type *)

</source>

<source lang="ocaml">

if (true) then x
          else n       (* --> idem (meme si dans ce cas, on peut ignorer le "else") ()

</source>

Caml donne des messages d'erreur explicites dans ces cas là. Par exemple, si on rentre l'expression <source lang="ocaml">

let x = 1.5 in x+1

</source> Caml répond :

# let x = 1.5 in x+1 ;;
This expression has type float but is here used with type int

(Remarquez le x souligné pour nous dire d'où vient l'erreur...)

Remarque : en Caml, on peut déclarer une variable locale à une expression avec la syntaxe "let x= expr in expr".

Les valeurs fonctionnelles

Les exemples du paragraphe précédent ne devraient pas trop vous surprendre. La vraie nouveauté est que même les fonctions sont des valeurs. <source lang="ocaml">

length         (* valeur de type "fonction des chaînes vers les entiers" *)

</source>

Une valeur de type fonctionnel peut être définie de la manière suivante : <source lang="ocaml">

fun x y -> 2*(x+y)

</source> Ceci ressemble à une définition mathématique usuelle :

La fonction qui à $x$ et $y$ associe $2\times (x+y)$, que l'on note habituellement $x,y\mapsto 2\times (x+y)$

Remarquez que cette fonction n'a pas de nom. Les langages impératifs tels que C, ou Pascal ne permettent pas de définir une fonction sans lui donner de nom.

Une telle fonction avec 2 arguments pourra être appliquée pour obtenir une nouvelle valeur. Dans l'exemple précédent, la fonction avaient deux arguments entiers et donnait un résultat de type entier. Si on donne le nom f à cette fonction : <source lang="ocaml">

let f = fun x y -> 2*(x+y)

</source> on pourra obtenir de nouvelles valeurs telles que : <source lang="ocaml">

f 1 2

</source>

Notez bien que pour appliquer une fonction à ses arguments, les parenthèses ne sont en général pas nécessaires, et qu'on n'utilise pas de "," pour séparer les arguments.

Notion d'environnement

Comme tous les langages de programmation, Caml garde en mémoire une liste de définitions. Chacune de ces définitions met en relation un nom ("x", "n", "length", ...) et une valeur ("3.7", "42", "fun s -> ...").

Lorsque l'on lance Caml, l'environnement contient déjà de nombreuse fonctions prédéfinies : max, min, mod, +, float_of_int, ... Une occurrence d'un nom de variable de l'environnement qui est en position de variable libre sera remplacé par la valeur correspondante.

Définitions

L'utilisateur peut rajouter des définitions dans l'environnement grâce au mot clé let

• let nom = expr permet de rajouter une définition simple dans l'environnement. Exemple : let n = 42
• let nom1 = expr1 and nom2 = expr2 permet de rajouter plusieurs définitions simultanément. Exemple : let a=1 and b=2
• let rec nom = expr permet de rajouter une définition récursive dans l'environnement. Exemple : let rec f n = if (n<1) then 0 else n+ f (n-1)
• let rec nom1 = expr1 and nom2 = expr2 permet de rajouter des définitions mutuellement récursives.

Dans chacun des cas précédents, on peut annoter la définition de types de données. Ceci évite à Caml d'avoir à deviner le type que l'on souhaite et permet de préciser la fonction : <source lang="ocaml">

let n:int = 42
let rec f (n:int) : string = if (n<1) then "" else "*" ^ (f (n-1))

</source>

Si une définition utilise le même nom qu'une définition précédente, la nouvelle définition écrase l'ancienne. Par exemple : <source lang="ocaml">

# let n=42 ;;
val n : int = 42
# let n=3.1415 ;;
val n : float = 3.1415
# n ;;
- : float = 3.1415

</source>

Définitions locales

Il est possible de modifier l'environnement de manière temporaire (locale). On utilise alors let nom = expr1 in expr2. Ceci ajoute la définition nom = expr1 dans l'environnement, mais seulement pour l'évaluation de l'expression expr2. <source lang="ocaml">

1. let x =

 let y = 42 in
   y/2 ;;

val x : int = 21

1. x ;;

- : int = 21

1. y ;;

Unbound value y </source>

Les définitions locales peuvent elles aussi être multiples (let ... and ... in), récursives (let rec ... in), mutuellement récursives (let rec ... and ... in). Elles acceptent également les annotations de type...

Transparence référentielle

Une des idées importantes en programmation fonctionnelle est la notion de « transparence référentielle » : grosso-modo, cela veut dire que l'on a toujours le droit de remplacer une expression par sa valeur sans changer le sens du programme. Bien que ceci semble évident, ce n'est pas vrai dans un langage tels que le langage C...

Pour comprendre pourquoi ceci n'est pas vrai dans un programme Pascal, considérez la fonction suivante <source lang="pascal">

function f (x:integer) : integer ;
begin
  writeln('Salut...');
  y:=0;                    { y est une variable globale }
  f:=x+1;
end;

</source> La valeur de f(3) est 4, mais on ne peut pas remplacer f(3) par 4 sans changer le comportement du programme...

C'est cette propriété qui facilite grandement la formalisation des langages fonctionnels, car on peut appliquer le principe mathématique

si $x=y$ alors $f(x)=f(y)$.

Les types

Les types atomiques

Caml (et les autres langages fonctionnels typés) possèdent plusieurs types de base tels que :

• les booléens : type bool (valeur true et false),
• les entiers : type int pour les entiers signés compris entre $-2^{30}$ et $2^{30}-1$. (Les entiers Caml sont stockés sur 31 bits...)
• les flottants : type float pour les réels en virgule flottante,
• les caractères : type char (notés entre guillemets simples)
• le type unité : type unit, dont l'unique valeur est (). (Nous verrons que ce type a une utilité...)

Même s'il ne s'agit pas vraiment d'un type atomique, nous pouvons également ajouter le type des chaînes de caractères : type string (notées entre guillemets doubles).

Caml définit de nombreuse fonctions sur ces types de données :

• opérations arithmétiques
• fonctions mathématiques usuelles (logarithme, sinus, ...)
• ...

Remarques : les opérations booléennes ("&&" pour le « et » et "||" pour le « ou ») fonctionnent de à gauche à droite, et l'argument de droite n'est évalué que si c'est nécessaires. Par exemple true || (0 = 1/0) donne la valeur true, alors que que false || (0=1/0) lève l'exception Division_by_zero.

Les fonctions

Caml utilise la notation mathématique pour écrire les types des fonctions. Si f est une fonction avec un seul argument de type string et d ont la valeur de retour est de type int (la fonction length par exemple), le type de f est noté string -> int. Dans l'in terprète Caml : <source lang="ocaml">

# length ;;
- : string -> int = <fun>

</source> Nous indique que la fonction length est bien de type string->int.

Une nouveauté des langages fonctionnels par rapports à Pascal est que string->int est un type comme les autre, et on peut donc créer une fonction d e type string -> (string -> int). Prenons par exemple la fonction suivante : <source lang="ocaml">

let f:string->int = fun s ->
                      let t = "prefix-" in
                      length (t ^ s)      (* "^" est l'opérateur de concaténation des chaînes. *)

</source> Cette fonction va calculer la longueur de son argument, auquel on a rajouter le préfixe "prefix-".

Si on veut pouvoir changer le préfixe que l'on rajoute devant s, on peut faire la fonction suivante : <source lang="ocaml">

let g:string -> ( string -> int) =
  fun prefix ->
    fun s -> length (t^s)

</source> La fonction f précédente aurait pu être obtenue grâce à "g "prefix-"".

Remarque : Caml n'utilise pas les parenthèses dans ce cas là : il notera "string -> string -> int".

Nous verrons un peu plus tard que les fonctions peuvent avoir des arguments qui sont eux mêmes des fonctions.

Exercice : essayez de trouver une fonction de type (int->int) -> int.

Les paires

Un autre type intéressant est celui des paires de valeur. Par exemple, le type "int * string" est compose de valeur "(3,"toto")". On peut accéder au premier élément d'une paire avec la fonction "fst" et au second élément avec la fonction "snd". <source lang="ocaml">

let paire = ("Bonjour !" , 42*42) in (snd paire)

</source> donnera la valeur 1764.

Ce type correspond exactement à la notion de produit cartésien utilisée en mathématiques :

$A\times B\quad =\quad \{(a,b)\ |\ a\in A\,,\,b\in B\}$

Les fonctions fst et snd sont généralement appelées projections :

$\pi _{1}:A\times B\to A\qquad (a,b)\mapsto a$

(et pareillement pour la projection sur l'élément de droite...)

Ce type de données particulièrement utile lorsque l'on veut écrire une fonction qui renvoie 2 ou 3 valeurs. On verra par la suite qu'il existe d'autre types plus appropriés si l'on veut avoir de nombreux champs, et s'il l'on veut leur donner un nom. (Dans une paire, la première composante et la seconde composante n'ont pas de nom propre...)

Notez également que les fonctions a plusieurs arguments n'utilisent en général pas de produit cartésien. Pour Caml :

• une fonction de type (A*B) -> C est une fonction à un seul argument, mais son argument est une paire,
• une fonction de type A -> B -> C est une fonction à deux arguments séparés. (Plus précisément, c'est une fonction à un argument qui renvoie une fonction à un argument.)

Exercice : cherchez une manière de passer d'une fonction de type A*B -> C à une fonction de type A -> B -> C, et vice-versa. Ces transformations s'appellent la curryfication et la decurryfication.

Écrivez les fonctions curry :: ('a*'b -> 'c) -> ('a -> 'b -> 'c) et un curry : ('a -> 'b -> 'c) -> ('a*'b -> 'c) en Caml.

Remarque : dans de nombreux cas, les parenthèses autour d'un tuple ne sont pas nécessaires :

<source lang="ocaml">

1. let x = 42 , "Toto" and y = (42 , "Toto") in

   x=y ;;

- : bool = true </source>

Dans le doute, mettez des parenthèses pour éviter des bugs.

Les listes

Le type des listes est fondamental en programmation fonctionnelle. D'une certaine manière, on peut dire qu'ils remplacent les tableaux que l'on utilise constamment en programmation impérative.

Exercice : quels sont les différences importantes (utilisation, complexité, mémoire, ...) entre les tableaux et les listes ?

En Caml, une liste est représentée entre crochets, et les éléments sont séparés par des points-virgules : <source lang="ocaml">

# let une_liste = [ 1 ; 2 ; 2 ; -1 ; 0 ] ;;
val une_liste : int list = [1; 2; 2; -1; 0]
# let une_autre_liste = [ "coucou" ; "je m'appelle" ; "Bob" ] ;;
val une_autre_liste : string list = ["coucou"; "je m'appelle"; "Bob"]

</source>

Comme vous pouvez le voir dans l'exemple au dessus, le type des listes d'entiers s'appelle "int list", le type des listes de flottants s'appelle "float list" et le type des listes de listes d'entiers s'appelle ... "int list list".

Contrairement au cas du produit cartésien de types, les éléments d'une liste doivent tous avoir le même type : <source lang="ocaml">

# let une_non_liste = [ 1 ; "Toto" ; 1.3 ] ;;
This expression has type string but is here used with type int

</source>

Attention : quel est le type de la liste suivante ?

<source lang="ocaml">

# let une_liste_bizarre = [ 1 , 2 , 3 ] ;;

</source>

La concaténation des listes s'obtient avec l'opérateur "@" et pour rajouter un element devant une liste existante on utilise "::". <source lang="ocaml">

1. 0::[1;2;3;4] ;;

- : int list = [0; 1; 2; 3; 4]

1. [-1;-2;-3;-4] @ [1;2;3;4] ;;

- : int list = [-1; -2; -3; -4; 1; 2; 3; 4] </source> Il existe en plus (dans la bibliothèque "List" les fonctions suivantes

• length,
• hd pour récupérer le premier élément d'une liste,
• tl pour récupérer la queue d'une liste (toute la liste, sans son premier élément).

Remarque : Caml possède plusieurs fonctions length : notamment une pour les listes et une pour les chaînes de caractères. Pour accéder à ces fonctions (qui ne sont pas dans la bibliothèque standard), il faut utiliser :

• List.length pour la longueur des listes,
• String.length pour la longueur des chaînes.

Vous pouvez aussi ouvrir toute la bibliothèque correspondante en utilisant la ligne "open List" au début de votre programme pour avoir accès à toutes les fonctions de la bibliothèque sur les listes...

La manière usuelle de définir des fonctions récursives sur les listes d'utilisez plutôt le filtrage ("pattern matching") décrit plus loin, ou les fonctions prédéfinies comme List.fold_left ou List.fold_right (qui seront vues en TD et TP).

--- examples et explication de fold ?

Filtrage, première partie

La notion de filtrage, aussi appelé "pattern-matching" est un outils clé pour la programmation en Caml. L'idée est d'essayer de faire correspondre une valeur avec un certain nombre de motifs. Le "case .. of" de Pascal en est une version ultra pauvre et simplifiée.

En Caml, la syntaxe du pattern matching est la suivante :

match expr with
   pattern1  ->  expr1
 | pattern2  ->  expr2
 | pattern3  ->  expr3
 | pattern4  ->  expr4

L'évaluation d'une telle expression se fait de la manière suivante : Caml évalue l'expression "expr", et essaie de la faire coïncider au motif "pattern1" (on dit que Caml essaie d'unifier l'expression "expr" avec le motif "pattern1"). Si il y parvient, il évalue l'expression "expr1" et renvoie la valeur correspondante. Caml regarde tous les motif dans l'ordre.

Par exemple, <source lang="ocaml">

match (2+2) with
   1 -> "Problème."
|  3 -> "Problème."
|  4 -> "Ouf"
|  _ -> "problème."

</source> s'évaluera en la valeur "Ouf".

Le motif "_" est un motif universel, et permet de faire ce que l'on ferait avec un "else" en Pascal. Le véritable avantage de filtrage de Caml se voit dans le filtrage sur les types "composés" comme les tuples, les listes ou les types sommes. Le filtrage permet de "déconstruire" une valeur en ces différents constituants. Par exemple, voici comment on pourrait programmer la fonction "fst" <source lang="ocaml">

 let premier p = match p with
   (x,y) -> x

</source> Pour évaluer "premier e", Caml essaie de faire coïncider la valeur de "e" avec un truc de la forme "(x,y)". S'il y arrive, alors il renvoie la valeur "x". Le typage de Caml inférera automatique que "p" doit être une paire, et il n'y a donc pas besoin de prévoir un cas par defaut.

On peut écrire des motifs plus intéressants comme <source lang="ocaml"> let imaginaire_pur x = match x with

   (0,_) -> true
 | _  -> false

</source> qui permettra de tester si la première coordonnée (partie réelle d'une nombre complexe) est nulle ou pas. On aura pu écrire de manière équivalente : <source lang="ocaml"> let imaginaire_pur x = if (fst x = 0) then true else false </source>

Question : à votre avis, que fait la fonction suivante :

<source lang="ocaml"> let une_fonction x = match x with

   (1,(y,z))  -> y-z
 | (0,(y,z)   -> y+z
 | (-1,(y,z)  -> z-y
 | (_,(y,_)   -> y

</source>

Attention : les variables qui apparaissent dans les motifs « écrasent » les variables de même nom qui peuvent apparaître avant dans l'expression :

<source lang="ocaml"> let f x = match x with

(x,_) -> x

</source>

calcule la fonction "fst". De plus, les motifs ne sont pas évalués : dans

<source lang="ocaml">

let un = 1
let g x = match x with
    un -> 1
  | 2 -> 2
  | _ -> 3

</source>

la fonction "g" prendra toujours la valeur 1 car le "un" est considéré comme un nom de variable...

Pour filtrer sur une liste, on utilise "[]" et "::". Par exemple, voici une manière de tester si une liste est vide : <source lang="ocaml">

let vide l = match l with
    [] -> true
  | x::xs  ->  false

</source> On peut écrire des fonctions comme <source lang="ocaml"> let un_element l = match l with

   [x] -> true
 | _ -> false

let deux_elements l = match l with

   x::y::[] -> true
 | _ -> false

let trois_element_ou_plus l = match l with

   _::_::_::_  -> true
 | _ -> false

</source>

--- complément sur l'unification, un peu plus de détails ?
--- un motif qui contient juste une variable est universel

Compléments syntaxiques : Caml définit les sucres syntaxiques suivants

• "or pattern" : on peut grouper plusieurs motifs qui définissent les mêmes variables et donnent la même expression

<source lang="ocaml"> let f x = match x with

   0::l | 1::l | 1::l  -> l  (* on groupe 3 motifs en une seule ligne *)
 | [] -> []
 | x::_ -> [x]

</source>

• "garde pour les motifs" : on peut « garder » les motifs par une condition avec le mot clé "when"

<source lang="ocaml"> let g x = match x with

   x::xs  when (List.lenght (f xs) = 1)  ->  true
 | _ -> false

</source>

• fonction par filtrage : comme on définit souvent des fonctions par filtrage, Caml autorise la syntaxe

<source lang="ocaml"> function

   pattern1 -> expr1
 | pattern2 -> expr2
 | ...

</source>

plutôt que

<source lang="ocaml"> fun x -> match x with

   pattern1 -> expr1
 | pattern2 -> expr2
 | ...

</source>

Remarquez que l'on ne peut faire ça que pour une fonction à une seule variable...

• fonction par filtrage : s'il n'y a qu'un seul motif, on peut alors utiliser le mot clé "fun" habituel, ce qui permet la définition d'une fonction à plusieurs arguments. (Mais dans ce cas, les parenthèses autour des tuples sont obligatoires.)

<source lang="ocaml">

1. let h = fun (x,y) z (u,v,w) -> x+y+z+v ;;

val h : int * int -> int -> 'a * int * 'b -> int = <fun> </source>

Le polymorphisme

Nous avons vu que Caml était un langage fortement typé : toutes les expressions ont un type, et on ne peut appliquer des fonctions que lorsqu'elles ont ses arguments ont le bon type.

Quel est le type de la fonction "fst" ? <source lang="ocaml">

 let fst = function (x,_) -> x

</source> Cette fonction est à la fois de type "int * int -> int", "int * float -> int", ... Pour Caml, cette fonction est de type "t1 * t2 -> t1" pour n'importe quels types "t1" et "t2". Caml dénote un tel type avec de guillemets simples de la manière suivante : <source lang="ocaml">

1. let fst = function (x,_) -> x ;;

val fst : 'a * 'b -> 'a = <fun> </source>

Complément : même si cela ne vous arrivera probablement pas dans un premier temps, sachez que seuls les valeurs évaluées peuvent être polymorphes. Par exemple, dans

<source lang="ocaml">

1. let i x = x

 let j = i i ;;

val i : 'a -> 'a = <fun> val j : '_a -> '_a = <fun> </source>

l'expression "j" n'est pas vraiment polymorphe. (C'est le sens du "_" devant le "a".) Le "'_a" veut dire : « la fonction "j" a pour type "t -> t", mais je ne connais pas encore ce type "t".) »

Dés que l'on applique "j" à quelque chose, Caml pourra savoir quel est le type de "j" :

<source lang="ocaml">

1. j 42 ;;

- : int = 42

1. j ;;

- : int -> int = <fun> </source>

Remarque : polymorphisme « ad-hoc »...

--- à faire