Programmation fonctionnelleweb4.ensiie.fr/~stefania.dumbrava/IPF/cours.pdf · Programmation fonctionnelle Julien Forest - ensiie - IPF 1/50. Fonctionnement du cours Regles de vie

Programmation fonctionnelle

Julien Forest - ensiie - IPF 1/50

Fonctionnement du cours

Regles de vie :I pas d’ordinateur portable dans l’amphitheatre ou en TD,I ne pas hesiter a poser des questions (en cours, en TD,. . . ),I arriver a l’heure,I pas de reprise du cours en TD , en TP.

Regles d’examens :I Premiere session :

projet (1/3) + examen sur table (2/3)I Deuxieme session : Examen ecrit qui remplace tout


Introduction

Imperatif vs Fonctionnel vs Objet . . .

Partir du probleme ; choix structure ; paradigme ; langage.

Plan du cours :I Notions de base (1 cours)I Plusieurs parties :

I Structure de donneesI Outils

I Notions de modules

I Un peu d’imperatif a la fin et du mixage.

Machines : manipulation, mise en œuvre

Travaux diriges : aspects theoriques, interet


Introduction










Introduction










Biblio

I Developpement d’applications avec OCamlI Chailloux, Manoury, PaganoI O’ReillyI http://www.pps.jussieu.fr/Livres/ora/DA-OCAML/

I Purely Functional Data StructuresI OkasakiI Cambridge University Press

SML !


http://www.pps.jussieu.fr/Livres/ora/DA-OCAML/

http://www.pps.jussieu.fr/Livres/ora/DA-OCAML/

Biblio

I Approche fonctionnelle de la programmationI Cousineau, MaunyI Ediscience/Dunod

Camllight !

I Le langage CamlI Leroy, WeisI Dunod


Rappels/Mise au point


Introduction

Programmation fonctionnelle?I Tout est valeur expressions,fonctions,modules?I Persistance Aucune modification

I Code simple ; correctionI Efficacite

Similaire a mathematiques ; abstraction/haut niveau

Modele formel : λ-calcul x (M1 M2) λx .M →β

Preuves aisees et naturelles.


Noyau fonctionnel : les fondements

Programme = listeI Expressions

; valeurs

I Declaration

; noms

I Separateurs (,) et ; ;

Valeurs predefinies :I Valeurs basiques (entiers, floatants,. . .) typees

I Operations arithmetiques et logiques respectant les typesI Comparaisons arguments de meme types

Typage fort⇒ pas d’erreur de segmentation



Programme = listeI Expressions ; valeursI Declaration ; nomsI Separateurs (,) et ; ;













Valeurs predefinies :I Valeurs basiques (entiers, floatants,. . .) typeesI Operations arithmetiques et logiques respectant les types

I Comparaisons arguments de meme types





Valeurs predefinies :I Valeurs basiques (entiers, floatants,. . .) typeesI Operations arithmetiques et logiques respectant les typesI Comparaisons arguments de meme types





Valeurs predefinies :I Valeurs basiques (entiers, floatants,. . .) typeesI Operations arithmetiques et logiques respectant les typesI Comparaisons arguments de meme types



Noyau fonctionnel : declarations

But : donner un nom a une valeur globalementlet x = expr (*x : nom de la valeur d’expr *)

let toto = 21 * 2 {(toto,42),. . . }Jamais modife apresidentificateur ; expression

let titi = toto {(titi,42), (toto,42),. . . }let toto = 3*222titi?















let titi = toto {(titi,42), (toto,42),. . . }let toto = 3*222 {(toto,666),(titi,42), (toto,42),. . . }titi?





let titi = toto {(titi,42), (toto,42),. . . }let toto = 3*222 {(toto,666),(titi,42), (toto,42),. . . }titi? 42


Noyau fonctionnel : declarations locales

But : donner un nom a une valeur localementlet x = e1 in e2 (*x : nom de la valeur d’expr *)

{(toto,666)}let = 84 / 2 in {(,42),(toto,666)}* 2 {(,42),(toto,666)}

{(toto,666)}




{(toto,666)}

let titi = 84 / 2 in {(titi,42),(toto,666)}titi = * 2 {(titi,42),(toto,666)}

{(toto,666)}

identificateur visible uniquement dans la partie in portee




{(toto,666)}let titi = 84 / 2 in {(titi,42),(toto,666)}

