Algorithmes et structures de donnees. Initiation au langage CamL.pdf

(259 KB) Pobierz
Algorithmes et structures de donn´es. Une introduction a la
e
`
programmation fonctionnelle et au langage Caml
Jocelyn S´rot
e
22 avril 2004
Pr´ambule
e
Ce document constitue une introduction a la programmation fonctionnelle – et en particulier au langage
`
Objective Caml – a travers la mise en œuvre de structures de donn´es classiques en informatique (listes,
`
e
arbres, graphes). Dans cette optique, les implantations et les algorithmes propos´s restent d´lib´r´ment
e
e e e
simples. Il existe de nombreux documents traitant de mani`re beaucoup plus approfondie des aspects pu-
e
rement algorithmiques. Par ailleurs, bien que ce cours puisse ˆtre vu comme une initiation a Caml, il ne
e
`
constitue en aucune fa¸on une formation compl`te a ce langage et encore moins d’un manuel de r´f´rence.
c
e `
ee
Le lecteur est donc invit´, corr´lativement, a se reporter aux ouvrages, documents et publications (pour
e
e
`
la plupart disponibles en lignes) traitant du langage et de ses applications (voir la bibliographie en fin de
document).
La forme du document privil´gie une approche
«
en situation
»
des probl`mes, les types de donn´es
e
e
e
et fonctions ´tant construits et valid´s
«
en temps r´el
»
via un interpr´teur
Caml.
Ces notes constituent
e
e
e
e
une trace comment´e de ces sessions de travail : les phrases entr´es par le programmeur sont pr´c´d´es du
e
e
e e e
caract`re d’invite # et suivies de la r´ponse de l’interpr´teur.
e
e
e
1
Chapitre 1
Rudiments
1.1
Expressions, valeurs et types
La notion cl´ en Caml (et plus g´n´ralement dans tout langage
fonctionnel
) est celle d’expression. Toute
e
e e
expression poss`de une
valeur
et un
type.
Ecrire un programme consiste a d´finir une expression dont la
e
` e
valeur est la solution au probl`me pos´. L’ordinateur ne fait alors qu’´valuer cette valeur. Dans les exemples
e
e
e
qui suivent, cette ´valuation est effectu´e de mani`re interactive par le
toplevel.
e
e
e
#1+2 ; ;
- :
int
= 3
Parmi les types de base on trouve notamment :
int, float, bool
et
string
1.1.1
Entiers et flottants
#2.1 *. 3.4 ; ;
- :
float
= 7.14
#4.5 *. 2 ; ;
Characters
7
−
8 :
4.5 *. 2 ; ;
ˆ
This expression has
type
int but is here used
with type
float
Les types
int
et
float
sont distincts et requi`rent des op´rateurs sp´cifiques. Les coercions sont toujours
e
e
e
1
explicites via les fonctions
float of int
et
int of float
par exemple
#4.5 *.
float of int(2);
;
- :
float
= 9.
1.1.2
Chaines de caract`res
e
Les chaines de caract`res sont ´crites entre ”. L’op´rateur de concat´nation est ˆ
e
e
e
e
#"Hello" ; ;
- :
string
=
"Hello"
1
On
verra pourquoi plus loin.
2
DEA CSTI - C4TCa
#"Hello,
"
ˆ
"world !"
; ;
- :
string
=
"Hello, world !"
SdD et algorithmes en Caml
1.1.3
Bool´ens
e
Il y deux valeurs bool´ennes :
true
et
false.
Les relations usuelles de comparaison (=,
<, >=,
. . . ) en particulier
e
retournent une valeur bool´enne. Elles op´rent sur des valeurs n’importe quel type :
e
e
#1> 2; ;
- :
bool
=
false
#1.2 = 1.2 ; ;
- :
bool
=
true
#"hello" =
"world"
; ;
- :
bool
=
false
La conditionnelle s’exprime avec
if, then
et
else.
Attention,
c’est ici une
expression,
qui poss`de donc une
e
valeur
:
#if 5+4
>
10
then
"Oui"
else
"Non"
; ;
- :
string
=
"Non"
1.1.4
N-uplets
Les
n-uplets
correspondent a un produit cart´sien de valeurs : ils combinent des valeurs de types quel-
`
e
conques sous la forme de paires, triplets,
etc.
:
#(1, 2); ;
- :
int
×
int
= (1, 2)
#("jean", 46, 2650.0); ;
- :
string
×
int
×
float
= ("jean", 46, 2650.)
1.2
D´finitions
e
Le mot-cl´
let
permet de nommer une valeur (pour la r´utiliser plus tard par exemple). La syntaxe est la
e
e
suivante :
let
nom
=
valeur
#let
pi
= 4.0
∗
.
atan
1.0; ;
val
pi
:
float
= 3.14159265359
#pi
∗
.
pi
; ;
- :
float
= 9.86960440109
Attention
: Les d´finitions ne correspondent pas aux
«
variables
»
(du C notamment). En particulier, elles
e
ne sont pas modifiable : le nom d´fini est d´finitivement li´ a la valeur calcul´e lors de la d´finition. C’est un
e
e
e`
e
e
simple synonyme pour cette valeur. On ne peut donc pas utiliser un nom avant de l’avoir d´fini.
e
J. S´rot
e
3
DEA CSTI - C4TCa
#let
y
=
sin
(pi
/.
2.0); ;
val
y
:
float
= 1.
#let
u
=
y
∗
.
2.0; ;
val
u
:
float
= 2.
#let
z
=
x
+ 1; ;
Characters
8
−
9 :
let
z
=
x
+ 1; ;
ˆ
Unbound value x
SdD et algorithmes en Caml
1.2.1
D´finitions locales
e
let
v
=
e1
in
e2
La forme
signifie que
x
vaut
e1
pendant le calcul de
e2
(et seulement pendant ce calcul).
#let
r
=
let
x
= 3
in
x
×
x
; ;
val
r
:
int
= 9
#x ; ;
Characters
0
−
1 :
x
; ;
ˆ
Unbound value x
L’identificateur
x
n’est visible que dans l’expression qui suit le
in
du
let
correspondant.
Les d´finitions peuvent ˆtre imbriqu´es a une profondeur arbitraire. Dans ce cas, les identificateurs d´finis a
e
e
e `
e
`
un niveau d’imbrication sont visibles a tous les niveaux
«
inf´rieurs
».
`
e
#let
u
= 2; ;
val
u
:
int
= 2
#let
v
= 3; ;
val
v
:
int
= 3
#let
w
=
let
x
=
u
+
v
in
let
y
=
x
×
u
in
x
×
y;
;
val
w
:
int
= 50
J. S´rot
e
4

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin