VERSION ENSEIGNANTS – NE PAS DIFFUSER

VERSION ENSEIGNANTS – NE PAS DIFFUSER

 
Université Département
Grenoble UFR IM2AG Licence Sciences
1 Questionnaire à choix multiples
 
40 pts
Alpes et Technologie
NE PAS RÉPONDRE SUR CET ÉNONCÉ.
UTILISER LA FEUILLE DE RÉPONSES SÉPARÉE.
TECHNOLOGIES 1re ANNÉE
LICENCE SCIENCES & TECHNOLOGIES,

UE INF201
ALGORITHMIQUE ET PROGRAMMATION FONCTIONNELLE

2021-2022

DEVOIR SURVEILLÉ — mars 2021-2022

sources : Exams/21-22/Partiel/
⎧ i21_partiel_21-22.tex
{
dépôt local , dépôt distant ⎨ prologue_ds_custom.tex , preambule_ds_custom.tex
{ enonce.tex
⎩

• Épreuve de 2 heures ; document autorisé : une feuille A4 manuscrite recto-verso ; appareils

électroniques interdits (à l’exception d’une montre non connectée).

• Le sujet comporte un QCM et trois exercices. Le QCM n’est pas nécessairement plus facile.
L’ensemble est noté sur 100 points. Le barème est donné à titre indicatif.

• Si vous êtes bloqué par une question, passez à la suivante qui peut être moins difficile. Il vous
est demandé de RÉPONDRE AUX QUESTIONS DANS L’ORDRE DE L’ÉNONCÉ.
Dans toute question, il est possible d’utiliser une fonction d’une question précédente sans
l’avoir définie. En revanche, l’utilisation d’une fonction auxiliaire de votre invention n’est
possible qu’après l’avoir spécifiée et réalisée.

• Prenez le temps de bien lire le sujet et de repérer les questions faciles.

Table des matières

1 Questionnaire à choix multiples 2

2 Exercise : kuple 6

3 Exercise : Normandy Battle 7

3.1 The type 𝑐𝑎𝑟𝑡𝑒 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 Rank and color of a carte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.3 The Normandy Battle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

4 Exercise : toise, pied and pouce 11

INF 201 algo. et prog. fonctionnelle 1/15 2/15 INF 201 algo. et prog. fonctionnelle

[git] • Branche master @ 621a931 • Version v1.4.1-polys-I-II ( 14/03/2022 ) par François Puitg [git] • Branche master @ 621a931 • Version v1.4.1-polys-I-II ( 14/03/2022 ) par François Puitg
 y
VERSION ENSEIGNANTS – NE PAS DIFFUSER +1/1/60+ y y +1/2/59+ y

VERSION ENSEIGNANTS – NE PAS DIFFUSER

Questionnaire du QCM d'INF201, INF231, INF251
Question 9 ♣ Le type point déni par type point = float*float est

Répondre sur la feuille réponse à part A un type récursif D un type énuméré

Question 1 ♣ Quelle est le type de l'expression (float_of_int 2) B un brave type E un type produit
C un type synonyme du type float*float F un type somme
A unit C int
Question 10 ♣ On veut modéliser les mois de l'année. On peut pour cela dénir le type mois par
B float D bool
A type mois (x:int) if 1 <= x <= 12
Question 2 ♣ Quelle est le type de la fonction f dénie par let f (x:int) : int = x/2
B type mois = 1|2|3|4|5|6|7|8|9|10|11|12
A float C int→int→int C type mois = Jan|Fev|Mar|Avr|Mai|Jun|Jui|Aou|Sep|Oct|Nov|Dec
B int→int D int D type mois = int (*restreint au entier de 1 à 12*)
Question 3 ♣ L'expression 2<3<6 E type mois = Jan*Fev*Mar*Avr*Mai*Jun*Jui*Aou*Sep*Oct*Nov

A s'évalue a true B s'évalue a false C renvoie une erreur de type Question 11 ♣ La valeur de l'expression let x = 10 in let x = 3 and y = x+4 in x+y est

Question 4 ♣ L'expression if a then true else false est équivalente à A 17 B 24 C 10

A ne peut pas se simplier B not a C a Question 12 ♣ La valeur de l'expression let x = 10 in let x = 3 in let y = x+4 in x+y
est
Question 5 ♣ L'expression if a then b else false est équivalente à
A 10 B 17 C 24
A a && b E (not a) && b
Question 13 ♣ On veut implémenter une fonction f qui convertit les float sans décimale après
B not (a || b) le point (comme 2.) en int (par ex. (f 2.) = 2) et qui renvoie -1 sinon (par ex. (f 2.1) = -1).
F a || b
C (not a) || b Cocher les implémentations correctes:
D ne peut pas se simplier G not (a && b)
A aucune des autres réponses n'est correcte.
Question 6 ♣ La fonction f dénie par let f a x = if a then x = 2 else x = 3 est de type B let f (x:float):int = let y = int_of_float x in if x = y then y else -1
C let f (x:float):int = if x = int_of_float x then x else -1
A bool*int→int F bool→int→ bool
D let f (x:float):int = let y = (int_of_float x) in
B bool→int→ int G bool
if x = (float_of_int y) then y else -1
C bool→bool→ bool H bool*int→bool
D bool→bool→ bool I bool→int Question 14 ♣ On veut dénir une fonction sum : int → int telle que sum n est la somme des
entiers de 0 à n. Parmi les implémentations suivantes lesquelles sont correctes:
E int J ne peut pas être typé correctement
A let sum n = (n*(n+1))/2
Question 7 ♣ La fonction f dénie par let rec f (n: int):int = n*f (n-1)
B let rec sum n = if n>0
A renvoie la valeur n! (factorielle n) B ne termine jamais, quelque soit l'entrée n then n+(sum (n-1)) else 0
C est récursive C let rec sum n = match n with
|0-> 0
Question 8 ♣ Le type t déni par type t = Empty | Node of t*t est |n->n+(sum (n-1))
D aucune des autres réponses ne sont correctes.
A un type somme D un type énuméré
E let rec sum n = match n with
B un brave type |n->n+(sum (n-1))
C un type produit E un type récursif |0-> 0

y [git] • Branche master @ 621a931 • Version v1.4.1-polys-I-II ( 14/03/2022 ) par François Puitg y y [git] • Branche master @ 621a931 • Version v1.4.1-polys-I-II ( 14/03/2022 ) par François Puitg y
 y
VERSION ENSEIGNANTS – NE PAS DIFFUSER +1/3/58+ y

VERSION ENSEIGNANTS – NE PAS DIFFUSER

  2 Exercice : kuple
 
10 pts
Question 15 ♣ On dénit la fonction f par let f b z = if not b then 5. else z

A (f true 4.) vaut 5. D z est de type oat Exo_et_Pb/Types_recursifs/Peano/Kuple/

B (f true 4.) vaut 4. Rappelons que les naturels de Peano sont une façon de représenter l’ensemble des entiers ⩾ 0,
C b est de type bool E z est de type unit N
noté en mathématiques. On définit le type correspondant ainsi :
type natP = Z | S of natP 1
Question 16 ♣ On dénit
let rec u n = if n< = 1 then 1 else (u (n-1))+(v (n-1)) and v n = u (n-1) L’objectif de cet exercice est d’explorer la notion de multiple dans natP, sans utiliser la multipli-
A quoi est égale (u 4): cation. Dans les implémentations demandées, l’utilisation des opérateurs arithmétiques + et ∗ est
interdite.
A 1 C 3 E 8
Le double d’un naturel est défini comme suit :
B (u 3)+(v 3) D 5 F (v 5)
spécification 1
Question 17 ♣ Soient f et g dénies par let f x = 2*x and let g y = y+6 . Quelle est la valeur
profil 𝑑𝑜𝑢𝑏𝑙𝑒 : 𝑛𝑎𝑡𝑃 → 𝑛𝑎𝑡𝑃
de g (g (f (g 9)))
sémantique 𝑑𝑜𝑢𝑏𝑙𝑒(𝑛) est le naturel de Peano correspondant à 2 × 𝑛.
A 64 B 201 C 1024 D 42 E 2019 F 32 ex. et prop. (i) 𝑑𝑜𝑢𝑏𝑙𝑒 𝑆(𝑆 𝑍) = 𝑆(𝑆(𝑆(𝑆 𝑍)))

Question 18 ♣ On dénit la fonction chevauche par

let chevauche (bi1,bs1 :int*int) (bi2,bs2 :int*int) : bool = Q1. (2pt) Compléter les équations définissant la fonction 𝑑𝑜𝑢𝑏𝑙𝑒 :
(bi1<bi2 && bi2<bs1 && bs1<bs2) || (bi2<bi1 && bi1<bs2 && bs2<bs1) Indication On pourra utiliser la propriété mathématique 2(𝑝 + 1) = 2𝑝 + 2
   
Parmi les expressions suivantes lesquelles valent true.
  
(1) 𝑑𝑜𝑢𝑏𝑙𝑒 (𝑍) = 𝑍
   
A chevauche (4,5) (5,8) C chevauche (4,5) (2,3) E chevauche (2,3) (4,5)
B chevauche (2,8) (4,5) D chevauche (0,4) (3,5) F chevauche (4,8) (3,5)    
(2) 𝑑𝑜𝑢𝑏𝑙𝑒 (𝑆 𝑝) = 𝑆(𝑆(𝑑𝑜𝑢𝑏𝑙𝑒 𝑝))

Correction
(1) = 0.5 ; (2) = 1.5

Q2. (1pt) Implémenter 𝑑𝑜𝑢𝑏𝑙𝑒.

Correction
let rec double (n:natP) : natP = 1

match n with 2

| Z -> Z 3

| S n -> S(S(double n)) 4

Q3. (2pt) Que doit-on modifier dans l’implémentation précédente pour obtenir une
fonction qui retourne le triple de son paramètre (un naturel de Peano) ?

Correction
Son nom, et on ajoute un S autour de l’appel réc.

On souhaite généraliser l’approche des questions précédentes en définissant la fonction sui-

vante :

6/15 INF 201 algo. et prog. fonctionnelle

y [git] • Branche master @ 621a931 • Version v1.4.1-polys-I-II ( 14/03/2022 ) par François Puitg y [git] • Branche master @ 621a931 • Version v1.4.1-polys-I-II ( 14/03/2022 ) par François Puitg
VERSION ENSEIGNANTS – NE PAS DIFFUSER 3.1 The type 𝑐𝑎𝑟𝑡𝑒

VERSION ENSEIGNANTS – NE PAS DIFFUSER

spécification 2
def

profil 𝑘𝑢𝑝𝑙𝑒 : N → 𝑛𝑎𝑡𝑃 → 𝑛𝑎𝑡𝑃 𝑒𝑛𝑠𝑒𝑖𝑔𝑛𝑒 =

def
{𝑃𝑖𝑞𝑢𝑒, 𝑇𝑟𝑒𝑓̀ 𝑙𝑒, 𝐶𝑜𝑒𝑢𝑟, 𝐶𝑎𝑟𝑟𝑒𝑎𝑢}
𝑝𝑒𝑡𝑖𝑡𝑒 = {7, 8, 9, 10} × 𝑒𝑛𝑠𝑒𝑖𝑔𝑛𝑒
sémantique (𝑘𝑢𝑝𝑙𝑒 𝑘 𝑛) est le naturel de Peano correspondant à 𝑘 × 𝑛. def
𝑡𝑒𝑡𝑒
̂ = {𝑉𝑎𝑙𝑒𝑡, 𝐷𝑎𝑚𝑒, 𝑅𝑜𝑖, 𝐴𝑠}
ex. et prop. (i) (𝑘𝑢𝑝𝑙𝑒 3 𝑆(𝑆 𝑍)) = 𝑆(𝑆(𝑆(𝑆(𝑆(𝑆 𝑍))))) ℎ𝑜𝑛𝑛𝑒𝑢𝑟
def
= 𝑡𝑒𝑡𝑒
̂ × 𝑒𝑛𝑠𝑒𝑖𝑔𝑛𝑒
def
𝑐𝑜𝑢𝑙𝑒𝑢𝑟 = {𝑅𝑜𝑢𝑔𝑒, 𝑁𝑜𝑖𝑟}
Pour cela, on spécifie la fonction intermédiaire suivante :
On souhaite utiliser ces ensembles pour définir l’ensemble des 𝑐𝑎𝑟𝑡𝑒𝑠 qui comporte les petites,
spécification 3 les honneurs et deux jokers : un rouge et un noir.
profil 𝑝𝑙𝑢𝑠𝑘 : N → 𝑛𝑎𝑡𝑃 → 𝑛𝑎𝑡𝑃
sémantique (𝑝𝑙𝑢𝑠𝑘 𝑘 𝑛) est le naturel de Peano correspondant à 𝑛 incrémenté 𝑘 fois. 3.1 Le type 𝑐𝑎𝑟𝑡𝑒
ex. et prop. (i) (𝑝𝑙𝑢𝑠𝑘 2 𝑆(𝑍)) = 𝑆(𝑆(𝑆 𝑍))
Q7. (5pt) Compléter les définitions des ensembles mathématiques ci-après ainsi que leur
implémentation de manière à modéliser le type carte avec les deux jokers :
Q4. (2pt) Implémenter 𝑝𝑙𝑢𝑠𝑘. Dans cette question, l’utilisation de match est interdite.    
𝑐𝑎𝑟𝑡𝑒 = {𝑃(𝑥) | 𝑥 ∈ 𝑝𝑒𝑡𝑖𝑡𝑒} ∪ {𝐻(𝑥) | 𝑥 ∈ ℎ𝑜𝑛𝑛𝑒𝑢𝑟 
 
def
} ∪ 𝐽(𝑥) | 𝑥 ∈ 𝑐𝑜𝑢𝑙𝑒𝑢𝑟
Correction

Pique |Trefle | Coeur | Carreau

let rec plusk (k:int (* ⩾ 0 *)) (n:natP) : natP =
type enseigne =
1
1
if k = 0 then
int (* restreint à {7,...,10} *) * enseigne
 
type petite =
2
2
n

 3

3

else type tete = Valet | Dame | Roi | As

 
4

 
S(plusk (k-1) n) 5
type honneur = tete * enseigne 4

type couleur = Noir | Rouge 

5
Si implémentation avec match correcte, donner 1pt.
  6

type carte = P of petite | H of honneur
| J of couleur
7

Q5. (2pt) Implémenter 𝑘𝑢𝑝𝑙𝑒.

Correction Correction
Par ordre d’apparition : 0.25, 0.5, 0.5, 0.75, 0.5, 0.5, 1, 1
let rec kuple (k:int (* ⩾ 0 *)) (n:natP) : natP = 1

match n with 2
Q8. (2pt)
| Z -> Z 3

| S n -> plusk k (kuple k n) 4

1. Quel nom donne-t-on aux types tels que 𝑐𝑎𝑟𝑡𝑒 ?

2. Quel nom donne-t-on aux types tels que 𝑒𝑛𝑠𝑒𝑖𝑔𝑛𝑒 ou 𝑐𝑜𝑢𝑙𝑒𝑢𝑟 ?

Q6. (1pt) Donner une autre implémentation – non récursive – de la fonction 𝑡𝑟𝑖𝑝𝑙𝑒.
3. Quel nom donne-t-on aux types tels que ℎ𝑜𝑛𝑛𝑒𝑢𝑟 ?
Correction
4. Donner l’expression OCaml désignant la carte correspondant au joker rouge.
let triple : natP -> natP = 1

kuple 3 2
Correction
On met bien sûr les points si ça n’est pas à l’odre supérieur.
0.5 pt chaque

 
1. type somme
3 Exercice : bataille Normande
 
25 pts 2. type énuméré (c’est aussi un type somme)

Exo_et_Pb/Types_somme/Bataille_Normande/ 3. type produit

On adopte la définition mathématique des ensembles suivants : 4. J(Rouge)

INF 201 algo. et prog. fonctionnelle 7/15 8/15 INF 201 algo. et prog. fonctionnelle

[git] • Branche master @ 621a931 • Version v1.4.1-polys-I-II ( 14/03/2022 ) par François Puitg [git] • Branche master @ 621a931 • Version v1.4.1-polys-I-II ( 14/03/2022 ) par François Puitg
VERSION ENSEIGNANTS – NE PAS DIFFUSER 3.2 Rank and color of a carte 3.3 The Normandy Battle

VERSION ENSEIGNANTS – NE PAS DIFFUSER

3.2 Rang et couleur d’une carte spécification 2
Le rang d’une carte 𝑐 désigne la place allouée à 𝑐 selon un ordre arbitraire, qui dépend du jeu profil 𝑐𝑜𝑢𝑙 : 𝑐𝑎𝑟𝑡𝑒 → 𝑐𝑜𝑢𝑙𝑒𝑢𝑟
considéré. Dans la bataille Normande, le rang des cartes est le suivant : sémantique 𝑐𝑜𝑢𝑙(𝑐) est la couleur de 𝑐.
𝑐 : 7 < 8 < 9 < 10 < Valet < Dame < Roi < As < Joker
ex. et prop. (i) 𝑐𝑜𝑢𝑙(𝑃(7, 𝐶𝑎𝑟𝑟𝑒𝑎𝑢)) = 𝑅𝑜𝑢𝑔𝑒
𝑟𝑎𝑛𝑔(𝑐) : 1 2 3 4 5 6 7 8 9
(ii) 𝑐𝑜𝑢𝑙(𝐻(𝐴𝑠, 𝑃𝑖𝑞𝑢𝑒)) = 𝑁𝑜𝑖𝑟
Indication L’enseigne et la couleur n’ont pas d’importance dans le calcul du rang.
Q11. (5pt) Implémenter la fonction 𝑐𝑜𝑢𝑙.
Q9. (1.5pt) Compléter la spécification de la fonction 𝑟𝑎𝑛𝑔 ci-dessous.
Indication Ne pas oublier le cas des jokers.
spécification 1
 
profil 𝑟𝑎𝑛𝑔 : 𝑐𝑎𝑟𝑡𝑒 → {1 , … , 9}  Correction
sémantique profil = 0.5 ; 2.25 pour chaque match
 
𝑟𝑎𝑛𝑔(𝑐) est la place de 𝑐 dans l’ordre décrit ci-dessus.
let couleur (c:carte) : couleur =
ex. et prop.

 
1
(i) 𝑟𝑎𝑛𝑔( 𝑃(8, -) )=2 match c with 2

   
| P(-,e) | H(-,e) -> (match e with
(ii) 𝑟𝑎𝑛𝑔( 𝐽 - )=9 3

(iii) 𝑟𝑎𝑛𝑔(𝑃(10, 𝑃𝑖𝑞𝑢𝑒)) = 4 


| Pique | Trefle -> Noir 4

(iv) 𝑟𝑎𝑛𝑔(𝐻(𝐴𝑠, 𝐶𝑜𝑒𝑢𝑟)) = 8 

| Carreau | Coeur-> Rouge) 5

| J(cl) -> cl 6

Correction
profil = 0.5 ; ex = 0.25 chaque
3.3 La bataille
Q10. (4.5pt) Compléter la réalisation de 𝑟𝑎𝑛𝑔 : Dans le jeu de la bataille Normande, on applique les règles suivantes pour comparer les cartes
des deux joueurs et savoir ainsi qui remporte le pli. Soit 𝑐1 la carte du joueur 1 et 𝑐2 la carte du
réalisation 1
joueur 2 :
algorithme analyse par cas par filtrage
implément. • si 𝑐1 est strictement supérieure à 𝑐2 alors 𝑐1 remporte le pli
⋮
• si 𝑐1 est strictement inférieure à 𝑐2 alors 𝑐1 perd le pli

Correction
• sinon, les cartes sont égales et il y a bataille.
profil = 0.5 ; 2 pour chaque match
let rang (c:carte) : int (* restreint à 1 ,…, 9 *) = 1
L’ordre utilisé pour comparer deux cartes est le suivant :
match c with 2

| P(p,-) -> p - 6 3
1. On compare d’abord les cartes selon leur rang (au sens de l’ordre décrit au paragraphe
| H(h,-) -> (match h with 4
précedent) ;
| Valet -> 5 5

| Dame -> 6 6

| Roi -> 7 7
2. à rang égal, les cartes de couleur noire sont inférieures aux cartes de couleur rouge ;
| As -> 8) 8

| J - -> 9 9 3. si les cartes ont même rang et même couleur, elle sont dites égales.

La couleur d’une carte est spécifiée ainsi : Pour représenter les trois résultats possibles d’une bataille entre deux cartes, on définit le type
énuméré suivant :

type resultat = Gagne | Perdu | Bataille 1

INF 201 algo. et prog. fonctionnelle 9/15 10/15 INF 201 algo. et prog. fonctionnelle

[git] • Branche master @ 621a931 • Version v1.4.1-polys-I-II ( 14/03/2022 ) par François Puitg [git] • Branche master @ 621a931 • Version v1.4.1-polys-I-II ( 14/03/2022 ) par François Puitg
VERSION ENSEIGNANTS – NE PAS DIFFUSER

VERSION ENSEIGNANTS – NE PAS DIFFUSER

Q14. (1pt) Définir les constantes troisTs (3 toises) et douzePc (12 pouces) de type
Q12. (7pt) Spécifier (profil, sémantique, exemples) puis implémenter une fonction longueur.
𝑗𝑜𝑢𝑒𝑟 qui prend en paramètres deux cartes 𝑐1 et 𝑐2 et qui retourne le résultat Gagne si
𝑐1 remporte le pli, Perdu si 𝑐1 perd le pli ou Bataille s’il y a bataille selon les règles Correction
énoncées ci-dessus. 0.5 chaque
Indication Réutiliser les fonctions des questions précédentes (sans les réécrire). let troisTs : longueur = Toise 3 1

and douzePc : longueur = Pouce 12 2

Correction partielle
profil = 0.75 ; sémant = 1 ; ex = 0.75 ; implem = 4.5
let jouer (c1:carte) (c2:carte) : resultat = 1

let r1 = rang c1 and r2 = rang c2 in 2

if r1 > r2 then 3

Gagne 4 La modélisation précédente est assez grossière ; par exemple, elle ne permet pas de représenter
else if r1 < r2 then 5 la longueur « trois toises, six pieds et quinze pouces ».
Perdu 6

else (* r1 = r2 *) 7

match couleur c1, couleur c2 with 8

On souhaite donc être plus précis en créant un type produit, nommé 𝑙𝑜𝑛𝑔𝑢𝑒𝑢𝑟𝐷 , représentant
| Rouge, Noir -> Gagne 9
les longueurs détaillées qui sont des triplets d’entiers naturels dénombrant les toises, pieds et pouces
| Noir, Rouge -> Perdu 10
associés à une longueur donnée.
| - -> Bataille 11

Q15. (2pt) En définissant les types 𝑡𝑜𝑖𝑠𝑒, 𝑝𝑖𝑒𝑑 et 𝑝𝑜𝑢𝑐𝑒 comme des types synonymes,

 
implémenter le type 𝑙𝑜𝑛𝑔𝑢𝑒𝑢𝑟𝐷 .
4 Exercice : toise, pied et pouce
 
25 pts
Correction
Exo_et_Pb/Types_somme/Toise_pied_pouce/ 0.25 pour chaque synonyme, 1.25 pour longueurD
type toise = nat 1

Dans un ancien système de mesure de longueurs, une toise1 vaut 6 pieds et un pied vaut 12 pouces. type pied = nat 2

On étudie l’information associée à une mesure de longueur au moyen de cet ancien système d’unités. type pouce = nat 3

type longueurD = toise * pied * pouce 4

Dans un premier temps, on modélise une longueur à l’aide de constructeurs faisant référence à
une unité – soit la toise, soit le pied, soit le pouce – chaque constructeur comportant un paramètre
N
entier naturel ( ) exprimant la longueur dans l’unité correspondante. Par exemple :
Q16. (1pt) Définir les constantes 𝑡𝑟𝑜𝑖𝑠𝑇𝑠𝐷 (trois toises) et 𝑑𝑜𝑢𝑧𝑒𝑃𝑐𝐷 (douze pouces) de
(i) trois toises : Toise(3) type 𝑙𝑜𝑛𝑔𝑢𝑒𝑢𝑟𝐷 .

(ii) six pieds : Pied(6) Correction

(iii) quinze pouces : Pouce(15) 0.5 chaque
let troisTsD : longueurD = (3,0,0) 1
Q13. (2pt) Implémenter un type somme, nommé longueur, permettant de modéliser and douzePcD : longueurD = (0,0,12) 2
ce système de mesure. On veillera à préciser les éventuelles contraintes.

Correction
0.5 pour chaque constructeur, 0.5 pour contrainte
type nat = int (* ⩾ 0 *) 1

type longueur = Toise of nat | Pied of nat | Pouce of nat 2

On souhaite permettre à l’utilisateur d’utiliser l’une ou l’autre des représentations en définissant

1
environ 2 mètres des fonctions de conversion d’une représentation à l’autre.

INF 201 algo. et prog. fonctionnelle 11/15 12/15 INF 201 algo. et prog. fonctionnelle

[git] • Branche master @ 621a931 • Version v1.4.1-polys-I-II ( 14/03/2022 ) par François Puitg [git] • Branche master @ 621a931 • Version v1.4.1-polys-I-II ( 14/03/2022 ) par François Puitg
VERSION ENSEIGNANTS – NE PAS DIFFUSER

VERSION ENSEIGNANTS – NE PAS DIFFUSER

Q17. (1.5pt) Donner le profil et implémenter une fonction 𝑙𝑜𝑛𝑔𝑉𝑙𝑜𝑛𝑔𝐷 qui convertit une distinctes. Pour éviter cette potentielle ambiguïté, on cherche à construire un représentant unique,
variable de type 𝑙𝑜𝑛𝑔𝑢𝑒𝑢𝑟 en sa valeur associée de type 𝑙𝑜𝑛𝑔𝑢𝑒𝑢𝑟𝐷 . Par exemple, on devra dit canonique, grâce à la propriété suivante :
pouvoir vérifier que les assertions suivantes sont vraies :

(i) 𝑙𝑜𝑛𝑔𝑉𝑙𝑜𝑛𝑔𝐷 (𝑡𝑟𝑜𝑖𝑠𝑇𝑠) = 𝑡𝑟𝑜𝑖𝑠𝑇𝑠𝐷

(ii) 𝑙𝑜𝑛𝑔𝑉𝑙𝑜𝑛𝑔𝐷 (𝑑𝑜𝑢𝑧𝑒𝑃𝑐) = 𝑑𝑜𝑢𝑧𝑒𝑃𝑐𝐷

Correction
On ne sanctionne pas l’abscence de profil si ligne 1 correcte
let longVlongD (x:longueur) : longueurD = 1

match x with 2

| Toise y -> (y,0,0) 3 Soit (-, 𝑝𝑑, 𝑝𝑐) ∈ 𝑙𝑜𝑛𝑔𝑢𝑒𝑢𝑟𝐷 ; (-, 𝑝𝑑, 𝑝𝑐) est canonique si et seulement si 0 ⩽ 𝑝𝑑 ⩽ 5 et
| Pied y -> (0,y,0) 4 0 ⩽ 𝑝𝑐 ⩽ 11.
| Pouce y -> (0,0,y) 5

On définit la notion de rang d’une unité de cet ancien système de mesure : la toise est d’un rang
supérieur au pied ; le pied est d’un rang supérieur au pouce.
Q18. (1.5pt) Implémenter la fonction 𝑙𝑜𝑛𝑔𝐷 𝑉𝑙𝑜𝑛𝑔 qui, étant donnée une 𝑙𝑜𝑛𝑔𝑢𝑒𝑢𝑟𝐷 , re-
tourne la 𝑙𝑜𝑛𝑔𝑢𝑒𝑢𝑟 correspondant à l’unité de plus haut rang. Par exemple, on devra
pouvoir vérifier que les assertions suivantes sont vraies :

(i) 𝑙𝑜𝑛𝑔𝐷 𝑉𝑙𝑜𝑛𝑔(2, 5, 12) = 𝑇𝑜𝑖𝑠𝑒(2)

Q20. (7pt) Implémenter une fonction 𝑟𝑒𝑝𝑟𝐶𝑎𝑛 ∶ 𝑙𝑜𝑛𝑔𝑢𝑒𝑢𝑟𝐷 → 𝑙𝑜𝑛𝑔𝑢𝑒𝑢𝑟𝐷 qui construit le
(ii) 𝑙𝑜𝑛𝑔𝐷 𝑉𝑙𝑜𝑛𝑔(0, 5, 12) = 𝑃𝑖𝑒𝑑(5) représentant canonique d’une longueur détaillée donnée. Par exemple, on devra pouvoir
vérifier que les assertions suivantes sont vraies :
(iii) 𝑙𝑜𝑛𝑔𝐷 𝑉𝑙𝑜𝑛𝑔(𝑑𝑜𝑢𝑧𝑒𝑃𝑐𝐷 ) = 𝑑𝑜𝑢𝑧𝑒𝑃𝑐
(i) 𝑟𝑒𝑝𝑟𝐶𝑎𝑛(𝑑𝑜𝑢𝑧𝑒𝑃𝑐𝐷 ) = (0, 1, 0)
Correction (ii) 𝑟𝑒𝑝𝑟𝐶𝑎𝑛(3, 6, 10) = (4, 0, 10)
let longDVlong (t,pd,pc : longueurD) : longueur = 1
(iii) 𝑟𝑒𝑝𝑟𝐶𝑎𝑛(4, 0, 10) = (4, 0, 10)
if t > 0 then 2

Toise t 3

else if pd > 0 then 4 Correction

Pied pd 5
profil (+ let éventuel pour décomposer le triplet) = 1 ; reste = 6
else 6
let reprCan (t,pd,pc : longueurD) : longueurD = 1
Pouce pc 7
let quo-pc, rst-pc = pc/12, pc mod 12 in 2

let quo-pd, rst-pd = (pd+quo-pc)/6, (pd+quo-pc) mod 6 in 3

(t+quo-pd, rst-pd, rst-pc) 4

On s’intéresse maintenant à l’unicité des représentations des longueurs en toise, pied et pouce.
On rappelle qu’une toise vaut 6 pieds et qu’un pied vaut 12 pouces.
Q19. (1pt) Donner deux valeurs différentes de type 𝑙𝑜𝑛𝑔𝑢𝑒𝑢𝑟𝐷 représentant la même
longueur « trois toises, six pieds, dix pouces ».

Correction
(3, 6, 10), (4, 0, 10) ; 0.5 chaque

La question précédente montre qu’une longueur donnée peut avoir plusieurs représentations Finalement, pour que tout cela soit lisible par un opérateur humain :

INF 201 algo. et prog. fonctionnelle 13/15 14/15 INF 201 algo. et prog. fonctionnelle

[git] • Branche master @ 621a931 • Version v1.4.1-polys-I-II ( 14/03/2022 ) par François Puitg [git] • Branche master @ 621a931 • Version v1.4.1-polys-I-II ( 14/03/2022 ) par François Puitg
VERSION ENSEIGNANTS – NE PAS DIFFUSER
Q21. (8pt) conclure en implémentant la fonction 𝑙𝑜𝑛𝑔𝐷 𝑉𝑠𝑡𝑟 qui génère une chaîne de
caractères décrivant textuellement la valeur d’une longueur détaillée, et ce sous un format
de représentation unique ; par exemple, « 3 toise 2 pied » (on ignorera les ‘s’ du pluriel).
On devra notamment pouvoir vérifier que les assertions suivantes sont vraies :

(i) 𝑙𝑜𝑛𝑔𝐷 𝑉𝑠𝑡𝑟(3, 6, 10) = ”4 𝑡𝑜𝑖𝑠𝑒 10 𝑝𝑜𝑢𝑐𝑒 ”

(ii) 𝑙𝑜𝑛𝑔𝐷 𝑉𝑠𝑡𝑟(𝑑𝑜𝑢𝑧𝑒𝑃𝑐𝐷 ) = ”1 𝑝𝑖𝑒𝑑 ”

(iii) 𝑙𝑜𝑛𝑔𝐷 𝑉𝑠𝑡𝑟(𝑙𝑜𝑛𝑔𝑉𝑙𝑜𝑛𝑔𝐷 𝑡𝑟𝑜𝑖𝑠𝑇𝑠) = ”3 𝑡𝑜𝑖𝑠𝑒 ”

Indication. Attention aux espaces !

Rappels. Une chaîne de caractères est de type string (par exemple, let s :
string = ”INF2-1 rocks!”). La concaténation de deux chaînes est implémentée
par l’opérateur ^ (par exemple, s = (”INF2-1” ^ ” rocks!”) est vrai). La fonction
prédéfinie string-of-int ∶ Z
→ 𝑠𝑡𝑟𝑖𝑛𝑔 permet de convertir un entier en la chaîne de
caractères correspondante.

Correction
profil = 0.5 ; appel à reprCan et décomposition du triplet = 1.5 ; le reste = 6
On ne sanctionne pas l’abscence d’iVs qui n’est là que pour la lisibilité.
let longDVstr (x:longueurD) : string = 1

let iVs = string-of-int and t,pd,pc = reprCan x in 2

let toise = if t > 0 then (iVs t) ^ ” toise ” else ”” 3

and pied = if pd > 0 then (iVs pd) ^ ” pied ” else ”” 4

and pouce = if pc > 0 then (iVs pc) ^ ” pouce ” else ”” in 5

toise ^ pied ^ pouce 6

INF 201 algo. et prog. fonctionnelle 15/15

[git] • Branche master @ 621a931 • Version v1.4.1-polys-I-II ( 14/03/2022 ) par François Puitg