Session de Juin 1996
Exercice 1:
Pour chacune des équations suivantes, justifier si elle est vraie ou fausse:
1- (x::[])@[y;z]=[x;y;z]
2- [7;11;15]::[]=[7;11;15]
3- xs::[]=xs
4- xs@ys=[xs::ys]
Exercice 2:
Donner un exemple de fonction ayant pour type
1: num*num -> bool
2: (alpha->beta) -> [alpha] -> [beta]
Exercice 3:
1: Rappeler les définitions des fonctions filtrer, appliquer et renverser
2: Donner, en les justifiant, les différentes étapes de l'évolution de : filtrer pair (renverser(aplliquer carre[2;3;4])). Rappelons que les fonctions pair et carre ont leur sens classique.
Exercice 4:
Etant donnée une liste xs d'entiers, soit L une liste d'entiers définie en compréhension comme-suit:
L=[x*x|x <- xs;impair x].
1: Evaluer L sachant que xs=[1;2;4;7;12].
2: Les fonctions impair et carre étant supposées connues, définir cette liste à l'aide de fonctions connues.
Exercice 5:
On donne le script suivant:
applique f xs = applique_rec([],xs)
sachant que
applique_rec (xs,[]) = xs
applique_rec (xs,y::ys) = applique_rec (xs@[f y],ys)
1: Donner le type de la fonction applique.
2: Détailler le calcul de applique carre [1;3;5]. Quelle remarque peut-on faire ?
3: Traduire ce script en CAML.
4: Montrer enfin par induction que: applique f xs = applique f xs.
Exercice 6:
La fonction faire appliquée à une liste xs doit renvoyer la paire ayant comme premier élément, la liste contenant le dernier élément de xs et, comme deuxième élément, la liste xs privée de son dernier élément.
-Exemple: faire [1;2;3]=([3],[1;2]).
1: Définir par filtrage la fonction faire. Il est possible de traduire le cas général à l'aide d'une définition locale faisant appel à la fonction faire.
2: Détailler ensuite l'évaluation de faire [1;2;3].
3: Traduire enfin le script obtenu en CAML.
NB: On rappelle que les notations et les définitions utilisées dans l'énoncé sont celles du cours d'Algorithmique Fonctionnelle. En particulier, x, y et z désignent des éléments de listes, et xs, ys, et zs des listes d'éléments