titi = * 2 {(titi,42),(toto,666)}{(toto,666)}





{(toto,666)}let titi = 84 / 2 in {(titi,42),(toto,666)}titi = titi* 2 {(titi,42),(toto,666)}

{(toto,666)}






{(toto,666)}






{(toto,666)}





{(toto,666)}let titi = 84 / 2 in {(titi,42),(toto,666)}titi = toto* 2 {(titi,42),(toto,666)}

{(toto,666)}





{(toto,666)}let toto = 84 / 2 in {(toto,42),(toto,666)}toto* 2 {(toto,42),(toto,666)}

{(toto,666)}

CAPTURE


Noyau fonctionnel declarations

Enchaıner les declarations

let x = e1 inlet y = e2 in...

Declarations simultanees

let x = e1and y = e2 in...

Donner un nom ou pas

let _ = e1let _ = e1 in e2


















Les expressions branchement

if e1 then e2 else e3

Types :I e1 : bool,I e2 et e3 meme type ⇒ else “obligatoire”

Valeur :I e2 si e1 vaut trueI e3 si e1 vaut false

if 666 < 42 then 666 else 42;; (*vaut 42 *)

Rq : branchement 6= fonction logique

if cond then true else false;;






if 666 < 42 then 666 else 42;; (*vaut 42 *)








if 666 < 42 then 666 else 42;; (*vaut 42 *)








if 666 < 42 then 666 else 42;; (*vaut 42 *)

Rq : branchement 6= fonction logiqueif cond then true else false;;






if 666 < 42 then 666 else 42;; (*vaut 42 *)



cond;;


Les expressions imbrication

(0x29a = 42) || (3 < 666);;

3+(if 42 < 666 then 1 else 322);;

(float_of_int 3) < 2.5 ; ;

I Manipulation d’expressionsI Bon typageI Pas de conversion implicite



(0x29a = 42) || (3 < 666);;

3+(if 42 < 666 then 1 else 322);;

3 < 2.5 ; ;




(0x29a = 42) || (3 < 666);;

3+(if 42 < 666 then 1 else 322);;

(float_of_int 3) < 2.5 ; ;



Les expressions les fonctions

fonction : valeur comme les autresfun x -> e

parametre formel x + corps e

Typage : α→ β si e de type β quand x de type α

Application :I Syntaxte (my_fonc my_arg)

I Evaluation

1. Remplacement de le corps du parametre formel par une valeur2. Evaluation du corps.



fonction : valeur comme les autresfun x -> e parametre formel x + corps e



I Evaluation







I Evaluation







I Evaluation







I Evaluation1. Remplacement de le corps du parametre formel par une valeur

2. Evaluation du corps.






I Evaluation1. Remplacement de le corps du parametre formel par une valeur2. Evaluation du corps.


Les fonctions : valeurs comme les autres

Nomage . . . (y compris localement)

let f = fun x -> e1

En parametre. . .

lef f = fun g ->(...(g e2)...)︸︷︷︸

M

Type : (α→ β)→ γ si e2 : α et M : γ quand x : α→ β

Retourner comme resultat (valeur). . .

let f = fun x -> (fun y -> e3)Type : α→ (β → γ) si e3 : γ quand x : α et y : β

(α→ β)→ γ 6=α→ (β → γ)



Nomage . . . (y compris localement)

let f = fun x -> e1

En parametre. . .

lef f = fun g ->(...(g e2)...)︸︷︷︸

M




(α→ β)→ γ 6=α→ (β → γ)



Nomage . . . (y compris localement)let f = fun x -> e1

En parametre. . .

lef f = fun g ->(...(g e2)...)︸︷︷︸

M




(α→ β)→ γ 6=α→ (β → γ)




En parametre. . .lef f = fun g ->(...(g e2)...)︸︷︷︸

M




(α→ β)→ γ 6=α→ (β → γ)





M


Retourner comme resultat (valeur). . .let f = fun x -> (fun y -> e3)

Type : α→ (β → γ) si e3 : γ quand x : α et y : β

(α→ β)→ γ 6=α→ (β → γ)





MType : (α→ β)→ γ si e2 : α et M : γ quand x : α→ β

Retourner comme resultat (valeur). . .let f = fun x -> (fun y -> e3)

Type : α→ (β → γ) si e3 : γ quand x : α et y : β

(α→ β)→ γ 6=α→ (β → γ)





