Voir la source de 20130930:TP:OCaml:Reloaded

[[category:EPITA:TP:20132014]]


== 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é: <tt>tp02_exerciceXX.ml</tt> où <tt>XX</tt> correspond au numéro de la question aligné avec un zéro si nécessaire (donc la question 1 ira dans le fichier <tt>tp02_exercice01.ml</tt>.) 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 <tt>xterm</tt> ou <tt>rxvt</tt>.)

=== 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 <tt>-</tt> 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 <tt>man</tt> 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 <tt>q</tt>. Quelques exemples:

<pre>
# Le manuel du manuel:
> man man
…
> man cp
…
</pre>

Les commandes de base dont vous aurez besoin sont:

* <tt>ls</tt>: list le contenu d'un répertoire
* <tt>cp</tt>: copie fichier et répertoire
* <tt>mkdir</tt>: créer un répertoire
* <tt>cd</tt>: 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: <tt>login-tp20130930</tt> (en remplaçant <tt>login</tt> par votre … login.)

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

Voici un exemple de session:

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

* '''Faite une archive au format tar.bz2 de votre répertoire et portant le nom <tt>login-tp20130930</tt>'''

: ''Hint: lisez la page de man de la commande <tt>tar</tt>''

== Configuration d'<tt>emacs</tt> ==

Vous pouvez suivre les indications de cette page: [[Emacs]].

== Arithmétiques et récursion ==

=== Question 1: factorielle ===

Écrire la fonction suivante:

<source lang="OCaml">
val fact: int -> int
</source>
<tt>fact n</tt> renvoie <math>n!</math> si <tt>n</tt> est positif ou nul et <tt>-1</tt> sinon.

=== Question 2: Fibonacci ===

Écrire la fonction suivante:

<source lang="OCaml">
val fibo: int -> int
</source>
<tt>fibo n</tt> renvoie le rang <tt>n</tt> de la suite de Fibonacci si <tt>n</tt> est positif ou nul et <tt>-1</tt> sinon. On rappelle que la suite de Fibonacci est définie comme:

<math>\text{Fibo}(0) = 0</math>

<math>\text{Fibo}(1) = 1</math>

<math>\text{Fibo}(n) = \text{Fibo}(n-1) + \text{Fibo}(n-2)</math>

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

=== Question 3: exponentielle ===

Écrire la fonction suivante:

<source lang="OCaml">
val expo: int -> int -> int
</source>
<tt>expo x n</tt> renvoie <math>x^n</math> si <tt>n</tt> est positif ou nul et <tt>-1</tt> sinon.

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

== Listes ==

=== Question 4: opérations simples ===

Écrire les fonctions suivantes:

<source lang="ocaml">
(* 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
</source>

=== Question 5: map ===

Écrire la fonction suivante:

<source lang="ocaml">
val map: ('a -> 'b) -> 'a list -> 'b list
</source>

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

=== Question 6: iter ===

Écire la fonction suivante:

<source lang="ocaml">
val iter: ('a -> unit) -> 'a list -> unit
</source>

<tt>iter f [e1; ...; en]</tt> ne renvoie rien et applique successivement la fonction <tt>f</tt> 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 ===

<source lang="ocaml">
val fold_left: ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
</source>

<tt>fold_left f a [b1; ...; bn]</tt> renvoie <tt>f (... (f (f a b1) b2) ...) bn</tt>.

=== Question 8: fold_right ===

<source lang="ocaml">
val fold_right:  ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
</source>

<tt>fold_right f [a1; ...; an] b</tt> renvoie <tt>f a1 (f a2 (... (f an b) ...))</tt>

=== Question 9: quantificateurs ===

Écrire les fonctions suivantes:

<source lang="ocaml">
val exists: ('a -> bool) -> 'a list -> bool
val for_all: ('a -> bool) -> 'a list -> bool
</source>

<tt>exists f l</tt> renvoie vrai si il existe un élément de <tt>l</tt> pour lequel <tt>f</tt> renvoie vrai.

<tt>for_all f l</tt> renvoie vrai si <tt>f</tt> renvoie vrai pour tous les éléments de <tt>l</tt>.

== 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:

<source lang="ocaml">
type tree =
  | Empty                       (* arbre vide *)
  | Node of tree * int * tree   (* noeud *)
</source>

=== Question 10: Taille de l'arbre ===

Écrire la fonction suivante:

<source lang="ocaml">
val size: tree -> int
</source>

<tt>size t</tt> renvoie le nombre de nœuds dans l'arbre <tt>t</tt>.

=== Question 11: Hauteur de l'arbre ===

Écrire la fonction suivante:

<source lang="ocaml">
val height: tree -> int
</source>

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