Remarques: Sur cette page, j'ai place l'integralite de mes TP et TD de
CAML. Cependant, je n'ai jamais note grand chose en travaillant sur machine
aussi les listings de programme sont absents de cette page.
J'ai place entre (*** ***) mes eventuelles remarques.
TD et TP
CAML
Deux fenêtres : -information sur l'exécution
du programme
-d'écriture
*Entrée -> valider
Entr -> passer à la ligne
Premier pas
I - Expression
Exemples:
type valeur
arithmétique et logique
2+2;; int = 4
2=9;; bool = false
(2<3)&(2>1);; bool = true
"ceci est une chaîne";; string = "ceci est une chaîne"
&: et logique
2.+.2.;; float = 4.0
fonctions et applications de fonction
function x -> x+1;;
function y -> y*3;;
(function x -> x+1)(5);; -:int = 6
Opérateurs:
Ils dépendent du domaine d'application
Pour les entiers: + - * / mod
Pour les réels, ajouter un point
comparaison : < >
logiques : or not &
chaînes : ^ (mise bout à bout de deux chaînes)
II - Définitions globales
let identificateur = expression;;
Exemple:
let s = 2+2;;
let u = 3>4;;
s;;
s*2;;
s>4;;
s*t;;
let t = s*4;;
s*t;;
let f = function x -> x+1;;
f;;
f(3);;
let g(y) = y*.3.;;
g;;
g(2);;
TD Informatique:
Fonction et application d'une fonction
. Les fonctions (objets abstraits) résolvent des problèmes.
Ces fonctions sont manipulées comme des valeurs numériques.
. Fonction /= application de cette fonction à des valeurs.
Exemple: Ent :R -> N
x -> [x] {partie entière}
x -> Ent(x)
Il ne faut pas confondre ent (abstraite) et ent(x) (valeur donnée).
. Le type précise les ensembles des objets manipulés
Exemple:
Type de ent en CAML : float -> int
algo : num -> num
Type de ent(x) en CAML : int
algo : num
. Application
type de
1) Somme_carré qui calcule la somme des carrés de deux valeurs
(num,num) -> num
(float*float) -> float
2)division entière qui détermine le quotient et le reste
d'une division
entière
(a,b) -> (q,r) définit par a = bq+r
(num,num) -> (num,num)
(int*int) -> (int*int)
. Les fonctions peuvent être paramètres de fonctions
Exemple: Rond:(f,g) -> g o f
(f,g) -> rond (f,g)
((A->B)*(B->C)) -> (A->C)
Type : ((alpha->beta)*(beta->gamma)) -> (alpha -> gamma)
Si A=B=C=R alors: ((num->num),(num->num))->(num,num)
((float->float)*(float->float))->(float,float)
. Application
types de
1) Somme
(x,y) -> x+y
R*R -> R
(num,num) -> num
(float*float) -> float
2) Carré
x -> x2
R -> R
num -> num
float -> float
3) Somme (3,4)
num -> num
4) carré (2)
2 -> carré (2)
num
5) rond (somme,carré)
(R*R->R)*(R->R)->(R*R->R)
Type de rond (s,c) : (num,num) -> num
6) rond (carré,somme)
carré: A -> B où A=B=R
somme: B -> C où B=R*R et C=R
C'est impossible, cette expression est mal formatée.
Le typage est un moyen de déceler les erreurs.
7) rond (somme,carré)(3,4)
(3,4) -> somme (3,4) -> carré (somme (3,4))
R*R -> R -> R
type : num
. Trouver des exemples illustrant chacun des types suivants:
1) (num->num)->(num->num)
Exemple f -> 3+f
f -> f'
2) num -> (num->num)
G(x) = (y->x+y)
G(5):y->5+y
*G(5) EST UNE FONCTION
3) (num,num) -> num
(x,y) -> J(x,y)=x+y
4) (num->num)->num
f -> K(f)
. Typage à partir d'un algorithme
Exemple : f(x,y)=y si x
-y sinon
Tx=bool car "si'
Ty=num car "-"
Tf(x,y)=num
Tf=(bool,num)->num
En CAML:
let f=function (x-> if x then y
else -y);;
1) f(x)=x+3 < 2*x
Tx=num
Tf(x)=bool car "<"
Tf=num->bool
2) f(x,y)=x(y+1) ou x(y-1)
Ty=num
Tf(x,y)=bool
Tx(y+1)=bool
Tx=num->bool
Tf=(num->bool,num)->bool
3) f(x,y)=x(y)
Ty=alpha
Tx=alpha->beta
Tf=(alpha->beta,alpha)->beta
4) f(x,y,z)=z(x) et y
Ty=bool <- et
Tz(x)=bool <- et
Tf(x,y,z)=bool <- et
Tx=alpha
Tz=alpha->bool
Tf=(alpha,bool,alpha->bool)->bool
5) f(x,y)=y si x(y)
faux sinon
Ty=bool <- faux
Tx(y)=bool <- si
Tf(x,y)=bool
Tx=bool->bool
Tf=(bool->bool,bool)->bool
6) f(x)=x et (x<10)
Tx=num <- <
or Tx=bool <- et
donc expression mal typée
. Ecrire les algorithmes et les types donnant:
1) L'aire d'une couronne
aire x y = Pi * (x2-y2) si x>y
Pi * (y2-x2) sinon
sachant que Pi = 3,14
Tx:num
Ty:num
Tf(x,y):num
Tf:(num,num)->num
2) Valeur intermédiaire entre trois valeurs saisies
valint (a,b,c) = a si (c<=a et a<=b)
= c si (c<=b et a<=b)
= b si (a<=b)
= b si (a>=b et b>=c)
= c si (a>=b et a>=c)
= a sinon
Type : (num,num,num)->num
Traduction en CAML
let interm (a,b,c)=if (c<=a&a<=b)
then a
else
if (c<=b&a<=b)
then c
else
if a<=b
then b
else
if (a>=b & b>=c)
then b
else
if (a>=b & a>=c)
then c
else a;;
. Résolution d'une équation de second degré
eq(a,b,c) = ("Pas de solution,0,0) si D<0
= ("1 solution",-b/2a,-b/2a) si D=0
= ("2 solutions", (-b-racine D)/2a,(-b+racine D)/2a) sinon
sachant que D=b2-4*a*c
*** racine D est bien évidemment la racine carré du discriminant
***
ou encore
eq(a,b,c) = "pas de solution" si D<0
= "une solution"^chaîne_de_num (-b/2a) si D=0
= "deux solutions"^chaîne_de_num (-b-racine D/2a)^chaîne_de_num
(-b+racine D/2a)
sachant que D=b2-4*a*c
En CAML, conversion d'un nombre réel en chaîne:string-of-float.
C'est un efonction de type float->string
. Fonction qui détermine sous la forme usuelle un âge à
partir d'une date de naissance et d'une date courante.
Hypothèse : on donne la date de naissance, on suppose que l'année
courante est postérieure à l'année de naissance et
les dates sont correctes.
Date de la forme (j,m,a)
Type ((num,num,num),(num,num,num)) -> num
Age ((jc,mc,ac),(jn,mn,an))=an-ac si mc>mn
=an-ac si (mc=mn et jc>jn)
=an-ac-1 sinon
. Remarques:déclarations locales
En algo avec sachant que...
En CAML avec let...in...
exemple:
let add(a,c)=let b=(a+c) in a+b;;
. Premières fonctions
Rappel
fact(n) = 1 si n=0 {cas d'arrêt}
= n * fact (n-1) {cas général}
Le raisonnement récursif est utilisé pour résoudre
un problème P sur un domaine D à partir du même problème
P sur un domaine D' plus petit. Ceci entraine un appel récursif.
Ce processus s'arrêtera s'il y a au moins un cas pour lequel la résolution
du problème est direct.
-> Cas de base ou cas d'arrêt.
fact (4)=n*fact(3)
24 = n*fact(2)
6 = n*fact(1)
2 = n*fact(0) {cas d'arrêt}
=1
. Exercices
a/ Somme des n premiers carrés définis pour n>=0
ex: 1+4+9+...+n2
somme (n)=0 si n=0
=(n*n)+ somme (n-1) sinon
b/ x^r pour n>=0
puis (x,n) = 1 si n=0
= puis (x,n-1) * x sinon
Type: (num,num) -> num
Autre méthode: pour n paire, x^n=(x*x)^n/2
puisrap (x,n) = 1 si n=0
= puisrap (x*x,n/2) si n mod 2=0
= x*puisrap (x,n-1) sinon
avec puisrap(3,17)=3*puisrap(3,16)
=puisrap(9,8)
=puisrap(81,4)
=puisrap(81^2,2)
=puisrap(81^4,1)
=81^4*puisrap(81^4,0)
=1
avec puisrap(3,13)=3*puisrap(3,12)
=puisrap(9,6)
=puisrap(81,3)
=81*puisrap(81,2)
=puisrap(81^2,1)
=81^2*puisrap(81^2,0)
=1
. Calcul du quotient et du reste d'une division entière par soustractions
successives:
a/Fonction quotient
quot (x,y) = 0 si x <y
=
1+quotient (x-y,y)
type quot: (num,num) -> num
b/Fonction reste
reste (x,y)=x si x < y
=reste
(x-y,y) sinon
type reste:(num,num) -> num
c/Fonction quot_reste
Type: (num,num) -> (num,num)
quot_reste(x,y)=(0,x) si x<y
=(1+premier
c,second c) sinon
sachant que c=quot_reste (x-y,y)
On suppose connu les fonctions :
premier (a,b) = a
second (a,b) = b
respectivement traduites en CAML par fst et snd
. Fonction de calcul: x^0+x^1+...+x^n
a/ En utilisant puisrap
A(x,n) = 1 si n=0
= puis_rap(x,n)+A(x,n-1) sinon
b/ En utilisant l'algo de Horner (1+x(x^0+...+x^n-1)
Horner (x,n) = 1 si n=0
= 1 + x*(Horner(x,n-1)) sinon
Jeu d'essai avec (2,3)
Horner (2,3) = 1 + 2*(Horner(2,2))
= 1 + 2*(Horner (2,1))
= 1 + 2*Horner (2,0)
=1
. Traitement récursif des chaînes de caractères:
On suppose connues les fonctions
* longueur : chaîne -> num
longueur (ch) = nombre de caractères de ch
* neme_car : (chaîne,num) -> car
neme_car (ch,n) = le caractère nunméro n de ch
* sous_chaîne : (chaîne,num,num) -> chaîne
sous_chaîne (ch,d,l) = la sous-chaîne prise dans ch, qui commence
au caractère numéro d de ch et qui a pour longueur l.
. Fonction déterminant si une chaîne est un palindrome
exemple : "ESOPE RESTE ICI ET SE REPOSE"
"LAVAL"
type : chaîne -> bool
palin ("ch")= vrai si L=1 ou L=0
= palin (sous_chaîne (ch,2,L-2)) si neme_car (ch,1) = neme_car (ch,L)
= faux sinon
sachant que L=longueur (ch)
avec LOVAL:
palin("LOVAL")=palin("OVA")
=Faux
avec LAVAL:
palin("LAVAL")=palin("AVA")
=palin("V")
=Vrai
. Fonction déterminant le nombre d'occurences d'un caractère
donné dans une chaîne donnée
Type (chaine,car) -> num
occur (ch,n) = 0 si l=0
= 1 + occur ((sous-chaîne (ch,2,l-1),n) si neme_car (ch,1)=n
= 0 + occur ((sous-chaîne (ch,2,l-1),n) si neme_car (ch,1)=n
sachant que l=longueur (ch)
. TP CAML
Les fonctions récursives doivent comporter rec
ex: let rec f...
*trace correspond à un jeu d'essai. Untrace annule l'effet précédent.
ex: trace "prod";; où prod est une fonction
Fonctions de traitement de chaînes de caractères
ALGO
nom type
longueur chaîne->num
neme_car (chaîne,num)->car
sous_chaîne (chaîne,num,num)->chaîne
Fonctions où on a pour paramètres un couple, triplet... sont
dites non
currifiées
-> Parenthèses et virgules
CAML
nom type
string_lenght string->int
nth_char string->int->char
sub_string string->int->int->string
Attention, la numérotation des caractères commence à
0
Fonctions où on a plusieurs paramètres isolés sont
dites currifiées.
-> Ni parenthèse ni virgules
Remarques: noter la différence de type entre fonctions currifiées
et non currifiées.
&: et logique
or: ou logique
and: sépare deux déclarations locales de même niveau.
ex: let def1=exp1 and def2=exp2 in...
Rappel:
Une constante de type chaîne est entre " "
Une constante de type caractère est entre ` ` {obtenu avec AltGr+7}
. Nouvelle version de palindrome
Dans celle-ci, on considère possible que l'utilisateur entre des
"blancs" dans sa chaîne.
palin (ch) = Vrai si l<=1
= palin(sous_chaîne(ch,2,l-2)) si neme_car(ch,1)=neme_car(ch,l)
= palin(sous_chaîne(ch,2,l-1)) si neme_car(ch,1)=` `
= palin(sous_chaîne(ch,1,l-1)) si neme_car(ch,l)=` `
= faux sinon
sachant que l=longueur(ch)
. Fonction qui détermine si une chaîne est incluse dans une
autre
Type : (chaîne,chaîne) -> booléen
incluse (ch1,ch2) = Faux si l>m
= Vrai si ch2=sous_chaîne(ch1,1,l)
= incluse (sous_chaîne (ch1,2,m-1),ch2) sinon
sachant que l=longueur (ch2)
m=longueur (ch1)
. Fonction qui détermine le rang d'une chaîne dans une autre
type: (chaîne,chaîne) -> num
rg (ch1,ch2) = -1 si non incluse (ch1,ch2)
= pos (ch1,ch2) sinon
sachant que pos (x,y)= 1 si sous_chaîne (y,1,l1)=x
= 1+pos (x,sous_chaîne (y,2,l2-1) sinon
sachant que l1=longueur x
l2=longueur y
en CAML:
let rang (ch1,ch2)=if incluse (ch1,ch2)=false
then -1
else let rec pos (x,y)
=l1=lenght_string x
and l2=lenght_string y
in if sub_string y 0 l1=x
then 1
else 1+pos (x,sub_string y 1 (l2-1))
in pos (ch1,ch2);;
. Fonction calculant le nombre d'occurences d'une chaîne dans l'autre
occ (ch1,ch2) = 0 si l2>l1
= 1 + occ (sous_chaîne(ch1,l2+1,l1-l2),ch2) si sous_chaîne
(ch1,1,l2) = ch2
= occ (sous_chaîne (ch1,2,l1-1),ch2) sinon
. Filtres et listes
1) Notion de filtre (ou filtrage)
NB: La notion de filtre est utilisée pour le traitement des listes
mais elle n'est pas réservé aux listes.
Les filtres sont les différentes formes des paramètres intervenant
dans la définition d'une fonction.*
ex: ne concernant pas les listes
ou exclusif type (bool,bool) -> bool
Rappel : table de vérité
ou inclusif
_________________
| A | B |A
ou B|
----------------------
| Faux | Faux | Faux |
----------------------
| Faux | Vrai | Vrai |
----------------------
| Vrai | Faux |Vrai |
----------------------
| Vrai | Vrai | Vrai |
----------------------
ou exclusif
_________________
| A | B |A
et B|
----------------------
| Faux | Faux | Faux |
----------------------
| Faux | Vra i | Vrai |
----------------------
| Vrai | Faux | Vrai |
----------------------
| Vrai | Vrai | Faux |
----------------------
ou_excl (A,B) = vrai si A=vrai et B=faux
= vrai si B=vrai et A=faux
= faux sinon
Toutes les formes doivent être envisagées. L'ordre est important.
2) Traitement de listes par filtrage
En général: 2 formes possibles pour un paramètre de
type liste:
- liste vide []
- liste non vide x::xs
Si x::xs est de type [alpha] alors x est de type alpha et xs de type [alpha]
exemple: tête type : [alpha] -> alpha
tête [] = T inversé
tête x::xs=x
Jeux d'essai
i) avec L=[1;2;3;5]
Type L [num]
tête L=1 de type num
ii) avec L=[[1;2];[3;5;7];[1;3]]
Type L = [[num]]
ici alpha = [num]
tête L= [1;2] de type [num]
. Fonction queue qui fournit la liste privée de son premier élément
Type : [alpha] -> [alpha]
queue [] = T inversé
queue x::xs=xs
. Fonction qui détermine si un élément appartient
à une liste
Type: ([alpha],alpha) -> bool
appart (a,[])=faux
(a,x::xs)=vrai si a=x
=appart (a,xs) sinon
. Fonction qui calcule le nombre d'éléments d'une liste
Type : [alpha] -> num
longueur ([]) = 0
longueur x::xs= 1+longueur (xs)
. Fonction qui concatène deux listes
Type: ([alpha],[alpha]) -> [alpha]
concatene ([],L)=L
concatene ((x::xs),L)=x::concatene (xs,L)
. Rappel:
L1@L2=L3 => type L1=type L2=type L3=[alpha]
x::xs=L => type L=type xs=[alpha] et type x=alpha
x::[]=[x]
x@[]=[x]
[[]]/=[]
[] de type [alpha]
. Exercices : Vrai, faux ? Justifier
1) x::[]@[y;z]=[x;y;z]
Soit alpha le type de x.
x::[]=[x] de type [alpha]
D'après les propriétés d'@: type [x]=type [y;z]=type
[x;y;z]
donc type x=type y= type z=alpha
La concaténation met bout à bout les éléments
de la première liste (ici x) et de la deuxième liste (ici
y et z).
On a bien [x]@[y;z]=[x;y;z]
2) [7;11;15]::[]=[7;11;15]
x::[]=[x]
ici, x=[7;11;15] donc x::[]=[[7;11;15]]
L'affirmation est par suite fausse.
3) xs::[]=xs
Faux car xs::[]=[xs]
4) xs@ys=[xs::ys]
Faux, car dans la partie de gauche, l'opérateur @ implique que xs
et ys soient de même type alors que dans la partie de droite, ::
prouve qu'ils sont de types différents. Il y a donc contradiction.
5) [[]]@xs=[xs]
On sait que L1@L2=L3 => type L1=type L2=type L3
Appliquée à notre exemple, cette propriété
affirme que type xs=type [xs] ce qui est faux
6) [xs]@[]=[xs]
Vrai car on n'ajoute aucun élément.
7) xs::[]=[xs]
Vrai, c'est une des propriétés
8) (x::xs)@[ys]=x::(xs@ys)
Pour simplifier la démonstration on va l'écrire sous la forme:
On pose type x=alpha
Dans la partie de gauche, on en déduit que:
type xs=[alpha]
et que type xs=type [ys]=[alpha] car présence de @
alors, type ys=alpha
On a donc type xs/=type ys
Or, à droite, xs@ys impose que type xs=type ys.
L'égalité initiale est donc fausse.
. Exercices:
1)Fonction qui retire les n premiers éléments d'une liste.
Le résultat est donc la liste privée de ses n premiers éléments.
Exemple : 3 et [1;2;3;4;5] -> [4;5]
Type : (num,[alpha]) -> [alpha]
retirer (0,L)=L
retirer (n,[])=T inversé
retirer (n,x::xs)=retirer ((n-1),xs)
2)Fonction qui donne les n premiers éléments d'une liste
exemple : 3 et [1;2;3;4;5] -> [1;2;3]
type: (num,[alpha]) -> [alpha]
elem (0,L) = []
elem (n,[]) = T inversé
elem (n,x::xs)=x::elem (n-1,xs)
3)Fonction coupler
exemple: ([1;2;3],[5;6;7]) -> [(1,5);(2,6);(3,7)]
Type : ([alpha],[beta]) -> [(alpha,beta)]
coupler (x::xs,y::ys)=(x,y)::coupler(xs,ys)
coupler (-,-)=[]
4)Fonction decoupler
Type [(alpha,beta)] -> ([alpha],[beta])
decoupler [] = ([],[])
decoupler (x,y)::l=(x::premier(c),y::second(c))
sachant que c=decoupler (l)
5)Fonction renverser
exemple : renverser [1;2;3]=[3;2;1]
Type : [alpha] -> [alpha]
renverser []=[]
renverser x::xs=(renverser xs)@[x]
6) Dernier
dernier [1;2;3]=3
type : [alpha] -> alpha
dernier [] = T inversé
dernier [x]=x
dernier (x::xs)=dernier (xs)
7) sauf_dernier
exemple : sauf_dernier [1;2;3]=[1;2]
sauf_dernier [] = T inversé
sauf_dernier [x] = []
sauf_dernier (x::xs) = x::sauf_dernier (xs)
. Redéfinir appliquer (qui applique une fonction à chaque
éléments de la liste).
Type ((alpha->beta),[alpha]) -> [beta]
appliquer (_,[]) = []
appliquer (f,x::xs)=f(x)::(appliquer (f,xs))
exemples d'utilisation:
i) carré x =x*x
l=[1;2;3]
appliquer (carré,l) = [1;4;9]
ii) carré_liste l = appliquer (carré,l)
sachant que appliquer (_,[])=[]
(x,y::ys)=x(y)::appliquer (x,ys)
et carré x = x*x
iii) liste_carré ([]) = []
(x::xs)=carré x::carré_liste (xs)
sachant que carré x=x*x
. Problème: Ajout d'un mêmme terme à tous les termes
d'une liste en utilisant appliquer.
exemple : ajout_liste (3,[1;2;3])=[4;5;6]
Appliquer : (alpha->beta,[alpha])->[beta]
Ajout_liste (n,l) = appliquer (plusf n,l)
plusf x y = x+y fonction currifiée de type num -> num -> num
NB: Une fonction currifiée permet de définir des fonctions
partielles en fixant certains des paramètres.
exemple : plusf n est une fonction de type num -> num.
Appliquer (plusf 3,[1;2;3]) = [plusf 3 1;plusf 3 2;plusf 3 3]
= [4;5;6]
. Polynômes creux (ayant beaucoupe de coefficients nuls)
-> une bonne représentation : liste de couples (coef,degré)
exemple: x^3-8x^9 -> [(1,3),(-8,9)]
1) Calcul de la valeur d'un tel polynôme pour x donné
a/ Calcul de la valeur d'un monome pour x donné
mono x (a,b) = a*puis (x,b)
sachant que puis (y,z) = 1 si z=0
= y*puis(y,z-1) sinon
Type num -> (num,num) -> num
TP
Filtrage en CAML
.Filtrage implicite:
exemple :
let ou_exclusif = function
(true,false) -> true
|(false,true) -> true
|(_,_) -> false;;
remarque: T inversé -> failwith "message"
Version en filtrage implicite de la fonction longueur:
let rec longueur = function
[] -> 0
|x::xs -> 1+longueur (xs);;
. En CAML, une fonction map est prédéfinie, c'est la version
currifiée d'appliquer
Rappel: version non currifiée de appliquer
Type ((alpha->beta),[alpha]) -> [beta]
appliquer (_,[]) = []
(f,x::xs)=f(x)::appliquer (f,xs)
En version currifiée:
Type (alpha->beta)->[alpha]->[beta]
appliquer _ [] = []
f x::xs=f(x)::appliquer f xs
Traduction CAML de appliquer
a/ filtrage explicite
let rec appliquer f l =
match l with
[] -> []
|x::xs->f(x)::appliquer f xs;;
b/ filtrage implicite
let rec appliquer =
function f -> (function [] -> []
|x::xs->f(x)::appliquer f xs);;