TP 2

Travaux Pratiques de
Programmation Fonctionnelle

(sujet n°2)

I. Définition de types algébriques et filtrage.

(a) Taper la définition du type des cartes à jouer (vu en cours)

(b) En s'inspirant de la définition du type des listes, définir un type paquet_de_carte à l'aide de 2 constructeurs: Derniere (qui construit un paquet avec une seule carte) et Dessus (qui construit un paquet en ajoutant une carte au-dessus d'un paquet).

(c) Donner une expression Ocaml correspondant à un paquet de carte composé d'un as de coeur, d'un roi de tréfle et d'un 10 de carreau.

(d) Ecrire une fonction qui détermine si un paquet donné contient les 4 as.

(e) Ecrire une fonction qui trie un paquet de cartes par couleur dans l'ordre suivant : d'abord les coeurs (au-dessus), puis les carreaux, puis les piques et enfin les trèfles (à la fin du paquet).

(f) (Question facultative) Ecrire une fonction qui étant donné 2 paquets de cartes détermine lequel est gagnant au jeu de la bataille.

II. Types classiques.

1. Listes

(a) Rédéfinir et expérimenter les fonctions suivantes sur les listes polymorphes (le nom de la fonction prédéfinie est donné en gras) :

longueur (longueur d'une liste) List.length
tete (premier élément d'une liste) List.hd
reste (la liste sans son premier élément) List.tl
nieme (n-ième élément d'une liste : les éléments sont numérotés à partir de 0) List.nth
inverse (liste obtenue en renversant une liste : le 1er élément devient le dernier, le 2ème devient l'avant-dernier, ...) List.rev
concat (concaténation de 2 listes) List.append ou (@)

(b) On choisit de noter un ensemble (en extension) par une liste. Ex. [1;2;5] note l'ensemble des entiers 1, 2 et 5. On peut remarquer qu'il y a plusieurs notations pour le même ensemble. Ex. les listes [1;2;5], [1;5;2] ou [5;1;2] notent le même ensemble. De plus, on convient qu'un même élément dans un ensemble peut apparaître plusieurs fois dans la liste correspondante. Ex. [1;2;2;5], [1;1;2;5] ou encore [2;1;5;2;5] désigne le même ensemble. Ecrire les fonctions suivantes sur les ensembles :

union (union de 2 ensembles)
intersection (intersection de 2 ensembles)
inclus (test d'inclusion d'un ensemble dans un autre)
difference (différence de 2 ensembles : les éléments du premier ensemble sans les éléments du second)
egal (test d'égalité de 2 ensemble)

(c) (Question facultative) Définir une fonction permut qui étant donné un ensemble donné par une liste sans doublon, détermine la liste de toutes les autres listes sans doublon qui désignent le même ensemble (autrement dit la liste de toutes les permutations des éléments d'une liste). Ex. permut [1;2;3];; donne


[[1;2;3];[1;3;2];[2;1;3];[2;3;1];[3;1;2];[3;2;1]]

.

(d) Le problème des Tours de Hanoï est un problème classique. Il peut être résolu de manière très élégante en utilisant les listes. Ecrire en quelques lignes une fonction deplacer qui retourne la liste des déplacements à effectuer pour faire passer n disques de l'emplacement de vers l'emplacement a en passant par l'emplacement intermédiaire par, étant donné le quadruplet (n, de,

a,

par).

Ex. Liste des déplacements de 3 disques de l'emplacement 1 à l'emplacement 3 en passant par l'emplacement 2 :

# deplacer (3,1,3,2);;

- : (int * int) list =

[(1, 3); (1, 2); (3, 2); (1, 3); (2, 1); (2, 3); (1, 3)]

2. Arbres binaires

(a) Définir le type tree des arbres binaires polymorphes avec une valeur à chaque noeud (branche ou feuille).

(b) Donner l'expression Ocaml de l'arbre suivant:

$\begin{displaymath} \epsfig{file=arbre}\end{displaymath}$

(d) Définir une fonction height qui calcule la hauteur d'un arbre. On appelle hauteur d'un arbre la longueur maximale d'un chemin direct de la racine à un noeud quelconque.

(e) Définir une fonction max_tree qui calcule la plus grande valeur présente dans un arbre.

[Page réalisée par Eric Violard]