MType : (α→ β)→ γ si e2 : α et M : γ quand x : α→ β

Retourner comme resultat (valeur). . .let f = fun x -> (fun y -> e3)Type : α→ (β → γ) si e3 : γ quand x : α et y : β

(α→ β)→ γ 6=α→ (β → γ)


Les fonctions : subtilites

let f = fun x1 -> fun x2 -> . . . -> fun xn -> e

Application partielle (tq→ dans type) (f e1 . . . ek); nouvelle fonction dependant des valeurs a la creation

let ex = fun x -> fun y -> x + y

ex 42 ; fun y -> 42 + yex 666 ; fun y -> 666 + y

Pas d’evalution “sous des fun”let f1 = fun x -> fun y -> 2 * x + 2 * ylet f2 = fun x ->let x1= 2 * x in fun y -> x1+ 2 * yf1 42;fun y -> 2 * 42 + 2*yf2 42;fun y -> 84 + 2*y






ex 42 ; fun y -> 42 + yex 666 ; fun y -> 666 + y

Pas d’evalution “sous des fun”let f1 = fun x -> fun y -> 2 * x + 2 * ylet f2 = fun x ->let x1= 2 * x in fun y -> x1+ 2 * yf1 42;fun y -> 2 * 42 + 2*yf2 42;fun y -> 84 + 2*y






ex 42 ; fun y -> 42 + yex 666 ; fun y -> 666 + y

Pas d’evalution “sous des fun”let f1 = fun x -> fun y -> 2 * x + 2 * ylet f2 = fun x ->let x1= 2 * x in fun y -> x1+ 2 * y

f1 42;fun y -> 2 * 42 + 2*yf2 42;fun y -> 84 + 2*y






ex 42 ; fun y -> 42 + yex 666 ; fun y -> 666 + y

Pas d’evalution “sous des fun”let f1 = fun x -> fun y -> 2 * x + 2 * ylet f2 = fun x ->let x1= 2 * x in fun y -> x1+ 2 * yf1 42;fun y -> 2 * 42 + 2*yf2 42;fun y -> 84 + 2*yJulien Forest - ensiie - IPF 16/50

Noyau fonctionnel recursion

Fonction recursive : cas de base + hypothese de recurrencelet rec f = . . . f . . .

Exemple : la factorielleI Cas de base : 0 ! = 1I Cas recurrence : hypothese n! = v ; (n + 1)! = v × (n + 1)

let rec fact = fun n ->if n = 0then 1

else (fact (n -1)) * n

v * n

Rq recursion non terminale : pile d’appel non bornee ; risque







v * n








v * n






let rec fact = fun n ->if n = 0then 1else let v = fact (n-1) in

v * n






let rec fact = fun n ->if n = 0then 1else let v = fact (n-1) inv * n






let rec fact = fun n ->if n = 0then 1else (fact (n -1)) * n

v * n




Ex : factorielleDef plus generale : ∀a,∀n, (f a n) = a× n!

I Cas de base : ∀a, f a 0 = aI Cas de recurrence : hyp : ∀a, f a n = a× n!

; ∀a, f a (n+1) = f (a× (n+1)) n = a× (n+1)×n! = a× (n+1)!

let rec fact_gen = fun acc n ->if n = 0 then accelse fact_gen (acc * n) (n-1)let fact2 = fact_gen 1

Rq recursion terminale : pile d’appel bornee





; ∀a, f a (n+1) = f (a× (n+1)) n = a× (n+1)×n! = a× (n+1)!

let rec fact_gen = fun acc n ->if n = 0 then accelse fact_gen (acc * n) (n-1)

let fact2 = fact_gen 1






; ∀a, f a (n+1) = f (a× (n+1)) n = a× (n+1)×n! = a× (n+1)!

let rec fact_gen = fun acc n ->if n = 0 then accelse fact_gen (acc * n) (n-1)let fact2 = fact_gen 1



Noyau fonctionnel terminale/non terminale

fact 4 fact2 4

fact 3 * 4 fact gen 1 4

fact 2 * 3 * 4 fact gen 4 3

fact 1 * 2 * 3 * 4 fact gen 12 2

fact 0 * 1 * 2 * 3 * 4 fact gen 24 1

1 * 1 * 2 * 3 * 4 fact gen 24 0

24 24



fact 4 fact2 4



