Université Paris 6 Licence d'informatique	Module de Programmation Année 1999-2000

Travaux dirigés n° 5

Exercice 1

Typez les expressions définies dans la session Caml suivante. L'environnement initial est noté Env-Init:
1.

let a = 3 and b = 1;;
let g = function x -> a*x+b;;
g 1;;
let a = true and b = false;;
g 1;;

let f2 = function x -> let a = 3 and b = 1 in a*x+b;;
f2 1;;

let f3 = let a = 3 and b = 1 in function x -> a*x+b;;
f3 1;;

let h = function x -> (fst x,x);;

Qu'en concluez-vous sur le type de cette fonction ?

Exercice 2

Dans le but d'écrire une fonction reste : (int*int) -> int qui permette de traiter le cas d'une division par 0, nous effectuons les déclarations suivantes :

exception Divise_par_zero of int ;;
let rec reste = 
    function (a,b) ->
      if (b = 0)  then  raise Divise_par_zero(a)
      else if ( b < 0 )  then  reste (a,-b) 
      else if (a < 0)  then  reste (-a,b)
      else if (a < b)  then  a 
      else  reste (a-b,b);;

1. Écrivez reste de manière un peu plus élégante en utilisant une fonction récursive utilitaire qui suppose ses deux arguments positifs.

2. Déduisez en une implémentation de pgcd : int*int -> int qui ne fasse pas de test à 0 mais qui rattrape l'exception Divise_par_zero.

Exercice 3

Nous allons nous familiariser ici avec le type des listes. On pourra revenir à cet exercice après avoir vu le polymorphisme.
1. Définissez le type des listes d'entiers.
2. Écrivez (définir, typer et évaluer) les fonctions suivantes :

length qui calcule la longueur d'une liste.
head, tail et nth qui retournent respectivement le premier, le dernier et le nthélément d'une liste.
reverse qui renverse une liste.
append qui met deux listes bout à bout.
member qui détermine si un élément est ou non présent dans une liste.
for_all qui détermine si un prédicat est vérifié par tous les éléments d'une liste.

Dans la suite on donnera les solutions pour ce type en définissant ses propres fonctions puis pour le type prédéfini des listes en s'appuyant sur la bibliothèque disponible en Caml.
3. Écrivez une fonction qui recherche, par dichotomie, si un élément est ou non présent dans une liste triée.
4. Écrivez la fonction merge qui fusionne deux listes triées. En déduire une fonction de tri par dichotomie.

Exercice 4

Typez et évaluez la déclaration suivante :

exception ArgumentNegatif
let fact = 
    let rec fac2 = function(v,n) -> if (n = 0) then v else fac2(v*n,n-1)
    in
      function n -> if (n < 0) then raise ArgumentNegatif else fac2(1,n) ;;

Exercice 5 (Les listes d'associations, épisode I)

Une association est un couple composé d'une clé et d'une valeur. Notre objectif est de définir une fonction assoc recherchant la valeur associée à une clé dans une liste d'associations.

1. Définir le type paramétré list_assoc. Écrire une valeur de ce type.

2. Écrire la fonction assoc prenant une clé et une liste d'associations et retournant « une » valeur associée à la clé dans la liste. La fonction lèvera l'exception prédéfinie Not_found si la clé est absente.

3. Écrire la fonction assoc_all retournant toutes les valeurs associées à une clé donnée. En cas d'absence, on continuera à lever l'exception Not_found.

to be continued...

Ce document a été traduit de L^AT_EX par H^EV^EA.