Programmation fonctionnelle

Licence D'Informatique - 3ème Année

Description

• cours - matière potentielle : cours

Programmation fonctionnelle Notes de cours Cours 3 28 Septembre 2011 Sylvain Conchon 1/21

• acces aux elements
• conditions sur les branches du filtrage
• char list
• addition par recurrence sur le couple
• true val
• let
• filtrage
• champs
• champ

Sujets

• cours

Informations

• Publié par: onjou
• Nombre de lectures: 41
• Langue: Français

Extrait

Programmation fonctionnelle
Notes de cours
Cours 3
28 Septembre 2011
Sylvain Conchon
[e-mail]
1/21Le programme de cette semaine
Le boulier japonais
2/21Le boulier japonais
Le boulier japonais convient parfaitement pour calculer en base 10.
Il est form´e de tiges s´epar´ees en deux par une barre transversale.
I Les boules du haut valent 5 unit´es et celles du bas 1 unit´e.
I On active une boule quand on la rapproche de la barre
transversale.
I La colone la plus `a droite repr´esente le chiffre des unit´es, celle
juste `a sa gauche repr´esente le chiffre des dizaines etc.
Par exemple, le nombre 3451 sera repr´esent´e par la configuration
suivante :
3/21Le boulier japonais : points techniques
On r´ealise l’op´eration d’addition de deux bouliers b et b . Pour1 2
cela, on ajoute les tiges de la droite vers la gauche (comme une
addition `a la main).
I Les deux bouliers n’ont pas n´ecessairement le mˆeme nombre
de tiges. On d´efinit l’addition par r´ecurrence sur le couple
(b ,b ) en prenant en compte la retenue.1 2
I Addition de 2 tiges (h ,l ) et (h ,l ) avec une retenue r1 1 2 2
l = (l + l + r) mod 51 2
h = (l/5+ h + h ) mod 21 2
0r = (l/5+ h + h )/21 2
I on affiche les tiges d’un boulier `a l’horizontale; par exemple le
boulier repr´esentant le nombre 462 est affich´e ainsi :
o-|oo-oo
-o|o-ooo
o-|oooo-
4/21Les notions abord´ees avec ce programme
I types enregistrement
I les listes
I pattern-matching (suite)
I polymorphisme
I it´erateurs
I assert
5/21Enregistrements
# type complexe = {re : float; im : float};;
type = {re : float; im : float}
# let c = {re = 1.4; im = 0.5};;
val c : complexe = {re = 1.4; im = 0.5}
# c.im +. 4.2;;
- : float = 4.7
I les enregistrements sont des n-uplets dont les ´el´ements, les
champs, ont chacun un nom distinct
I l’acc`es aux ´el´ements se fait `a l’aide de la notation v.champ
6/21Enregistrements : pattern-matching
# type t = {a : int; b : float * char; c : string};;
type t = {a : int; b : float * char; c : string}
# let v = {a = 1; b = (3.4,’a’); c = "bonjour"};;
val v : t = { a = 1; b =; c = }
# let {b = ( ,x); c = y} = v;;
val x : char = ’a’
val y : string = "bonjour"
I le filtrage permet un acc`es partiel et de mani`ere interne aux
champs d’un enregistrement
I il permet de d´efinir plusieurs variables simultan´ement
7/21Enregistrements : ordre des champs
I les d´efinitions de types suivantes sont ´equivalentes
type t = { a : int; b : char; c : bool }
type t = { b : char; c : bool; a : int }
I de mˆeme ces valeurs sont ´egales
# {a = 1; b=’t’; c=true} = {b=’t’; c=true; a=1};;
- : bool = true
I le filtrage est ´egalement insensible `a l’ordre des champs
# let {c = x; b = y} = {b = ’t’; c = true; a = 1};;
val x : bool = true
val y : char = ’t’
8/21Les listes
# 4::1::5::8::1::[];;
- : int list = [4; 1; 5; 8; 1]
# [’a’; ’b’; ’c’] =;;
- : char list = [’a’; ’b’; ’c’]
# [2.3]::[1.]::[[4.4; 7.8+0.1]];;
- : float list list = [[2.3]; [1.0]; [4.4; 7.9]]
I list est le type g´en´erique des s´equences de valeurs
I une liste ne peut contenir que des ´el´ements de mˆeme type
I la liste vide est not´ee []
9/21Listes : pattern-matching
La d´efinition des fonctions sur les listes prennent g´en´eralement la
forme d’une d´efinition avec au moins deux cas :
I le cas ou` la liste est vide (cas de base)
I le cas ou` elle ne l’est pas (r´ecurrence)
Pour cette raison, il est plus agr´eable de r´ealiser cette analyse par
cas avec du filtrage
let f l =
match l with
| [] -> ...
| x::s -> ...
I on peut ´egalement ajouter des conditions sur les branches du
filtrage `a l’aide de la construction when e, ou` e est une
expression bool´eenne
10/21