fact 1 * 2 * 3 * 4 fact gen 12 2

fact 0 * 1 * 2 * 3 * 4 fact gen 24 1

1 * 1 * 2 * 3 * 4 fact gen 24 0

24 24



fact 4 fact2 4



fact 1 * 2 * 3 * 4 fact gen 12 2

fact 0 * 1 * 2 * 3 * 4 fact gen 24 1

1 * 1 * 2 * 3 * 4 fact gen 24 0

24 24



fact 4 fact2 4



fact 1 * 2 * 3 * 4 fact gen 12 2

fact 0 * 1 * 2 * 3 * 4 fact gen 24 1

1 * 1 * 2 * 3 * 4 fact gen 24 0

24 24



fact 4 fact2 4



fact 1 * 2 * 3 * 4 fact gen 12 2

fact 0 * 1 * 2 * 3 * 4 fact gen 24 1

1 * 1 * 2 * 3 * 4 fact gen 24 0

24 24



fact 4 fact2 4



fact 1 * 2 * 3 * 4 fact gen 12 2

fact 0 * 1 * 2 * 3 * 4 fact gen 24 1

1 * 1 * 2 * 3 * 4 fact gen 24 0

24 24



fact 4 fact2 4



fact 1 * 2 * 3 * 4 fact gen 12 2

fact 0 * 1 * 2 * 3 * 4 fact gen 24 1

1 * 1 * 2 * 3 * 4 fact gen 24 0

24 24


Noyau fonctionnel Inference

let rec f = fun g -> fun n -> fun x ->if n = 0 then xelse f g (n-1) (g x)

Type de f?

(α→ α)→ int → α→ α


Noyau fonctionnel Inference

let rec f = fun g -> fun n -> fun x ->if n = 0 then xelse f g (n-1) (g x)

Type de f?

(α→ α)→ int → α→ α


Noyau fonctionnel types produits

Etendre les types de base. . .t1* . . .*tn type des tuples (x1,· · ·,xn) avec xi : ti

Rq : α ∗ (β ∗ γ) 6= α ∗ β ∗ γ 6= (α ∗ β) ∗ γRq : (α ∗ β)→ γ 6= α→ β → γ

Construction : let triplet = (42,true,"pfff");;Destructuration : let (a,b,c) = triplet;;

Cas particulier : les couples fst: α ∗ β → α, snd: α ∗ β → β




















Noyau fonctionnel declarations de types

Permet de creer ses propres types. . .Declaration : type t = . . .Affirmation : (expr : t)

type int_quad = int * int * int * int;;let t1 = 1,2,3,4;;let t2 : int_quad = 4,3,2,1;;

Enregistrements produits avec noms de champstype compl = { real : float; im : float };;let i = { real = 0.0; im = 1.0 };;let i_real = i.real;;










Enregistrements produits avec noms de champs

type compl = { real : float; im : float };;let i = { real = 0.0; im = 1.0 };;let i_real = i.real;;







Noyau fonctionnel constructeurs

Definir types structures enumeration, union,. . .

type couleur = (* Ex enumeration *)| Pique | Coeur (* Majuscule en debut du nom *)| Carreau | Trefle

type rang =| Roi | Dame | Valet| Ordinaire of int (* Etiquette contenant int *)

Recuperation : filtrage sur la structure et pas sur la valeur !

match valeur with (* Une seule expression *)| motif1 -> e1 (* motif : constructeurs + variables*)| motif2 -> e2| · · · (* motifs testes DANS L’ORDRE ! *)

Filtrer : ∃? un remplacement des variables pour retrouver la valeur
























Filtrer : ∃? un remplacement des variables pour retrouver la valeurJulien Forest - ensiie - IPF 24/50

Noyau fonctionnel filtrage

motif : constructeurs + variables Filtrer : ∃? remplacement

Pas de nom de valeur dans les motifsFiltrage exhaustif

let x = · · ·let y = 2match x with| Roi -> Printf.printf "Wow"| Ordinaire -> Printf.printf "Bof"| _ -> Printf.printf "Ok"(*En dernier : ORDRE *)



motif : constructeurs + variables Filtrer : ∃? remplacement

Pas de nom de valeur dans les motifsFiltrage exhaustif

let x = · · ·

let y = 2

match x with| Roi -> Printf.printf "Wow"| Ordinaire toto -> Printf.printf "Bof"

