1. Installation d’OCaml Installez OCaml sur votre ordinateur. Pour installer OCaml, il est recommandé d’installer opam le gestionnaire de paquet d’OCaml d’abord, qui vous permettra ensuite d’installer une version spécifique d’OCaml.
1.1 Installation d’OPAM Sur Linux Installez le paquet opam de votre distribution :
apt-get install opam sur Ubuntu et Debian référez-vous à la documentation de votre distribution pour les autres Sur MacOS Installez le paquet opam avec Brew (brew install opam) ou MacPorts (port install opam), ou lancez la commande suivante :
Pour ce laboratoire, nous allons utiliser les exemples typing.ml et inference.ml du dépôt d’exemples.
Ce labo réplique certains exercices du laboratoire précédente, mais en faisant des modifications dans les exemples de typages plutôt que dans l’interpréteur.
Vérification de types Types de fonctions Soit les fonctions suivantes :
let f = fun x y -> x + y let g = fun a b -> a (b + 1) let rec h = fun x -> h x Les réécrire en annotant avec des informations de typage.
Résolution de programmes (Examen Été 2023) Soit le programme suivant :
a(_). b(X, Y) :- a(X), c(X, Y). b(2, 5). c(X, Y) :- d(X), e(Y). d(1). d(2). e(3). e(4). Dans la suite de cette question, vous devrez dessiner des arbre de résolution. Pour cela, il est important :
d’indiquer les buts à résoudre dans les nœuds de l’arbre d’indiquer les assignations aux variables logiques sur les arcs d’indiquer true comme feuille pour les requêtes qui réussissent, et false.
1. La fonction factorielle La factorielle n! d’un entier naturel n est le produit des nombres entiers strictement positifs inférieurs ou égaux à n. Écrire la fonction fact à un paramètre entier n qui renvoie n!. Le résultat attendu à l’utilisation est le suivant :
# fact;; - : int -> int = <fun> # fact 0, fact 1, fact 2, fact 3, fact 4, fact 5;; - : int * int * int * int * int * int = (1, 1, 2, 6, 24, 120) Note : pour écrire une fonction récursive fct, et donc d’avoir le droit d’appeler fct dans la définition de fct, le mot clé rec est à placer juste avant l’identificateur lors de la liaison globale :
Note : ce laboratoire est prévu pour être fait durant deux scéances.
1. Définition de type et filtrage par motif 1.1. Cartes Définir un type card qui représente les différentes cartes possibles pour un jeu de carte. Une carte peut soit être une valeur numérique, soit une figure parmi le valet, la dame, et le roi. Une carte a également une couleur (cœur, carreau, trèfle, ou pique).
On souhaite comparer les cartes par valeur, où la valeur d’une carte numérique et égale à son nombre, et où le valet à une valeur inférieure à la dame, qui a une valeur inférieure au roi.
Les fonctions d’ordre supérieur sont des fonctions paramétrées par une ou plusieurs fonctions et/ou qui renvoient une fonction. Le but de ce TP est d’utiliser et d’écrire de telles fonctions et de se familiariser avec cette notion.
Premières fonctions d’ordre supérieures et curryfication Dans cet exercice, on utilisera les deux définitions suivantes :
let sqr x = x * x let my_list = [3; 12; 3; 40; 6; 4; 6; 0] Exprimer le type de la fonction f_sum paramétrée par une fonction f ainsi que deux entiers a et b et qui calcule f(a) + f(b).
Arbre binaire Rappel : un arbre binaire est un objet récursif défini comme étant
soit une feuille; soit un nœud interne portant un élément et à partir duquel sont attachés deux arbres binaires. De manière équivalente, un arbre binaire est une structure de données qui peut se représenter sous la forme d’une hiérarchie dont chaque élément est appelé nœud. Dans un arbre binaire, chaque élément possède au plus deux éléments enfants au niveau supérieur, habituellement appelés gauche et droit.
Démonstrations Théorèmes sur append Définir la fonction append qui prend deux listes en argument et renvoie la concaténation de ces deux listes. Démontrer que la liste vide est l’élément neutre à gauche pour append, c’est-à-dire append [] xs = xs pour tout xs Démontrer que la liste vide est l’élément neutre à droite pour append, c’est-à-dire append xs [] = xs pour tout xs Définir la fonction rev qui inverse une liste.
Écrire une relation member/2 entre une liste et ses membres. ?- member(1, [1,2]). true . ?- member(1, [2,3]). false. ?- member(X, [1,2,3]). X = 1 ; X = 2 ; X = 3. ?- member(1, L). L = [1|_] ; L = [_, 1|_] ; L = [_, _, 1|_] . Écrire une relation nth/3 entre une liste et son nième élément. ?- nth(0, [a,b,c], X). X = a. ?
Les problèmes de ce labo sont inspirés de la suite de problème P-99
Listes Écrire une relation palindrome/1 qui est vraie pour les listes étant un palindromes. ?- palindrome([a,b,c,b,a]). true. ?- palindrome([a,b,c]). false. Écrire une relation compress/2 entre une liste et la liste contenant les mêmes éléments, mais avec les éléments identiques consécutifs éliminés. ?- compress([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X). X = [a,b,c,a,d,e] Écrire une relation pack/2 entre une liste et la liste contenant les éléments identiques consécutifs groupés en sous-listes.
