Remarques : Vous trouverez ici tous les cours d'informatique du second semestre a l'exception de ceux des deux dernières semaines.
Informatique
Le langage CAML est un dérivé du langage LISP.
La Programmation fonctionnelle
Plan:
Chp 1 - Les concepts fondamentaux
Chp 2 - Les fonctions
Chp 3 - Les types fondamentaux
Chp 4 - Les listes
Chp 5 - Récursivité, récurrence
Chp 1 - Les concepts fondamentaux
I - La programmation fonctionnelle
1) Les modes de l'impératif et du fonctionnel
Les langages impératifs sont fondés sur la notion d'ETAT de la machine (mémoire centrale et périphériques).
- Ecrire un programme dans un langage impératif
Décrire la suite des états par lesquels la machine doit passer, en partant d'un état initial jusqu'à un état final, de telle sorte que l'exécution du programme favorise les résultats recherchés.
=> On explique comment le réaliser.
- Exemple : Algo impératif et Pascal
Les langages fonctionnels sont fondés sur la notion de fonction.
=> Ecrire un programme dans un langage fonctionnel
Décrire une fonction qui, appliquée à des arguments, renvoie le résultat recherché.
- Exemple : Algo fonctionnelle et CAML
Remarque : Il n'y a pas de barrières infranchissables entre "impératif" et "fonctionnel"
- "Impératif" avec "fonctions" est proche du "fonctionnelle".
- "fonctionnelle" a besoin de l'affectation.
2) Principe de base
Programmer dans un langage fonctionnel consiste :
- à construire des définitions
- à utiliser la machine pour évaluer des expressions
=> 2 acteurs : le programmateur et la machine
Rôle fondamental de chaque acteur
a) Le programmeur
Construction d'une fonction résolvant un problème donné. Ce travail engendre en général un certain nombre de fonction subsidiaires.
Ce travail va être exprimé dans une notion qui obéira aux principes mathématiques usuels.
b) La machine
. Doit agir comme un évaluateur ou calculateur
. Elle doit évaluer (ou calculer) des expressions et afficher des résultats trouvés
. Ce calculateur fonctionnel évalue les expressions qui contiennent des occurences de noms de fonctions (définies par le programmeur) en utilisant comme règles de réduction (ou de simplification) les définitions posées afin de les transformer au format affichable.
II - Session et script
1) La programmation fonctionnelle en mode interactif
Elle va commencer par évaluer l'idée d'utilisation d'un emachine comme calculateur fonctionnel en mode interactif. a) Affichage d'un signal d'invite (ou prompt)
La machine indique qu'elle est prête à évaluer une expression en affichant un signal d'invite.
Nous conviendrons par convention qu'il s'agit de ?
b) Evaluation d'une expression en mode interactif
On entre au clavier une expression. On la transmet à l'évaluateur en la faisant suivre d'"Enter". Le calculateur répond en affichant le résultat de l'évaluation de l'expression. Le calculateur réaffiche un nouveau signe d'invite à un enouvelle expression.
- Remarques : Pour certains langages, l'expression doit se terminer par certains signes. Ainsi en CAML, on doit la faire suivre par;;
2) Notion de session
Définition : On appelle session une séquence d'interaction entre le programmeur et le calculateur.
Exemple de session:
?49 <- cas le plus simple. Pas d'évaluation à faire
49
?6*7 <- La simplification se fait en effectuant la multiplication
42
? (7*9) +(2*5) <- La simplification se fait en effectuant la * puis l'+
73
Remarques : Les règles d'évaluation des expressions seront détaillées au chap 3.
III - La notion d'environnement ou programme fonctionnel
Pour l'instant, une session est simple :on évalue seulement des expressions. Il serait plus intéressant de disposer d'un moyen permettant de NOMMER des VALEURS afin de pouvoir les utiliser ensuite.
1) Définition et liaison
- Définition : On appelle définition la construction qui permet de nommer une valeur.
Convention : le nommage des valeurs va se faire en utilisant = (au sens d'équation)
définition : dudule = 7
Un identificateur sert à désigner une valeur. La valeur est dite liée à l'identificateur par la définition posée : identificateur = expression
Le couple (identificateur / valeur) est appelé une liaison.
Exemple:
u = 5
v = 2 + 1 + 7
2) Environnement
On appelle environnement (ou contexte ou script) un ensemble de définitions (c.a.d des liaisons).
Exemple de script simple : x = 1
identificateur y = 2 valeur
L'environnement est caractérisé par les deux liaisons :
- l'identificateur x est lié à 1 et <- (x,1)
- l'identificateur y est lié à 2 et <- (y,2)
Exemple de script :
identificateur | argument | définition | expressions | conditions
carré x = x*x
min x,y = x si x < y
= y si x>y
Dans ce script, deux fonctions identifiées par "carré" et "min" ont été définies :
- La fonction "carré" prend la valeur de x comme argument et renvoie la valeur x*x.
- La fonction "min" prend comme argument x et y et renvoie la valeur minimum.
Remarque: On ne s'intéresse pas encore ici à la syntaxe correcte des définitions. Notons toutefois qu'elles sont écrites comme étant des équations entre certains types d'expressions.
Un script ayant été créé, on peut le soumettre au calculateur et donc entrer une session.
Exemple : ayant défini l'environnement précédent:
? carré (3+4)
49
? min 5 7
5
? carré (min 8 11)
64
?
Remarque: Dans l'environnement: ? t-t erreur car l'identificateur t n'est pas lié à une valeur.
3) Portée d'un identificateur
Principe fondamental en algo fonctionnel. La portée d'un identificateur est la durée de validité de la liaison qui lui est associée.
Exemple:
année = 1995 liaisons
(année,1995)
année future = année + 1 (année future,196)
? année future
1996
année = 0 (année,0) <- année est liée à zéro
? année + 5
5
? année future <- La valeur liée à "année future" n'est pas modifiée,
1996 car dans sa définition, il y a eu remplacement textuel de
"année". Mais (année,1995) n'est plus accessible. Désormais
"année" est liée à "0".
Environnement=[(année,0),(année future,1996),(année,1995),Env]
-Définition :
. Le script soumis à l'évaluateur définit l'environnement global de la session qui l'utilise.
. Les liaisons que crée le script sont appelées des liaisons globales.
Remarque fondamentale: Une déclaration globale n'est pas modifiable.
-> Elle reste valide pendant toute la session
-> Si on veut changer la valeur liée à l'identificateur dans l'environnement global, on doit obligatoirement définir une nouvelle liaison globale qui sera désormais seule accessible.
-> Les déclarations utilisant l'ancienne liaison ne sont pas affectées.
4) CAML et les sessions
a) Le script des définitions globales
obligatoire
let i arg = expressions;;
=soit
*facultatif
->forme plus ou moins complexe
b) La session en CAML # let x=5;
# x:int=5 : dont le type est
# x;;
_ : int = 5
# (La foncton carré : x->x*x avec x entier)
# let carré x = x*x;; * = multiplication des entiers
# carré:int -> int = < fun >
# carré x;;
_ : int = 25
# let min x y = if x<=y then x
else y;;
_ : int = 25
#carré (-5);;
#min : int -> int -> int = < fun >
#carré (min 2 4);;
_ : int = 4
#
IV - L'analyse des expressions
1) La réduction
- Définition : On appelle réduction (ou simplification ou évaluation), le processus utilisé par la machine pour évaluer une expressions, en la réduisant à la forme équivalente la plus simple et pour afficher ensuite sa valeur.
convention : => signifie "réduit à"
Exemple : Règle de simplification
i) carré (5+7) => carré 12 (+)
=> 12*12 (carré)
=> 144 (*)
ii) carré (5+7) => (5+7)*(5+7) (carré)
=> 12 * (5+7) (+)
=> 12 * 12 (+)
=> 144 (*)
L'évaluation de l'expression est faite par un processus simple de substitution et de simplification, utilisant à la fois:
- des règles prédéfinies (des primitives), et
- des règles édictées par le programme sous forme de définitions.
- Définition : . Une expression est dite sous forme canonique normale si elle ne peut plus être réduite.
. Une valeur affichable comme étant sa représentation canonique normale.
Remarque: Les termes valeurs n'ont pas de forme canonique normale. Par exemple, la valeur Pi.
- Le symbole du T inversé
(***il n'existe pas dans le jeu de caractère ISO-8859 du HTML. A moins d'insérer une image en plein milieu du texte (ce qui serait peu judicieux), il n'y a pas moyen de vous le représenter***)
Certaines expressions n'ont pas la possibilité d'être réduites : 1/0
Suivant le langage arithmétique choisi, l'évaluateur voit sortir un message d'erreur ou "se" lancer dans un processus infin de calculs.
Convention: On peut introduire le symbole du T inversé représentant une valeur indéfinie.
=> Il n'y aura pas d'exception. Ainsi 1/0= T inversé
2) L'univers des types
L'univers des valeurs est partitionné en ensembles organisés appelés des types de valeur.
Deux catégories:
i)Les types de base (ou prédéfinis)
Les valeurs d'un type de base sont dérivables et les opérations possibles de ce type sont précisées.
- Le type num désignant les nombres
- Le type bool désignant les valeurs dérivables
- Le type car désignant les caractères
- Le type chaîne désignant les chaînes de caractères
Remarque : En CAML, on distingue les entiers (type int) des réels (type float). CAML distingue alors les opérations de ces deux types (exemple: + pour int et +. pour float).
ii) Les types construits (ou composés)
Leurs valeurs sont construites à partir de type déjà défini
exemple :
a) (num,car) paires dont la première valeur est un nombre et la deuxième un caractère.
b) (num -> num) f numérique
c) [car] liste de caractères
Remarque : A chacun de ces types, il faudra associer un certain nombre d'opérations.
3) Le principe du typage fort
Définition: Une expression est bien formée si on peut lui assigner un type qui se déduit uniquement de ces constituants. Dans le cas contraire, l'expression est mal formée.
Exemple : Considérons le script
valeur x = 'A'
forme x = x + valeur
avec x de type num, valeur de type car et + impliquant une addition num
=> L'expression (x+valeur x) est mal formée
=> Le script est rejeté
4) Les deux niveaux d'analyse d'une expression
Il y a deux niveaux d'analyse lorsque un eexpression est soumise à l'évaluation:
i) L'analyse syntaxique:
L'évaluateur vérifie que l'expression satisfait les lois de définition d'une expression.
- si oui, on passe au niveau 2
- si non, une erreur de syntaxe est signalée
ii) L'analyse de type
L'évaluateur vérifie que l'expression possède un type.
- si non, une erreur est signalée
- si oui, le processus d'évaluation commence
5) Les deux niveaux d'analyse d'un script
Même démarche jusqu'en ii). Dans ce cas et seulement, le script est accepté.
Exemple en CAML:
#let carré x = x * x;;
#carré : int -> int = < fun >
#carré (-2);;
_ : int = 4
#carré -5;;
>erreur
>expression of type int -> int
#21+5.2;;
>erreur
>expression of type float
>cannot be used with type int
#
V - Spécification et implémentation
Définition :
a) Une spécification est une description du travail que le programme doit accomplir.
b) Une implémentation est un algo qui réalise la spécification.
=> Elles sont différentes par nature et servent des objectifs différents.
a) Spécification=expression des intentions du programmateur
Objectif = expression claire et succinte
b) Implémentation=expression pour l'exécution par la machine
Objectif = expression efficace afin que le programme s'exécute dans le temps et l'espace disponible.
Exemple : la fonction "plus_que_carré"
*Une spécification de plus_que_carré:num -> num peut-être : Pour tout x>=0, plus_que_carré x > carré x
*Une implémentation peut-être : plus_que_carré x = carré (x+1)
2 aspects : . Elle est valide dans notre notation si on connaît la définition de carré x
. Elle satisfait la spécification:
plus_que_carré x = carré (x+1) = (x+1)(x+1)
= x*x + 2*x+1
> x*x
> carré x
Remarque: La spécification n'est pas en général unique. On peut citer deux méthodes permettant de vérifier que des définitions satisfont les spécifications.
a- Poser la définition puis vérifier que les conditions sont requises (exemple précédent)
b- Développer systématiquement la définition
-> comme x+1>x alors carré x+1>carré x
On peut choisir: plus_que_carré x = carré x+1
Paradygme et développement d'un logiciel
1- Ecrire d'abord une spécification claire
2- Développer ensuite une implémentation raisonnablement efficace
Chp 2 - Les fonctions
I - Type fonctionnel et valeur fonctionnelle
Il s'agit du plus important type de valeur en programmation fonctionnelle. Les types prédéfinis utilisés ici seront vus en détail au chapitre 3.
1) Les fonctions mathématiques
Définition : Etant donné deux ensembles A et B, une fonction f définie dans A et à valeur dans B, et une loi de correspondance qui fait correspondre à tout élément de A, un de B. Quand f(x) existe, il est appelé le résultat de l'application de f à x.
2) Définition d'une fonction en maths
a) Le graphe représentatif: = {x,f(x)|x appartient à A}
b) Par abstraction: expression = 5-(3+x)²
x --> expression f(x)=5-(3+x)²
c) Utilisation d'une structure alternative
abs (x) = x si x>=0
= -x si x<=0
Par morceaux:
X(x) = x^3-1 si x <=1
= x²+4 si x>1 et <=10
=x-x si x>10 et <=1000
3) Les fonctions en programmation fonctionnelle
Définition: Etant donné deux types A et B, une fonction f définie dans A à valeur dans B et une loi de correspondance qui associe à toute valeur prise dans A une valeur dans B.
On exprime cette information sous la forme : f:A->B
Cette formule indique que le type de f est A -> B
La fonction f:A->B est : - prendre ses arguments dans A
- renvoyer un résultat dans B
Remarque:. Le symbole -> dénote un opérateur sur les types
. Il sert à construire de nouveaux types: LES TYPES FONCTIONNELS
Ainsi A->B dénote le type fonctionnelle des fonctions de A et B
Une valeur ayant un type fonctionnelle est appelée une fonction ou une valeur fonctionnelle.
Remarque: Il faut distinguer une fonction f de f(x), son application à un argument:
. f est une valeur prise dans le type fonctionnel A dans B
. f(x) est unue valeur de type B
Scripts de définitions de fonctions:
carre:num -> num (type de fonction)
carre x=x*x (Moyen de calcul de f(x))
double:num -> num
double x=2*x
Remarque: Notre langage fonctionnel est fortement typé, il n'est pas nécessaire d'accompagner les définitions de fonctions de leurs types. Celui-ci est directement déduit de l'équation de définition.
On verra que x, un opérateur sur le type num -> (num->num) est implicite.
4) Les paramètres de type
. La fonction id x=x
. Son type est A -> A quelque soit le type A
. Pour assigner à "id" un type sensé, on introduit alpha appelé: PARAMETRE DE TYPE
=> On dira alors que id est de type alpha -> alpha
Pour tout type A, id peut-être considéré de type A -> A
Convention : les paramètres de ce type seront alpha,beta,gamma
5) Vers un langage des expressions dénotant les types
Nous avons à notre disposition, le noyau de ce langage:
- les expressions constantes (num,car...)
- les paramètres de types (alpha,beta...)
- les opérateurs (-> ...)
Si une expression contient des paramètres de types, on dit qu'elle dénote un type polymorphe sinon, elle dénote un type monomorphe.
II - Déclaration de fonction
1) La formule de calcul est unique
identificateur paramètres = expression
On peut utiliser des paramètres (par1, par2...)
exemple :
carre x = x * x
produit (a,b) = a* b
somme x y = x+y
2) Le calcul de la valeur est fait par séparation des cas
identificateur paramètres = expression1, si condition
= expression2, si condition
................
= expression, si condition
->expression ->valeurs booléennes
Exemple:
min x y = x, si x<=y
= y, si x>y
morceaux x = x+1, si x<=1
= x+2, si x>1 et <=100
= x+3, si x>100
Remarque:
. L'évaluation des conditions est faite de façon linéaire de la première à la dernière posée.
. Les fonctions sont évaluées par la première condition vraie rencontrée.
. Si la liste des conditions n'est pas exaustive, on pourra engendrer un erreur (valeur non définie) à l'utilisation.
3) L'alternative simple
identificateur paramètres=expression1, si condition
=expression2, sinon
exemple:
max x y = x, si x>=y
= y, sinon
III - Les définitions locales
En math, une définition est parfois introduite sous la forme:
f(x,y)=(a+1)*(a+2) sachant que a=(x+y)/2
L'expression f(x,y) introduit un edéfinition locale dont le contexte est l'expression à droite du = dans la définition de f.
1) Pas de séparation des cas
identificateur paramètres = expression1 (contenant u) sachant que u=expression2
Exemple:
f x y = (a+1)*(a+2) sachant que a = (x+y)/2
2) Séparation des cas
identificateur paramètres=expression1, si condition1
...................
=expression2, si condition2
sachant que u = expression ?
Remarque: la portée de la définition locale est l'ensemble des cas
Exemple:
f x y = x + a si x>10
= x - a sinon
sachant que a=carre (y+1)
Remarques:
i) On peut avoir plusieurs définitions locales indépendantes.
On notera alors:
sachant que définition locale 1
(et implicite) définition locale 2
La règle de portée est la même et de façon indépendante les unes des autres.
ii) Une définition locale étant une définition, elle peut en contenir d'autres.
Exemple:
t = x + y + z | 26
sachant que z = x + y | 13
sachant que y = 3 + x | 8
sachant que x = 5 | 5
? t
26
?
3) Définitions locales en CAML
|Expression
|sachant que id f=expression
|Expression
|sachant que id f1=expression1
| id f2=expression2
|Expression
|sachant que id f2=expression2
| sachant que id f1=expression1
ALGORITHME
|let id f=expression1 in expression
|let id f1=expression1
|and id f2=expression2
|in expression
|let id f1=expression1
| in
|let id f2=expression2
| in
| expression
CAML
#let t=let x=5
in let y=3+x
in let z=y+z
in x+y+z;;
t:int=26
# t;;
_ : int=26
4) Les fonctions en CAML
let min x y = if x<=y then x
else y;;
let mini = function (x,y)
if x <= y then x
else y;;
Exemple: let carre x = x*x;;
let puis 4 x =let y = carre y
in carre y;;
IV - Les définitions récursives
1) Les fonctions récursives en programmation fonctionnelle
Une définition est récursive si elle fait appel à elle-même dans sa définition ou si elle fait appel à d'autres définitions qui font au moins appel une fois à sa définnition.
Exemple : calcul de n!
0!=1
n!=n(n-1)!
fact n = 1 si n=0
= n * fact (n-1) sinon
2) Les fonctions récursives en CAML
On doit ajouoter le mot-clé rec dans la définition après le mot-clé let.
Exemple:
. let rec fact n =
if n=0 then 1
else n * fact (n-1);;
. let rec fact = function n ->
if n=0 then 1
else n*fact (n-1);;
Chp 3 - Les types fondamentaux
I - Introduction
. Dans ce chapitre, on va introduire les types de valeur de base à l'aide desquels on va construire les expressions.
. Nous verrons quelle est la représentation de chacun d'entre-eux et nous donnerons quelques primitives permettant de les manipuler.
II - Les nombres (num)
1) Les valeurs numériques
Le type de valeur "num" comprend les entiers, les réels.
Notations : Entiers: 0;41;-12
Réels : 5.0;5.412;-143.51
Opérations : + (addition); - (soustraction); * (multiplication)
/ (division); ** (exponentiel; div (division entière); mod(reste)
Les deux dernières ne sont définies que sur les entiers.
Remarque:
Certains langages distinguent entiers et réels. Parfois, les symbôles opératoires sont distincts (exemple:CAML)
Exemple de session:
? 3-7-2
-6
? 3*7+4.1
25.1
? carré (3*4)
144
? carré 3*4
36
? 3**4*2
162
2) Règles de priorités
Dans l'ordre on a: **;*;/;div;mod
+;-
Les fonctions ont des priorités plus fortes que les opérations
On calcule d'abord les () internes
3) Les règles d'association
Elles permettent de résoudre le problème lié à l'apparition d'opérations de même niveau.
Lorsqu'on a des opérations de même niveau, on compose de gauche à droite.
Les deux exceptions sont ** et ->. Dans ces deux cas, l'opération est appliquée de gauche à droite.
Exemple:
. 7-15+2 signifie (7-15)+2 et non 7-(15+2)
. 3**2**2 signifie 3**(2**5) et non (3**2)**5
. alpha -> beta -> gamma signifie alpha -> (beta -> gamma) et non (alpha -> beta) -> gamma
. f x y signifie (fx)y et non f(xy)
. 7 mod 3 vaut 1
. (-7) mod 3 vaut 2
. 7 div 3 vaut 2
. (-7) div 3 vaut -3
4) Exemple d'utilisation des oopérations de base
cf TD
III - Les valeurs de vérité (bool)
1) Valeurs booléennes
Elles servent à comparer des expressions. Notées bool, elles se composent de deux valeurs VRAI et FAUX. Toute fonction renvoyant un booléen est dit prédicat.
2) Les opérations de comparaison
On y trouve : = ; /= ; < ; > ; >= ; <=
Session :
? 2 = 2
Vrai
? 5 <2+1
Faux
? Vrai = Faux
Faux
? Faux < Vrai
Vrai
Règle : les expressions que l'on peut analyser sont de même type et ont des représentations canoniques.
3 - Les opérations logiques
On y trouve : ou, et, non
4) Les règles de priorité
Priorité plus forte que les opérations arithmétiques.
Priorité dégressive non, ou, et.
Au même niveau, évaluation de gauche à droite
Exemple :
? 1<2 et 7<12
Vrai
? non (1<2)
Faux
5) Exemple d'utilisation
a) Déterminer si une année est bisextile
-Spécification
Une année bisextile est une année divisible par 4 sauf si elle est divisible par 100 auquel cas elle doit être divisible par 400.
- Implémentation
bisextile x=(x mod 400=0) si x mod 100=0
=(x mod 4)=0 sinon
ou bisextile x=(x mod 4=0) et (x mod 100=0) ou (x mod 400=0)
IV - Les caractères et chaînes (car et chain)
1) Les caractères
Les valeurs du type "car" se compose de l'ensemble des caractères ASCII, c'est à dire les signes visibles et les caractères de contrôle.
On les dénote en les mettant entre ''. 'a','A','5','-'...
Fonctions primitives: 2 fonctions permettent la conversion caractère en ASCII et inversement:
code: car -> num
décode: num -> car
Exemple:
?code 'b'
98
?decode 98
'b'
?decode (code 'b' ->1)
'c'
?code '7
' 10
Fonction de comparaison : 2 caractères peuvent être comparés. Elle est faite en comparant leur code ASCII.
Exemple:
?'a' < 'b'
Vrai
?'A' < 'a'
Vrai
Des fonctions simples manipulant des caractères
. Chiffre : car -> bool
chiffre x='0' <= x et x <='9'
. Majuscule: car -> bool
majuscule x='A' <= x et x<='2'
. Minuscule: car -> bool
minuscule x = 'a' <=x et x<='z'
. conv_min_maj: car -> car
conv_min_maj x = decode (ecart+code x) si minuscule sinon
= x, sachant que ecart = code 'A' - code 'a'
Traduction en CAML:
En CAML, il est en général nécessaire de prendre le code ASCII afin de comparer.
Le code ASCII est obtenu avec la fonction int_of_char
Le caractère associé est obtenu avec la fonction char_of_int
Exemple:
let chiffre x=(int_of_char '0' <= int_of_char x) & (int_of_char x <= int_of_char '9');;
let majuscule x=(int_of_char 'A') <= int_of_char x) & (int_of_char x <= int_of_char 'Z');;
let min-maj x=let ecart=int_of_char 'A'.int_of_char 'x'
in
if minuscule x
then char_of_int (ecart int_of_char x)
else x;;
2) Les chaînes
Elles sont des suites de caractères. Le type "chaîne" comprend toutes les chaînes. On les dénote en les mettant entre guillemets.
"Bonjour" "1231.167" "x-y215"
Fonction de comparaison
Elles s'effectuent dans l'ordre lexicographique
Exemple:
?"Bonjour" < "Bonjour"
Faux
?"Bon" < "Bonjour"
Vrai
?"Bonjour"
"Bonjour"
3) L'opération de concaténation notée ^
Elle renvoie comme chaîne résultat, la suite de caractères obtenus en mettant les deux chaînes à la suite l'une de l'autre.
Exemple:
a = "Bon"
b = "jour"
c = a'b
?c
"Bonjour"
Fonction "long_chaîne" donNant la longueur d'une chaîne
Exemple:
?long_chaîne "Bonjour"
7
4) Fonction manipulant des chaînes
La justification de l'affichage:
On suppose connue une fonction espace n qui renvoie une chaine de n espaces, on obtient alors :
justifierg n x = x^espace (n-m) si n >= m
sachant que m = long_chaine x
justifierd n x = espace(n-m)^x si n>=m
sachant que m = long_chaine x
justifierc n x = espace gm^x^espace dm si n>=m
sachant que dm=(n-m)-gm
sachant que gm = (n-m) div 2
sachant que m=long-chaine x
V) Les n-uplets
1) Définition: On peut former des nouveaux types en combinant des types par paires, par n-uplets...
Mathématiquement, il s'agit d'élément appartenant au produit cartésien de plusieurs ensembles.
E1*E2*...*En = {(x1...xn}, pour tout i appartenant à [1,n] xi appartient à Ei}
Produit cartésien de plusieurs types:
Soient n ensemble E1,...,En tel que ti est le type associé à l'ensemble Ei
Alors t1*t2*...*tn est le type associé à E1*E2*...*En
Les valeurs du produit sont notées (v1,...,vr) avec vi de type ti et sont des n-uplets.
vi appartient [1,n], vi:ti => (v1,...,vn):t1*t2*...*tn
Exemple: num * car est le type des paires dont le premier élément est un nombre, le deuxième étant un caractère.
num*bool*chaîne est le type des triplet...
Session:
? (4+2,'a')
(6,'a')
? (5,Vrai,'Bonjour')
(5,Vrai,'Bonjour')
Remarque: On peut introduire des définitions locales dans les n-uplets.
t=(x*x,3*x)
sachant que x=5
?t
(10,15)
2)Exemple d'utilisation
a)
quot-reste: num*num -> num*num
quot-reste (x,y) = (x div y,x mod y)
?quot-reste (7,2)
(3,1)
?quot-reste (7.1,2.2)
T inversé
b) Racines d'une équation de second degré
rac-equat (a,b,c)=(c1,c2) si (a /=0) et (d>=0)
sachant que r1=(-b+r)/(2*a)
r2=(-b-r)/(2*a)
sachant que r = racine d
sachant que d= b*b-4*a*c
Remarques :
i) L'operateur "div" n'est pas définit en CAML
ii) La fonction "rac-equat" n'est pas complètement définit => erreur si a=0 ou d<0
3) Comparaison des n-uplets (=,<=,>=,<,>)
Elle se fait dans l'ordre lexicographique en prenant les composants de gauche à droite.
Session:
? (3,4) = (4,3)
Faux
? ((1,2),3) = (1,(2,3))
Faux
? ('a','b') = ('a','b')
Vrai
? (3,6) < (4,2)
Vrai
Seule l'= est définit en CAML.
VI - Les filtres
La notion de filtre peut être vue comme une généralisation de la notion de paramètre.
Définition: . Un filtre décrit avec précision les différentes formes que peut prendre un paramètre et indique la façon de calculer le résultat.
Un filtre est applicable à des arguments de n'importe quel type.
Constructon: Un filtre est une expression formée à l'aide des constructions de valeurs, de constantes, de paramètres formels ayant des noms tous positifs et éventuellement le symbole -.
Quelques exemples de fonctions définies par filtrage
1- Condition Vrai x y = x
Condition Faux x y = y
2- Non Vrai = Faux
Non Faux = Vrai
3- Fact 0 = 1
Fact n=n*fact (n-1)
4- un_argument (Vrai,x,-) = x
un_argument (Faux,-,y) = y
Règles :
i) Quand une valeur est filtrée par plusieurs filtres, c'est la première qui est retenu.
ii) Le filtrage d'un paramètre formel effectue la liaison de la valeur au nom du parametre formel
iii) Le _ filtre toute valeur sans créer de liaison.
Le filtrage en CAML:
1- Match expression with
Filtre_1 -> result_1
|.......
|Filtre_n -> result_n
let condition P x y =
match P with
true -> x
|false -> y;;
Remarque: On ne définit pas explicitement de fonctions.
2- Let nom_funct = function
filtre1 -> expr1
|....
|filtren -> exprn;;
let rec fact = function
0 -> 1
|n -> n*fact (n-1);;
let reponse = function
"oui" -> true
|"non" -> false;;
Chp 4 - Les listes
I - Introduction
On va définir le concept de liste, présenter les principales...
II - Le type liste
1- Définition-Notation
. Une liste est un ensemble de valeurs d'un même type linéairement ordonnée.
. Une relation d'ordre est définit à partir du rang des éléments de la liste (le rang du premier = 0)
. La liste de valeur v1,...,vn est notée [v0,v1,...,vi,...,vn-1]
Exemple:
[1;2;3] liste de trois nombres
[[]] liste d'une liste
[] liste vide
[[1;2],...,[3;5]] liste de listes à deux éléments
si alpha est le type des éléments, la liste est [alpha]
Exemple:
[1;2;3]:[Num]
[[1;2];[2;3]]:[[Num]]
Remarque: Etant donné que les chaînes sont des listes de carctères, toutes les opérations sur leslistes sont applicables aux chaînes.
Deux listes sont égales si et seulement si elles contiennent les même éléments dans le même ordre.
Session:
?[1;1] = [1]
Faux
?[1;2;4]=[3;2;1]
Faux
?[1;9;11]=[1;9;11]
Vrai
Cas particuliers: [a...b] = {la liste des entiers de a à b si a<=b
{[] si a>b
2- Définition d'une liste en compréhension
La définition posée précédemment est extensible, on énumère la liste.
Elle ne donne pas un moyen pour définir une liste donnée en comprehension
l=[x|homme x,age(x) appartient à [20;40]]
Elle se déclare : [< expression >|< qualificateur >...< qualificateur >]
où < expression > dénote : -une expression booléenne
-un générateur
< variable> <- < liste >
[< variable >,< variable >] <- < liste de paires >
Le premier signifie que la variable reçoit toutes les valeurs de la liste.
Le second signifie la conjonction des deux proprités. Les derniers qualificateurs varient plus vite que leurs prédécesseurs.
Session:
?[x*x|x <- [1..10], pair x]
[4;16;36;64;100]
?[(a,b)|a<-[1..3],b<-[1;2]
[(1,1);(1,2);(2,1);(2,2);(3,1);(3,2)]
?[(i,j)|i <- [1..4], pair i,j <- [i+1..4],impair j]
[(2,3)]
Remarque: Des listes définies en compréhension peuvent être utilisées dans les définitions.
Exemple:
. diviseur n = [d|d <- [1..n],n mod d=0]
liste des diviseurs de n (entier n>=1)
. Premier a = [diviseur n=[1..n]]
tester si n>=1 est premier ou non
Remarque:
Les définitions de listes en compréhension n'existent pas en CAML.
III - Opérations et fonctions de base sur les listes
1- La concaténation des listes
Etant données deux listes de même types
l1 = [e1,...en] et l2=[f1,...,fn]
@ renvoie la liste:
l1@l2 = [e1,...,en,f1,...,fn]
Session:
?[1;2;3]@[4;5]
[1;2;3;4;5]
type:[alpha] -> [alpha] -> [alpha]
Convention: x,y,z... désignent des éléments de listes.
xs,ys,zs...désignent des listes
xss,yss,zss... désignent des listes de sites.
2- La fonction concat
concat: [[alpha]] -> [alpha]
concat xss = [x|xs<-xss,x<-xs]
Session:
?concat [[1;2];[];[3;2;1]]
[1;2;3;2;1]
Remarque: concat n'est pas prédéfinit en CAML
3- La longueur d'une liste
long_liste:[alpha] -> num
Exemple:
?long_liste []
0
?long_liste [1;1;2;2;3;3]
6
Remarques:
. long_liste (xs@ys)=long_liste xs + long_liste ys
. long_liste (expression|x<-xs)=long_liste xs
4- L'opérateur :: (cons)
x est un élément de type alpha et xs un eliste de type [alpha]
:: renvoie comme liste celle obtenue en insérant l'élément x en tête de xs.
Si xs=[x1;...;xn] alors
x::xs=[x;x1;...;xn]
Session:
?1::[]
[1]
Remarque:
[x1;x2;...;xn]=x1::x2::...::xn::[]
5- Tête et queue de liste
"tête" renvoie le premier élément d'une liste.
"queue" renvoie la liste privée de son premier élément.
tête:[alpha]->alpha
queue:[alpha]->[alpha]
Propriétés:
tête ([x]@xs)=x=tête(x::xs)
queue([x]@xs)=xs=queue(x::xs)
tête[]=T inversé
queue[]=T inversé
xs=[tête xs]@queue xs
6-Filtrage sur leslistes
Les filtres sont soit:
- la constante []
- bâtis avec ::
Remarque: Car une liste est obtenue d'une et d'une seule avec [] et ::
Exemple:
1- singleton [] = Faux
singleton [x] = Vrai
singleton x::y::xs=Faux
Foncton booléenne testant si une liste est un sigleton.
2- vide [] = Vrai
vide _ = Faux
3- tête x::xs=x
tête [] = T inversé
IV - Fonction de manipulation de listes
1 - Les fonctions "retirer" et "prendre"
n>0 et une liste xs
retirer n xs=retire les n premiers éléments de xs
prendre n xs=renvoie les n premiers éléments de xs
Exemple:
?Prendre 3 [1..10]
[1;2;3]
?retirer 3 [1..6]
[4;5;6]
2- Les fonctions "retire tq" et "prendre tq"
Elles agissent comme les précédentes à ceci près que leur premier argument est un prédicat à laplace d'un entier.
prendretq p xs réunie le plus segment initial de xs dont les éléments satisfont p.
retiretq p xs supprime dans xs le plus grand segment initial dont les éléments satisfont p.
?prendretq pair [2,4,6,1,5,6]
[2,4,6]
?retiretq (='a') ['a','a','b','0']
['b','0']
3- La fonction "renverser"
Elle renvoie la liste en ordre inverse.
?renverser ["Bonjour";"a;"tous"]
["tous";"a";"Bonjour"]
4- Les fonctions "coupler"
Elle a pour argument une paire de liste, elle renvoie une liste de paires.
Si elles n'ont pas lamême longueur, le couplage s'arrête sur la liste la plus courte.
?coupler([1..3],[5..7])
[(1,5);(2,6);(3,7)]
?coupler ([1..5] ["B","a","n"])
[(1,B);(2,0);(3;n)]
i) Produit scalaire: X.Y=somme (de i=1 à n) de xi*yi
ps (xs,ys)=somme[x*y|(x,y)<-coupler(xs,ys)] où l'on suppose connue la fonction "somme" qui ajoute les éléments d'une liste.
ii) Position de la première occurence de x dans xs
a- position xs x = [i|(i,y) <- coupler ([0..long_liste xs],xs),x=y]
b- position xs x = tete((positions xs x)@[-1])
5-Les fonctions "appliquer" et "filtrer"
La fonction "appliquer" applique une fonction f donnée à tous les éléments d'une liste, et renvoie la liste composée des résultats trouvés.
appliquer: (alpha -> beta) -> [alpha] -> [beta]
appliquer f xs = [f x|x <- xs]
Session:
?appliquer carré [9;2]
[81;4]
?somme (appliquer carré [1..5])
55
Propriété:
appliquer f(xs@ys) = (appliquer f xs)@(appliquer f ys)
"filtrer" a pour argument un prédicat p et un eliste xs. Elle renvoie la sous-liste des éléments de xs vérifiant p.
filtrer:(alpha->bool)->[alpha]->[alpha]
filtrer p xs:[x|x <-xs,p x]
Session:
?filtrer pair [1;2;4;5;62]
[2;4;62]
?appliquer carré filtrer pair [1..10]
[4;16;36;64;100]
Propriétés: filtrer p (xs@ys)=(filtrer p xs)@(filtrer p ys)
6- Traduction des listes en compréhension
Toute liste définie en compréhension commençant par un générateur peut-être traduite à l'aide des fonctions "appliquer", "filtrer", "concat".
Pratiquement, on y parvient à l'aide des quatre règles suivantes:
i) [x|x<-xs]=xs
ii) [f x|x <- xs]=appliquer f xs
iii) [e|x <- xs,px,...]=[e|x <- filtrer pxs...]
iv) [e|x <- xs,y <- ys...]=concat[e|y<-ys]x<-xs
Exemple:
[x*x|x<-xs,pair x]=appliquer carré (filtrer pair xs)
V - Les opérateurs "recomposer"
Ils vont permettre de convertir des listes en autre chose que des listes.
Il y a deux schemas possible que l'on va maintenant presenter.
1) L'operateur "recomposerg"
recomposerg : (beta -> alpha -> beta) -> beta -> [alpha] -> beta
(*** vient ensuite une feuille simple sur recomposerd et recomposerg. Je ne l'ai pas retranscrit car les indices y pullulent***)
Chp 5 - La récursivité
I - Introduction
On va mettre l'accent sur les deux notion fondamentales que sont :
- les définitions récursives
- les principes de récurrence
En programmation fonctionnelle, elles nous permettent de:
-définir des fonctions introduites précédemment
-de démontrer un certain nombre de propriétés des opérateurs en fonction.
II - Récursivité et récursion
1- Définitions récursives
Une définition est récursive si elle fait appel à elle même sans sa définition où si elle fait appel à d'autres définitions qui feront appel au moins une fois à sa définition.
Exemple: Calcul de x^n sachant que x appartient à N+
x**n=1 si n=0
=x*x**(n-1), si n>0
En utilisant des filtres, on peut écrire:
x**0=1 (1)
x**n=x*x**(n-1) (2)
La définition de x^n est bien récursive: pour une valeur de x, la valeur de x^n est obtenue à partir de la valeur de x^n-1 dont la valeur est obtenue à partir de x^n-2 et ainsi de suite jusqu'à ce que l'on atteigne x^0 connu.
2- Principe de récurrence sur les entiers
Soit P(n) vraie, une propriété qui dépend d'un entier n>=0.
Pour tout n appartenant à N, P(n) vraie <=> 1. P(0) vraie
2. Pour tout n appartenant à N*, si P(n-1) vraie alors P(n) vraie.
-> x**x(m+n)=(x**m)*(x**n)
avec x>0 et (m,n) appartenant à R²
Il suffit de faire un raisonnement par récurrence sur m
a/ x**x(0+n)=x**(n) *(Propriété de l'+)*
=1*x**(n) *(Propriété de l'*)*
=(x**0)*(x**(n)) *(Propriété n°1)*
b/ Supposons la propriété vraie pour la valeur m-1
x**(n+m)=x**((m-1+n)+1) *(Propriété de l'+)*
=x*(x**(m-1+n)) *(Propriété n°2)*
=x*((x**(m-1))*(x**n)) *(Hypothèse de récurrence)*
=x*(x**(m-1)*x(x**(n))) *(Propriété de l'*)*
=(x**m)*(x**n)
III - Récursion et récurrence des listes
. Pour les entiers, la récurs° et la récurrence sont basées sur deux cas: 0 et n
. Ces principes peuvent être appliqués aux listes
. Elles vont reposer sur deux cas: liste [] et liste x::xs pour x et xs.
1-Définitions récursives sur des listes
Donnons quelques exemples de définitions récursives poratnt sur des listes:
i) Fonction long_liste
long_liste []=0
long_liste (x::xs)=1+long_liste xs
ii) L'opération concaténation des listes
[]@ys=x::(xs@ys)
iii) Inversion d'une liste
renverser [] = []
renverser [x::xs]=renverser [xs]@[x]
2- Principes de récurrence sur les listes finies
Soit P(xs) une propriété qui dépend d'une liste finie xs: [alpha]
Pour tout xs finie, P(xs) vraie <=> |i) 1-P([]) vraie
|ii) Pour tout x:alpha, si P(xs) vraie alors P(x::xs) vraie
Remarque: On peut formaliser ce principe à partir du principe de récurrence sur les entiers en utilisant la longueur des listes.
Exemple: Preuve de l'associativité de @
-> xs@(ys@zs)=(xs@ys)@zs
Preuve par récurrence sur xs
. Cas []
[]@(ys@zs)=(ys@zs)
=(([]@ys)@zs)
. Cas (x::xs) supposé vrai pour xs
(x::xs)@(ys@zs)=x::(xs@(ys@zs))
=x::((xs@ys)@zs)
=(x::(xs@ys))@zs
=((x::xs)@ys)@zs
IV - Définition formelle d'opérateurs sur les listes
Au chapitre 4, on a vu des fonctions manipulant des listes, on va donc voir:
1- La fonction "coupler"
On la définit par filtrage (liste exhaustive)
coupler ([],ys)=[]
coupler (x::xs,[])=[]
coupler (x::xs,y::ys)=(x,y)::(xs,ys)
Remarque: On peut vérifier que les filtres recouvrent bien toutes les combinaisons possibles des deux arguments.
2-Preuve par induction sur les filtres
Le principe de récurrence sur les listes peut-être généralisé avec les définitions récursives définies par filtrage, ceci dans la mesure où l'on a définit la liste exhaustive des filtres correspondants à toutes les combinaisons des arguments impliqués.
Exemple: montrer que:
lg_liste coupler (xs,ys)=min (lg_liste xs) (lg_liste ys)
. Cas ([],ys):
lg_liste coupler ([],ys)=lg_liste[]
=0
=min 0 lg_liste ys
=min lg_liste [] lg_liste ys
. Cas (x::xs,[])
lg_liste coupler (x::xs,[])=lg_liste []
=0
=min 0 lg_liste (x::xs)
=min lg_liste (x::xs) lg_liste[]
3-Les fonctions prendre et retirer
prendre 0 xs = []
prendre n [] = [}
prendre n (x::xs) = x::prendre (n-1) xs
retirer 0 xs = xs
retirer n []
retirer n (x::xs) = retirer (n-1) xs
Remarques :
1/ Une preuve/recurrence sur n, ne prevoit pas la possibilite d'avoir n=T inverse; si on veut le prevoir, il faut l'inclure dans la demonstration comme cas additionnel.
2/ Il en est de même avec une variable liste qui peut recevoir la valeur T inverse, il faut la traiter separement.
Preuve par filtrage de la propriete :
(prendre n xs)@(retirer n xs) = xs
- Cas 0 xs :
(prendre 0 xs)@(retirer 0 xs)
= []@[] (1 de prendre et retirer)
=xs (propriete 1 de @)
- Cas n [] :
(prendre n [])@(retirer n [])
= []@[] (2 de prendre et retirer)
= [] (1 de @)
- Cas n (x::xs) : Vrai pr ((n-1)xs)
(prendre n (x::xs))@(retirer n (x::xs))
=x::((prendre (n-1) xs)@(retirer (n-1) xs))
=(x::xs)
Remarques :
prendre 0 Tinverse = []
prendre Tinverse [] = Tinverse
retirer 0 Tinverse = []
retirer Tinverse [] = Tinverse
=> prendre Tinverse [] @ retirer Tinverse [] = Tinverse @Tinverse = Tinverse
ne verifie pas la propriete.
4-Les fonctions tete et queue
tete (x::xs) = x
queue (x::xs) = xs
tete [] = Tinverse
et queue [] = Tinverse
Propriete : [tete xs]@[queue xs] = xs quelque soit xs /= []
La demonstration se fait par analyse des cas sur xs.
[tete (x::xs)]@[queue(x::xs)] = [x]@xs = (x::xs)
5-Les fonctions appliquer et filtrer
appliquer f [] = []
appliquer f (x::xs) = f x::(appliquer f xs)
filtrer p [] = []
filtrer p (x::xs) = x::(filtrer p xs) si px
= filtrer p xs sinon
On peut montrer que :
filtrer p (appliquer f xs) = appliquer f (filtrer (p o f) xs)
VI - Auxiliaires et generalisations
Dans certains cas, pour definir une fonction ou pour prouver un theoreme il est plus facile ou necessaire :
- Soit de definir des fonctions auxiliaires ou de prouver des theoremes auxiliaires
- Soit de definir des definitions plus generales ou de provoquer des theoremes plus generaux.
Un exemple : la fonction renverser possede la propriete suivante :
renverser (renverser xs) = xs
[tete (x::xs)]@[queue (x::xs)] = [x]@xs = (x::xs)
La demonstration est plus facile si l'on procede comme suit :
i/ Montrer par induction que renverser (ys@[x]) = x::renverser ys
ii/ L'appliquer ensuite a la propriete a demontrer.
Montrons le resultat auxiliaire :
renverser (ys@[x]) = x::renverser ys
raisonnement par recurrence sur ys.
. Cas [] :
renverser ([]@[x]) = [x] = x::renverser []
. Cas (y::ys) : vrai pour ys
renverser (y::ys@[x])
=renverser (ys@[x])@[y]
=x::renverser ys@[y]
=x::renverser (y::ys)
On peut alors montrer que renverser (renverser xs) = xs
raisonnement par recurrence sur xs.
. Cas [] :
renverser (renverser []) = renverser [] = []
. Cas (x::xs) : vraie pour xs
renverser (renverser (x::xs))
=renverser (renverser xs@[x])
=x::renverser (renverser xs)
=x::xs
VII - Implementation des resultats en CAML
let rec renverser = function [] -> []
|x::xs -> renverser xs@[x];;
let rec coupler = function
([],ys) -> []
|(x::xs,[]) -> []
|(x::xs,y::ys) -> (x,y)::coupler (xs,yx);;
let rec prendre = function
0, xs -> []
|n,[] -> []
|n,x::xs -> x::prendre (n-1,xs);;
let rec retirer = function
let appliquer = map;;
let recomposerg = it_list;;
let recomposerd = list_it;;
let tete = hd;;
let queue = tail;;
let long_liste = list_lenght;;
let rec filtrer = function
p,[] -> []
|p,x::xs -> if px
then x::(filtrer(p,xs))
else filtrer (p,xs);;
let rec intervalle a b = if a>b
then []
else a::intervalle (a+1) b;;