| _ -> Printf.printf "Ok"(*En dernier : ORDRE *)



motif : constructeurs + variables Filtrer : ∃? remplacementPas de nom de valeur dans les motifs

Filtrage exhaustif

let x = · · ·let y = 2match x with| Roi -> Printf.printf "Wow"| Ordinaire y -> Printf.printf "Bof"

| _ -> Printf.printf "Ok"(*En dernier : ORDRE *)



motif : constructeurs + variables Filtrer : ∃? remplacementPas de nom de valeur dans les motifsFiltrage exhaustif

let x = · · ·

let y = 2

match x with| Roi -> Printf.printf "Wow"| Ordinaire toto -> Printf.printf "Bof"| Dame | Valet -> Printf.printf "Ok"(*Meme valeur *)



motif : constructeurs + variables + _ Filtrer : ∃? remplacementPas de nom de valeur dans les motifsFiltrage exhaustif

let x = · · ·

let y = 2

match x with| Roi -> Printf.printf "Wow"| Ordinaire toto -> Printf.printf "Bof"| _ -> Printf.printf "Ok"(*En dernier : ORDRE *)



C’est une expression⇒ utilisable partout

let f = fun x -> match x with · · ·

Structure profonde :

type carte = C of (Couleur * rang)

match x with| C(Coeur,Dame) -> Printf.printf "Ok"| C(_,Ordinaire n) -> Printf.printf "valeur = %d" n| _ -> · · ·
















Noyau fonctionnel inductifs

cf. cours de logiqueType : ensemble inductif def par les constructeurs.

type entier =| Z| S of entier

match . . . with| Z -> . . .| S e -> . . .

let rec int_of_entier = fun e ->match e with| Z -> 0| S e’ -> 1 + int_of_entier e’





match . . . with| Z -> . . .| S e -> . . .






match . . . with| Z -> . . .| S e -> . . .






match . . . with| Z -> . . .| S e -> . . .



Noyau (pas tres fonctionnel) exceptions

Comme en objet : valeur en cas d’erreur1/0;;Exception: Division_by_zero

. . . affinage du typage (fonctions partielle)

. . . pour interrompre le calculet peut-etre le reprendre plus tard autrement

Definition :exception Mon_exception;;exception Autre of string

Levee :raise Mon_exceptionraise (Autre "Impossible de faire le calcul")



Comme en objet : valeur en cas d’erreur1/0;;Exception: Division_by_zero. . . affinage du typage (fonctions partielle)







. . . pour interrompre le calcul

et peut-etre le reprendre plus tard autrement













Definition :exception Mon_exception;;

exception Autre of string

Levee :raise Mon_exception

raise (Autre "Impossible de faire le calcul")









Rattrapage : cf objet try e1 with Motif_exc -> e2

1. Evalutation de e1 sans exception ; valeur de e1

2. Exception dans e1a Filtree par Motif_exc ; valeur de e2b Non filtree : exception propagee












Listes

Structure dynamique

Structure :I VideI Ajout de e en tete de l

Fonction :I Ajout en teteI VaccuiteI AppartenanceI Concatenation

PB : temps de calcul


Listes

Structure dynamique





Listes

Structure dynamique


Fonction :I Ajout en tete

I VaccuiteI AppartenanceI Concatenation



Listes

Structure dynamique


Fonction :I Ajout en teteI Vaccuite

I AppartenanceI Concatenation



Listes

Structure dynamique


Fonction :I Ajout en teteI VaccuiteI Appartenance

I Concatenation



Listes

Structure dynamique





Listes

Structure dynamique


Fonction :I Ajout en teteI VaccuiteI AppartenanceI Concatenation PB : temps de calcul


Listes

+ Ajout en tete : temps constant

+ FILO : ordre d’entree conserve- Appartenance lineaire- Concatenation lineaire

Type ’a list natif dans Ocaml :I Liste vide : []I Constructeur : ::

Utilsables dans le filtrage

Notation : [a;b;. . .;k]⇔ a::b::. . .::[]


Listes

+ Ajout en tete : temps constant+ FILO : ordre d’entree conserve

- Appartenance lineaire- Concatenation lineaire



Notation : [a;b;. . .;k]⇔ a::b::. . .::[]


Listes

+ Ajout en tete : temps constant+ FILO : ordre d’entree conserve- Appartenance lineaire

- Concatenation lineaire



