I31 cours 05 12 PDF

Preview

Summary

Programmation fonctionnelle - COurs - 05-12...

Description

I31 – Programmation Fonctionnelle (OCaml) Cours – 05/12 Type enregistrement : Un enregistrement est un ensemble de champs. Chaque champ d'identifiant par un nom. type = {( : ;) + …} Exemple : liste de contacts. type contact_t = { nom : string; prenom : string; tel : int; } let e = { nom=''Durand''; prenom=''Jean''; tel=0628342018; } Sélection d'un champ : e. Exemple : téléphone : e.tel;; Imbrication d'enregistrement : type date_t = {jour : int; mois : int; an : int} type anniv_t = {nom : string; date : date_t} let pers = {nom=''Dupont''; date = {jour = 1; mois = 3; an = 1991}} Création d'un enregistrement à partir d'un autre enregistrement : L'opérateur with permet d'avoir un nouvel enregistrement avec des valeurs différentes pour certains champs. {e with tel = 0;};; {e with nom=''Dupont''; prenom=''Georges'';};; Remarque : l'ordre de définition des champs n'est pas important. Filtrage : le filtrage peut s'effectuer uniquement sur un champ particulier. Exemples :

type groupe_t = Amis|Famille|Travail;; type contact_t = {nom : string; prenom : string; tel : int; groupe : groupe_t};;

Compte des contacts correspondants à la famille dans une liste de contacts : let rec countfamily l = match l with | [] -> [] | {groupe = Famille}::r -> 1 + countfamily r | _::r -> countfamily r;; let rec select_family l = match l with | [] -> [] | {groupe = Famille} as e::r -> e::select_family r | _::r -> select_family r;; Sélection des contacts sur un groupe : let rec selectgroup l g = match l with | [] -> [] | e::r when e.groupe = g -> e::selectgroup r g | _::r -> selectgroup rg;;

Fonction de second ordre La programmation se définit à partir d'une instanciation de « patron » d'algorithme, c'est à dire que l'on spécialise les algorithmes pour un problème donné. Exemple : STL (C++), OCaml, Haskell. La notion de patron repose sur le fait que les algorithmes se ressemblent et leur variation porte sur peu d'éléments. Exemple : fonctions déterminant l'opposé des valeurs d'une liste. [1,2,3] → [-1,-2,-3] let rec opposite l = match l with | [] -> [] | a::r -> (-a)::opposite r;;

let rec mul100 l = match l with | [] -> [] | a::r -> (100*a)::mul100 r;;

Pour ces 2 algorithmes, seul le traitement sur l'élément a diffère. Fonction qui retourne une liste de booléens déterminant les valeurs supérieurs à 0. [10,-1,0,3] → [true,false,false,true] let rec pick l = match l with | [] -> [] | a::r -> (a>0)::pick r;; Pour ces algorithmes, le patron des programmes est identique : let rec g l = match l with | [] -> [] | a::r -> (f a)::(g::r);; Un opérateur du second ordre est un opérateur qui admet dans ses arguments une fonction. let rec map f l = match l with | [] -> [] | a::r -> (f a)::(map f r);; Fonction pure, ou non nommée : fun a → calcul let x = (fun a b -> a + b) 1 2;; ( = let x = 1 + 2;;) Exemple : let pick2 l = map(fun a -> a>0) l;; La fonction map est incluse dans OCaml pour chaque structure : List.map). Opérateur fold : let rec fold = mach l with | [] -> v | a::r -> f a::(fold f r v);;

Exemple :

- taille d'une liste : let size l = fold(fun a b -> 1 + b) l 0;; - somme des éléments d'une liste : let sum l = fold(fun a b -> a + b) l 0;;

Opérateur map2 : let rec map2 f l1 l2 = match l1 l2 with | ([],[]) -> [] | (_,[]) -> failwith ''liste de taille différente'' | ([],_) -> failwith ''liste de taille différente'' | (a1::r1,a2::r2) -> (f a1 a2)::map f r1 r2;; v = v1+ v2 . Exemple : addition de 2 vecteurs  let v = map2(fun a1 a2 -> a1 + a2) v1 v2;; Distance de Manhattan : nombre des différences de 2 listes en respectant l'ordre. let distance l1 l2 = fold(fun a b -> a + b)(map2 (fun a1 a2 -> if(a1 = a2) then 0 else 1) l1 l2) 0;; let rec distance l1 l2 = match (l1,l2) with | ([],[]) -> 0 | (a1::r1,a2::r2) -> (if(a1=a2) then 0 else 1) + (distance r1 r2) | (_,_) -> failwith ''liste de taille différente'';; Opérateurs logiques sur des ensembles : ∀x∈L : p(x) – vérifier que les éléments d'une liste ne sont pas inférieurs à 0. Exemple : ∀x∈l , x ≥0 . Opérateur forall : let forall p l = fold(fun a b -> p(a) && b) l true;; let exist p l = fold(fun a b -> (p a) || b) l false;; Exemple : Définitions d'un sous-ensemble : E⊆l . E = { x ∈L | p(x)}. filtre (ou sélection) : let filter p l = fold(fun x r -> if(p x) then x::r else r) l [];; Exemple : filtre des éléments positifs. let pos l = filter(fun x -> x >= 0) l;; expansion : remplacement de la fonction par son code. let pos l = fold(fun x r -> if(x >= 0) then x::r else r) l [];; expansion de fold : let rec pos l = match l with | [] -> [] | x::r -> if(x >= 0) then x::(pos r) else (pos r);;

La fonction de filtre peut s'écrire aussi : let rec filter p l = match l with | [] -> [] | a::r when (p a) -> a::(filter p r) | _::r -> (filter p r);;...