\[ \DeclareMathOperator{\even}{even} \DeclareMathOperator{\odd}{odd} \DeclareMathOperator{\true}{true} \DeclareMathOperator{\false}{false} \]
En salle machine, nous vous recommandons d’utiliser Eclipse configuré avec le plugin OCaml
. Pour cela, commencez par démarrer Eclipse. Pourq installer le plugin OCaml
, allez dans le menu Help -> Install New Software… Une boîte de dialogue apparaîtra. À partir de cette dernière, ajoutez une nouvelle source de plugin en cliquant sur le bouton Add...
(dans la section Work with...
). Le nom de la source (champ Name
de la nouvelle boîte de dialogue) importe peu — utilisez OCaml
par example. La source (champ Location
) doit être positionné sur
Validez la nouvelle source. Dans la liste sous la section Work with...
, le plugin OcaIDE
devrait apparaître. Sélectionnez le puis validez. Eclipse vous demandera de confirmer l’installation de OcaIDE
et d’accepter sa licence. Une fois l’installation terminée, Eclipse vous proposera de redémarrer. Acceptez.
(Nous fournissons également des instructions pour installer un environnement de développement pour OCaml chez vous).
Pour cette session, nous vous recommandons d’utiliser un top-level graphique comme celui de OcaIDE ou ocaml-top. Ouvrez votre top-level OCaml. Vous verrez alors apparaître une invite de commandes telle que:
À partir de là, il vous est possible d’entrer des expressions OCaml qui seront interprétées au fil de l’eau par le top-level – ces expressions doivent se terminer par un ;;
afin d’indiquer que vous avez fini votre saisie. E.g., taper la commande 42;;
puis appuyez sur entrée. Le top-level évalue l’expression, puis imprime le résultat accompagné du type de l’expression :
Vous pouvez aussi essayer avec 21+21
:
Notez que l’expression n’a pas à être saisie sur une seule ligne comme avec :
D’où l’importance des ;;
finaux ! (Ces derniers disparaitront lorsque nous utiliserons OCaml comme compilateur et non plus comme interpréteur)
Il est également possible de définir des variables via l’instruction let
, par exemple :
Ici, OCaml vous indique la création d’une variable x
de type int
et initialisée à 3
. Cette variable peut ensuite être utilisée dans les expressions, comme dans :
Notez que les variables en OCaml sont immuables : x
vaut 3
et il n’est plus possible de changer sa valeur. Pas contre, vous pouvez redéfinir x
:
Ici, nous définissons une nouvelle variable x
mais cette fois ci initialisée à 4
et qui cache la première définition de x
. La différence est subtile et nous reviendrons dessus plus tard lors d’exerices sur l’ordre supérieur et les clôtures.
De la même manière, la construction let
nous permet de définir des fonctions :
Ici, f
est une fonction (indiqué par le <fun>
) de type int -> int
(c’est-à-dire qui prend un argument de type int
et renvoie une valeur de type int
). Il est à noter que le type de f
a été inféré. Optionnellement, il est possible d’indique le type des arguments ou du retour d’une fonction :
Le faire peut parfois aider à comprendre une erreur de typage (due à une erreur de programmation) en guidant l’inférence de type – notamment lors du typage de fonctions récursives.
De même qui pour les variables, f
peut ensuite être utilisée dans les expressions :
Notez que l’application en OCaml se fait par juxtaposition : il n’y a pas de parenthèses.
On peut bien sûr définir des fonctions à plusieurs arguments :
et le corps d’une fonction peut utiliser des fonctions ou des variables précédemment définies :
# let x = 3
val x : int = 3
# let f a = a * a
val f : int -> int = <fun>
# let h a = f a + x
val h : int -> int = <fun>
# h 2
- : int = 7
# let x = 4
val x : int = 4
# h 2
- : int = 7
Notez que cet exemple montre bien qu’une variable est immuable. Redéfinir x
ne change pas le comportement de h
!
Donner le type des expressions suivantes (lorsque possible) :
01) 42
02) 42.0
03) 42,0
04) 42;0
05) true
06) ()
07) []
08) [1]
09) [1, true]
10) [1; true]
11) 1 + 1
12) 1. + 1
13) 1. +. 0.
14) x
15) 'x'
16) "x"
17) 0 = 1
Donner des exemples d’expressions OCaml ayant les types suivants :
Pour chacune des expressions ci-dessous, donner la valeur retournée par l’interpréteur OCaml.
01) let a = 1 in a + 2
02) let a = 1 in a + 2; a
03) (let a = 1 in a + 2); a
04) let a = 7 in let b = a in a + b
05) let a = 1 in let a = 2 in a
06) let a = 1 in (let a = 2 in ()); a
07) let f x = fun y -> x * y in let g = f 3 in g 5
Écrire une fonction pmap
telle que pmap f g
retourne une fonction prenant une paire et retournant la paire obtenue à partir de la première par application de f
(resp. g
) sur sa première (resp. seconde) composante. Quel est le type de pmap
?
Écrire une fonction idc : int -> (int -> int) * (int -> int)
telle que idc x
retourne une paire de fonctions, la première (resp. seconde) implémentant la fonction d’incrément (resp. décrément) par x
.
Écrire une fonction de composition, c’est-à-dire une fonction comp
telle que comp f g x
calcule f (g x)
. Quel est le type de comp ? Que fait la fonction suivante ?
Écrire une fonction récursive fact : int -> int
calculant la factorielle de son entrée. Quel est le comportement de votre fonction si son argument est négatif ?
Une fonction récursive terminale est une fonction où l’appel récursif est la dernière instruction à être exécutée par l’appelant, c’est-à-dire que la fonction appelant n’utilise pas son résultat dans un calcul, mais le renvoie directement. Une fonction récursive terminale peut-être exécutée en place, sa pile d’exécution n’ayant pas besoin d’être sauvée. Dans ce cas, il n’y a pas de risque d’épuisement de la pile (stack overflow). Une technique standard pour transformer l’implémentation d’une fonction récursive en une implémentation récursive terminale est d’ajouter un argument supplémentaire à la fonction qui contienne le résultat partiel d’évaluation. Écrire une fonction récursive terminale fact_r : int -> int -> int
, telle que fact_r r x
calcule \(r \times x!\). En déduire une implémentation récursive terminale de fact.
Écrire la fonction exp : int -> int -> int
qui calcule l’exponentielle entière (de manière naïve puis en utilisant la récursion terminale). Combien de multiplications exécute exp x n
en fonction de n
? Écrire une autre implémentation de exp qui a un coût logarithmique en nombre de multiplications en utilisant le fait que \(x^{2n} = (x^n)^2\).
Écrire deux fonctions mutuellement récursives even, odd : int -> bool
selon les spécifications suivantes :
\[\begin{aligned} \even : n \mapsto & \left\{ \begin{aligned} \true && \text{si $n = 0$} \\ \odd(n-1) && \text{si $n > 0$} \\ \even(-n) && \text{si $n < 0$} \end{aligned} \right. & \odd : n \mapsto & \left\{ \begin{aligned} \false && \text{si $n = 0$} \\ \even(n-1) && \text{si $n > 0$} \\ \odd(-n) && \text{si $n < 0$} \end{aligned} \right. \end{aligned}\]
Écrire une fonction récursive parity : bool -> int -> bool
récapitulant les deux fonctions précédentes.
Écrire une fonction fibo : int -> int
implémentant la suite de Fibonacci, dont on rappelle la définition :
\[\left\{ \begin{aligned} \mathcal{F}(0) &= 1 \\ \mathcal{F}(1) &= 1 \\ \mathcal{F}(n+2) &= \mathcal{F}(n+1) + \mathcal{F}(n) \end{aligned} \right.\]
On prendra \(\mathcal{F}(n) = 0\) pour \(n < 0\). Combien de fois un appel à fibo 15
appelle-t-il (calcule-t-il) fibo 10
? (Si votre réponse est 1
, bravo !) Quelle conclusion en tirez-vous quant à la complexité d’exécution de votre code ?
On se propose de pallier ce problème en utilisant la technique de « mémoïsation ». La mémoïsation est une technique d’optimisation de code dont le but est de diminuer le temps d’exécution d’un programme en mémorisant les valeurs retournées. Le cas de Fibonacci est très particulier dans la mesure où il ne nécessite que les deux derniers calculs pour passer au rang suivant (on verra un cas plus général par la suite).
Écrire une fonction fibo_r : int -> int -> int -> int
telle que fibo_r a b n
retourne \(\mathcal{F}(n+p)\), en supposant que a
et b
sont resp. égaux à \(\mathcal{F}(p)\) et \(\mathcal{F}(p+1)\) initialement. Au cours de son exécution, votre implémentation ne devra pas se rappeler plus d’une fois avec la même valeur pour n
. En déduire une seconde implémentation de fibo.
Que pouvez dire également, à propos de votre nouvelle implémentation, quant à sa récursivité terminale ?
Écrire une fonction sum : int list -> int
qui calcule la somme des éléments d’une liste.
Écrire une fonction gsum
telle que gsum f s
retourne la somme des f x
pour x
parcourant s
(on suppose que f
retourne un entier). Quel est le type de gsum
? Donner une implémentation directe de sum
(question précédente) à partir de gsum
.
Écrire une fonction zfilter : int list -> int list
qui retire tous les éléments négatifs de son entrée, en préservant l’ordre des éléments. Écrire une fonction filter p s
, où p
est une prédicat de filtrage, qui retire tous les éléments de s
qui ne valide pas p
(c’est-à-dire telle que p x
retourne false
), tout en préservant l’ordre des éléments. Quel est le type de filter
? Récrire zfilter
à partir de filter
.
Écrire une fonction insert x s
qui insère x
dans une liste d’entiers s
, supposée triée par ordre croissant. En déduire une fonction de tri sort qui procède par insertions successives : le tri obtenu est appelé tri par insertion. Généraliser insert
et sort
afin qu’elles travaillent sur des listes de type quelconque, la relation d’ordre étant donnée en argument. Écrire un prédicat sorted : ('a -> 'a -> bool) -> 'a list -> bool
telle que sorted leq s
retourne true
si et seulement si s est une liste triée pour la relation leq
. Vérifier sur des exemples que sorted (<=) (sort (<=) s)
.
(difficile) Écrire une fonction perm : 'a list -> 'a list list
qui retourne toutes les permutations (avec doublons) de la liste donnée en entrée.
Définir un type record représentant les nombres complexes – on utilisera les float pour représenter les scalaires. Définir les quatre opérations de base :
Définir, à l’aide d’un record, un type date représentant une date (jour, mois, année). Écrire des fonctions d’accès aux différents champs d’une date en utilisant un filtrage partiel. Écrire une fonction nextday : date -> date
qui calcule la date du lendemain de son argument.
On se propose de définir un type pour représenter des cartes à jouer (jeu français). Définir un type somme suit
représentant les couleurs des cartes (coeur, carreau, trèfle, pique). Définir ensuite un type cvalue
représentant les valeurs possibles d’une carte (as, simple de 2 à 10, valet, dame, roi), puis un type card qui représente une carte à jour. Donner les listes de toutes cartes d’un jeu de 52/32 cartes – on pourra faire générer la liste par une fonction ! Écrire une fonction belote_1 : bool -> cvalue -> int
qui donne le nombre de point, pour la belote, d’une carte – le booléen indiquant si la carte est dans la couleur de l’atout ou non. En déduire une fonction belote : suit -> card list -> int
qui retourne le nombre de points d’une main – le premier argument étant ici la couleur de l’atout.
Atout | Non Atout |
---|---|
Valet : 20 points | As : 11 points |
9 : 14 points | 10 : 10 points |
As : 11 points | Roi : 4 points |
10 : 10 points | Dame : 3 points |
Roi : 4 points | Valet : 2 points |
Dame : 3 points | 9 : 0 points |
8 : 0 points | 8 : 0 points |
7 : 0 points | 7 : 0 points |
Pour chacune des expressions ci-dessous, donner la valeur de la référence r
après leur exécution :
Écrire une fonction counter : int -> (unit -> int)
telle que counter x
retourne un compteur initialisé à 0
et d’incrément égal à x, c’est-à-dire retourne une fonction telle que les appels successifs à cette dernière retourne 0
, x
, 2*x
, 3*x
… Chaque compteur devra fonctionner en isolation : la création d’un nouveau compteur ne devra pas modifier le comportement des compteurs précédemment créés.