Notation : [a;b;. . .;k]⇔ a::b::. . .::[]


Listes

+ Ajout en tete : temps constant+ FILO : ordre d’entree conserve- Appartenance lineaire- Concatenation lineaire



Notation : [a;b;. . .;k]⇔ a::b::. . .::[]


Listes




Notation : [a;b;. . .;k]⇔ a::b::. . .::[]


Listes




Notation : [a;b;. . .;k]⇔ a::b::. . .::[]


Listes

iterateurs

map

Parcours de structure et construction de resultat portants sur lastructure

map : liste de resultat d’application de fonction sur les elementsmap f (a1::. . .::an::[])

; (f a1)::. . .::(f an)::[]

Type :

(α→ β)→ α list→ β list

Equation :

I ∀f, map f [] =[]

I Hyp : ∀f,map f l = v(f)∀e, ∀f,map f (e::l) =(f e)::v(f)


Listes iterateurs map


map : liste de resultat d’application de fonction sur les elements

map f (a1::. . .::an::[])

; (f a1)::. . .::(f an)::[]

Type :


Equation :

I ∀f, map f [] =[]





map : liste de resultat d’application de fonction sur les elementsmap f (a1::. . .::an::[])

; (f a1)::. . .::(f an)::[]Type :


Equation :

I ∀f, map f [] =[]





map : liste de resultat d’application de fonction sur les elementsmap f (a1::. . .::an::[]) ; (f a1)::. . .::(f an)::[]

Type :


Equation :

I ∀f, map f [] =[]





map : liste de resultat d’application de fonction sur les elementsmap f (a1::. . .::an::[]) ; (f a1)::. . .::(f an)::[]Type :


Equation :

I ∀f, map f [] =[]





map : liste de resultat d’application de fonction sur les elementsmap f (a1::. . .::an::[]) ; (f a1)::. . .::(f an)::[]Type : (α→ β)→ α list→ β list

Equation :

I ∀f, map f [] =[]






Equation :

I ∀f, map f [] =[]






Equation :I ∀f, map f [] =[]






Equation :I ∀f, map f [] =[]



Listes iterateurs fold


fold : composition d’application de fonction sur les elements

listes : deux sens possiblesI fold_left f acc(a1::. . .::an::[])

;

f(. . .(f acc a1). . .)an

Type :

(α→ β → α)→ α→ βlist→ α Terminal

I fold_right f (a1::. . .::an::[]) acc

;

f a1(. . .(f an acc). . .)

Type :

(α→ β → β)→ αlist→ β → β Non terminal





listes : deux sens possibles

I fold_left f acc(a1::. . .::an::[])

;

f(. . .(f acc a1). . .)an

Type :

(α→ β → α)→ α→ βlist→ α Terminal

I fold_right f (a1::. . .::an::[]) acc

;

f a1(. . .(f an acc). . .)

Type :






listes : deux sens possiblesI fold_left f acc(a1::. . .::an::[])

;

f(. . .(f acc a1). . .)an

Type :

(α→ β → α)→ α→ βlist→ α TerminalI fold_right f (a1::. . .::an::[]) acc

;

f a1(. . .(f an acc). . .)

Type :






listes : deux sens possiblesI fold_left f acc(a1::. . .::an::[]) ;

f(. . .(f acc a1). . .)anType :

(α→ β → α)→ α→ βlist→ α TerminalI fold_right f (a1::. . .::an::[]) acc ;

f a1(. . .(f an acc). . .)Type :







f(. . .(f acc a1). . .)anType : (α→ β → α)→ α→ βlist→ α

TerminalI fold_right f (a1::. . .::an::[]) acc ;

f a1(. . .(f an acc). . .)Type :







f(. . .(f acc a1). . .)anType : (α→ β → α)→ α→ βlist→ α

Terminal

I fold_right f (a1::. . .::an::[]) acc ;

f a1(. . .(f an acc). . .)Type : (α→ β → β)→ αlist→ β → β

Non terminal






f(. . .(f acc a1). . .)anType : (α→ β → α)→ α→ βlist→ α Terminal

I fold_right f (a1::. . .::an::[]) acc ;

f a1(. . .(f an acc). . .)Type : (α→ β → β)→ αlist→ β → β Non terminal


Zipper

Listes : ajout au milieu + persistance⇒ copies inutiles

Sol : avoir un point de vue local (cf. liste doublement chaınees)

