20130930:TP:OCaml:Reloaded

Introduction

Ce TP a pour but de vous faire revoir les notions d'OCaml acquises en SUP.

Le TP est découpé en exercice, chaque exercice devra correspondre à un fichier OCaml nommé: tp02_exerciceXX.ml où XX correspond au numéro de la question aligné avec un zéro si nécessaire (donc la question 1 ira dans le fichier tp02_exercice01.ml.) Chaque question peut contenir une ou plusieurs fonctions.

Vos fichiers ne devront contenir que le code demandé (et d'éventuels commentaires), en effet, la correction commencera par une compilation de chaque question, s'il y a du code faux dans le fichier (autre que celui demandé) la question sera considérée comme ne compilant pas.

Quickstart

Cette partie s'adresse à ceux qui n'ont encore jamais utilisé un shell sur un système UNIX.

Ce TP est le premier TP sous Unix à l'école. Il va donc falloir que vous vous fassiez la main sur les manipulations de base.

Le terminal

Votre interface d’interaction principale avec le système d'exploitation est ce qu'on appelle le shell: il s'agit d'un programme qui reçoit des commandes de l'utilisateur au travers d'une interface textuelle. En général, si vous êtes dans un environnement graphique pour accéder au shell vous devez ouvrir un émulateur de terminal (en général xterm ou rxvt.)

Commandes de base

Les commandes sont (preque toutes) des programmes réalisant une tâche simple (KISS principle) comme copier un fichier ou créer un répertoire …

Presque toutes les commandes ont la même forme: un nom suivi d'option commencant par un - ou de paramètre (en général des noms de fichier.)

Lorsque vous avez besoin de documentation sur une commande (entre autre) vous pouvez utiliser la commande man qui affiche les pages des manuels. Lorsque vous ouvrez une page de manuel, la documentation s'affiche dans le terminal courant et vous pouvez vous déplacer avec les flèches haut et bas et quitter avec la touche q. Quelques exemples:

# Le manuel du manuel:
> man man
…
> man cp
…

Les commandes de base dont vous aurez besoin sont:

• ls: list le contenu d'un répertoire
• cp: copie fichier et répertoire
• mkdir: créer un répertoire
• cd: changer de répertoire courant.

Préparer le TP

Ce TP sera probablement corrigé, du coup, autant commencer directement dans les bonnes conditions de rendu: vous allez créer un répertoire pour les TP (vous pouvez prendre n'importe quel nom) et dans ce répertoire vous créerez un sous-répertoire de la forme: login-tp20130930 (en remplaçant login par votre … login.)

Une fois ce répertoire créer, on va y ajouter le traditionnel fichier AUTHORS.

Voici un exemple de session:

> pwd
/usr/home/burell_m
> mkdir -p TP/burell_m
> cd TP/burell_m
> echo '* burell_m (Marwan Burelle)' > AUTHORS

• Faite une archive au format tar.bz2 de votre répertoire et portant le nom login-tp20130930

Hint: lisez la page de man de la commande tar

Configuration d'emacs

Vous pouvez suivre les indications de cette page: Emacs.

Arithmétiques et récursion

Question 1: factorielle

Écrire la fonction suivante:

val fact: int -> int

fact n renvoie $n!$ si n est positif ou nul et -1 sinon.

Question 2: Fibonacci

Écrire la fonction suivante:

val fibo: int -> int

fibo n renvoie le rang n de la suite de Fibonacci si n est positif ou nul et -1 sinon. On rappelle que la suite de Fibonacci est définie comme:

$\text{Fibo}(0) = 0$

$\text{Fibo}(1) = 1$

$\text{Fibo}(n) = \text{Fibo}(n-1) + \text{Fibo}(n-2)$

Note: essayer, si possible d'écrire une version linéaire, et non exponentielle, de cette fonction.

Question 3: exponentielle

Écrire la fonction suivante:

val expo: int -> int -> int

expo x n renvoie $x^n$ si n est positif ou nul et -1 sinon.

Note: essayer, si possible d'écrire la version rapide de cette fonction.

Listes

Question 4: opérations simples

Écrire les fonctions suivantes:

(* length l: renvoie la taille de la liste *)
val length : 'a list -> int
(* nth l i renvoie le ieme element la liste l*)
val nth : 'a list -> int -> 'a
(* rev l renverse la liste *)
val rev : 'a list -> 'a list
(* append l1 l2 accroche les deux listes entre elles *)
val append : 'a list -> 'a list -> 'a list

Question 5: map

Écrire la fonction suivante:

val map: ('a -> 'b) -> 'a list -> 'b list

map f [e1; ...; en] renvoie la liste [f e1; ...; f en]. Attention, vous devez vous assurez que l'évaluation de la fonction f sur chaque élément de la liste, respecte l'ordre de la liste (cf cours.)

Question 6: iter

Écire la fonction suivante:

val iter: ('a -> unit) -> 'a list -> unit

iter f [e1; ...; en] ne renvoie rien et applique successivement la fonction f sur chaque élément de la liste en entrée.

Note: vous aurez un type probablement différent de celui attendu pour cette fonction, essayez de comprendre pourquoi.

Question 7: fold_left

val fold_left: ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

fold_left f a [b1; ...; bn] renvoie f (... (f (f a b1) b2) ...) bn.

Question 8: fold_right

val fold_right:  ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b

fold_right f [a1; ...; an] b renvoie f a1 (f a2 (... (f an b) ...))

Question 9: quantificateurs

Écrire les fonctions suivantes:

val exists: ('a -> bool) -> 'a list -> bool
val for_all: ('a -> bool) -> 'a list -> bool

exists f l renvoie vrai si il existe un élément de l pour lequel f renvoie vrai.

for_all f l renvoie vrai si f renvoie vrai pour tous les éléments de l.

Arbres

Nous allons maintenant manipuler des arbres binaires valués sur les nœuds. Pour le reste de cette partie nous utiliserons le type suivant:

type tree =
  | Empty                       (* arbre vide *)
  | Node of tree * int * tree   (* noeud *)

Question 10: Taille de l'arbre

Écrire la fonction suivante:

val size: tree -> int

size t renvoie le nombre de nœuds dans l'arbre t.

Question 11: Hauteur de l'arbre

Écrire la fonction suivante:

val height: tree -> int

height t renvoie la hauteur de l'arbre t (on rappelle que la hauteur de l'arbre vide est -1.)