PRFO23 : TP2

Exercice 1 : Interface des files

On cherche à écrire une interface pour les files (queue, structure de données FIFO). On travaillera dans un fichier queue.mli

1. Déclarer un type abstrait polymorphe pour les files.
2. Déclarer une valeur pour la file vide.
3. Déclarer une exception Empty_queue.
4. Déclarer une fonction pour insérer un élément dans une file.
5. Déclarer une fonction pour retirer l'élément le plus ancien d'une file. Il faudra également retourner la file sans laquelle on a retiré l'élément.
6. Déclarer une fonction fold qui itère sur les éléments d'une file dans l'ordre dans lequel ils ont été insérés.

Exercice 2 : Implémentation des files

Pour implémenter les files de façon fonctionnelle, on peut utiliser des couples de liste : la première permet de récupérer les éléments, si elle n'est pas vide sa tête sera donc l'élément le plus ancien. La deuxième sert à stocker les éléments, sa tête sera donc le dernier élément inséré.

Ainsi, le couple [1; 2], [4; 3] est un pile dans laquelle on a inséré les élements 1 2 3 4 dans cet ordre.

Pour retirer un élément quand la première liste est vide, il faudra inverser la deuxième pour récupérer son élément le plus ancien ; on utilisera alors la suite de la liste inversée comme première liste.

Ainsi, pour la pile représentée par [], [4; 3; 2; 1], on retournera 1 comme élément et [2; 3; 4], [] comme nouvelle pile.

On travaillera dans un fichier queue.ml

1. Définir le type concret pour les files.
2. Définir la valeur de la file vide (couple de listes vides).
3. Définir une exception Empty_queue.
4. Définir une fonction pour insérer un élément dans une file. On ajoute en tête de la seconde liste.
5. Définir une fonction pour retirer l'élément le plus ancien d'une file, comme décrit ci-dessus.
6. Définir une fonction fold qui itère sur les éléments d'une file dans l'ordre dans lequel ils ont été insérés. On pourra utiliser List.fold_left et List.fold_right.

Exercice 3 : Utilisation

On considère des dépendances entre tâches (ici représentées par des entiers). On peut par exemple penser à des dépendances dans un Makefile. On souhaite afficher un ordonnancement des ces tâches qui respecte les dépendances (c.-à.-d. si i est affiché avant j, alors i ne dépend pas de j).

On complétera le fichier deps.ml.

Les dépendances seront représentées par une liste de couples a, l où a est une tâche et l est la liste de tâches dont elle dépend.

1. Écrire une fonction add_no_dep qui prend en paramètre une file et une liste de dépendances, et qui retourne une file et une liste de dépendance telles que on a retiré de la liste de dépendances tous les couples i, [] et on a alors ajouté i dans la file.
2. Écrire une procédure order_aux qui prend en paramètre une file et une liste de dépendances. Si la file est vide on s'arrête. Sinon retire alors un élément i de la file. On affiche i sur la sortie standard. On retire i de la liste l de chacun des couples j, l de la liste de dépendances. On applique add_no_dep sur la file et la nouvelle liste de dépendances, et on s'appelle récursivement sur les nouvelles file et liste de dépendances.
3. Écrire une procédure order qui prend en paramètre une liste de dépendances. On part d'une file vide et de la liste de dépendances et on y applique add_no_dep pour obtenir la file et la liste de dépendances initiales. On applique alors order_aux à celles-ci.
4. Utiliser fold pour afficher l'état de la file à chaque appel récursif à order_aux.