type ’a zipper = {left : ’a list;pos : int; (* position courrante *)right : ’a list; } (* valeur courante dans right *)

Fonctions :leftmost, rightmost, is_empty : ’a zipper -> boolempty : ’a zipperinsert : ’a -> ’a zipper -> ’a zipper;

delete : ’a zipper -> ’a zipper; (*peut echouer *)go_left : ’a zipper -> ’a zipper; (*peut echouer *)go_right : ’a zipper -> ’a zipper; (*peut echouer *)get : ’a zipper -> ’a; (*peut echouer *)pos : ’a zipper -> int


Zipper

Listes : ajout au milieu + persistance⇒ copies inutilesSol : avoir un point de vue local (cf. liste doublement chaınees)





Zipper






Zipper



Fonctions :

leftmost, rightmost, is_empty : ’a zipper -> boolempty : ’a zipperinsert : ’a -> ’a zipper -> ’a zipper;



Zipper






Zipper




delete : ’a zipper -> ’a zipper; (*peut echouer *)go_left : ’a zipper -> ’a zipper; (*peut echouer *)go_right : ’a zipper -> ’a zipper; (*peut echouer *)get : ’a zipper -> ’a; (*peut echouer *)pos : ’a zipper -> intJulien Forest - ensiie - IPF 34/50

Arbres

: binaires polymorphes

e1 e2 . . . en

f2 . . .

. . .

type ’a arbre=| Empty| Node of (’a arbre*’a*’a arbre)

plus des fonctions de parcours, . . .


Arbres : binaires polymorphes

e1 e2 . . . en

f2 . . .

. . .





e1 e2 . . . en

f2 . . .

. . .

type ’a arbre=| Empty

| Node of (’a arbre*’a*’a arbre)




e1 e2 . . . en

f2 . . .

. . .





e1 e2 . . . en

f2 . . .

. . .




Arbres : n-aires

Nombres variables de fils.


(*Ne peut pas etre sous arbre d’un arbre non vide *)

| Node of ’a * (’a arbre list)

Plusieurs representations d’un meme arbre.

Contraindre la representation dans les commentaires. ⇒ fonctions deconstruction


Arbres : n-aires



(*Ne peut pas etre sous arbre d’un arbre non vide *)

| Node of ’a * (’a arbre list)




Arbres : n-aires


type ’a arbre=| Empty(*Ne peut pas etre sous arbre d’un arbre non vide *)| Node of ’a * (’a arbre list)


Contraindre la representation dans les commentaires.

⇒ fonctions deconstruction


Arbres : n-aires


type ’a arbre=| Empty(*Ne peut pas etre sous arbre d’un arbre non vide *)| Node of ’a * (’a arbre list)




Arbres : n-aires (2)


type ’a ne_arbre=| Node of ’a * (’a ne_arbre list)

type ’a arbre=| Empty| Ne of ’a ne_arbre


Arbres : specialises

Pour un type de donnees particulier.

type bexpr =| Val of bool| And of bexpr * bexpr| Or of bexpr * bexpr| Not of bexpr

let rec eval be =match be with| Val b -> b| And(b1,b2) ->let v1 = eval b1 in let v2 = eval b2 in v1 && v2

| Or(b1,b2) ->let v1 = eval b1 in let v2 = eval b2 in v1 || v2

| Not b -> let v = eval b in not v
















Constatation

Conflits de noms

Representation concrete polluante

Duplication

; Modules


Constatation

Conflits de noms

Representation concrete polluante

Duplication

; Modules


Modules Generalites

Gros code ; petites unites coherentes

: maintenance + reutilisation

Module = Corp(prive) + Interface(publique)Interface : com. avec exterieur (main, peau,yeux,. . . )Corp : fonctionnement du module (foie, poumons, rate, cerveau?)


Modules Generalites

Gros code ; petites unites coherentes : maintenance + reutilisation



Modules Generalites


Module = Corp(prive) + Interface(publique)

Interface : com. avec exterieur (main, peau,yeux,. . . )Corp : fonctionnement du module (foie, poumons, rate, cerveau?)


Modules Generalites


Module = Corp(prive) + Interface(publique)Interface : com. avec exterieur (main, peau,yeux,. . . )

Corp : fonctionnement du module (foie, poumons, rate, cerveau?)


Modules Generalites




Modules Generalites




Modules Generalites




Modules Principes

Interfacedeclaration/definition typesdeclaration de fonctions

CorpsDefinition typesDefinition fonctions

Interface :I Declaration des types (abstrait) et des fonctions a exporter.I Definition des types concrets a exporter.

Corps :I au moins types declares et/ou definis dans interfaceI au moins definitions fonctions declarees dans interfaces.


Modules Schema

interface

:typesprof. func.

corps

:def. typesdef. func.

M1

profil

interface

corpsprofil

M2

utilise


Modules Schema

interface :typesprof. func.

corps :def. typesdef. func.

M1

profil

interface

corpsprofil

M2

utilise


Modules Schema

interface

:typesprof. func.

corps


M1

profil

interface

corpsprofil

M2

utilise


Modules Schema

interface

:typesprof. func.

corps


M1

profil

interface

corpsprofil

M2

utilise


Modules Schema

interface

:typesprof. func.

corps


M1

profil

interface

corpsprofil

M2

utilise


Modules Fichiers

.mli = interface Informations publiques

.ml = implantation Cambouis

Compilation separee avec ocamlc -c (ou ocamlopt -c)D’abord .mli ; .cmiEnsuite .ml ; .cmo (ou .cmx) Verification de conformite

Utilisation : denomination par majusculeUn seul fichier a compiler : le fichier modifie (sauf si interface)


Ensembles

Structure dynamique

Fonctions :I Vide + test vacuiteI AjoutI AppartenanceI #,

⋃,⋂

I RetraitI . . .

Organisation : ordonner les ∈; savoir ou chercher


Ensembles

Structure dynamique


⋃,⋂

I RetraitI . . .



Ensembles

Structure dynamique


⋃,⋂

I RetraitI . . .



Ensembles

Structure dynamique


⋃,⋂

I RetraitI . . .



Ensembles

Structure dynamique


⋃,⋂

I RetraitI . . .



Ensembles profils

type int_set

val empty : int_set

val is_empty : int_set -> bool

val mem : int -> int_set -> bool

val cardinal : int_set -> int

val union : int_set -> int_set -> int_set

val inter : int_set -> int_set -> int_set

val remove : int -> int_set -> int_set


Ensembles Listes

I Facile a implanter

I Temps de recherche/insertion


Ensembles Listes




Ensembles Listes




Ensembles ABR

type int_set = Empty | Node (int_set*int*int_set)

r

< r >r

MAINTENIR L’INVARIANT?

Constructeur fute

I Recherche et construction ; max : profondeurI Reduire cout⇒ reduire profondeur (pour une autre fois).


Ensembles ABR


r

< r >r

MAINTENIR L’INVARIANT?

Constructeur fute



Ensembles ABR


r

< r >r

MAINTENIR L’INVARIANT? Constructeur fute



Ensembles ABR


r

< r >r


I Recherche et construction ; max : profondeur

I Reduire cout⇒ reduire profondeur (pour une autre fois).


Ensembles ABR


r

< r >r




Ensembles ABR

Subtilites :I Ajout/recherche : on compare la valeur a la racine et on part du

bon cote

I Retrait idee :1. rechercher la valeur a retirer2. retirer min sous-arbre droit3. mettre min sous-arbre droit a la racine locale


ABR : Retrait

de 12

: le slide secret

10

9 12

11 18

15

13

14

Recherche valeurRecherche min sous arbre droitremplacement


ABR : Retrait de 12 : le slide secret

10

9 12

11 18

15

13

14

Recherche valeur

Recherche min sous arbre droitremplacement



10

9 12

11 18

15

13

14

Recherche valeur




10

9 12

11 18

15

13

14

Recherche valeur

Recherche min sous arbre droit

remplacement



10

9 12

11 18

15

13

14

Recherche valeur


remplacement



10

9 12

11 18

15

13

14

Recherche valeur


remplacement



10

9 13

11 18

15

14

Recherche valeur



Ensembles ABR

I Moins facile a implanter

I Temps de recherche/insertion meilleurs (parfois)

I Tests generiques : toujours pas de solution


Ensembles ABR





Ensembles ABR





Ensembles ABR





Documents

Programmation fonctionnelleweb4.ensiie.fr/~stefania.dumbrava/IPF/cours.pdf · Programmation fonctionnelle Julien Forest - ensiie - IPF 1/50. Fonctionnement du cours Regles de vie