\documentclass[10pt]{tpcaml}

% TP caml à LLG, Début Février 2010
% par Gabriel Scherer
% Version modifiée des colles de Victor Nicollet

\tp{2}{Programmation récursive\\ }

\begin{document}

  \maketitle
  
  Cette colle a été (comme la première, et sans doute les suivantes)
  adaptée d'une colle donnée par Victor Nicollet à LLG il y a quelques
  années.

\section{Récursivité}


  On dit qu'une fonction est \em récursive \em lorsqu'elle apparaît dans sa 
  propre définition. Cela est indiqué par le symbole \code{rec}, qui rend le 
  nom de la fonction disponible à l'intérieur de sa définition (sans lui, 
  le nom ne serait disponible qu'après la définition).
%
\begin{codesection}
  let rec fac = function \+\\
    | 0 -> 1 \\
    | n -> n * fac (n - 1);;
\end{codesection}
 
  L'exemple ci-contre est une fonction récursive qui calcule $n!$.  
  Lorsque \code{fac n} est exécutée, elle va appeler \code{fac (n-1)}, qui va appeler
  \code{fac (n-2)} et ainsi de suite jusqu'à 0. Il va donc y avoir $n+1$ appels
  à \code{fac } pour calculer \code{fac n}.
  
  La récursion est un outil pratique pour traduire en \camli\ des fonctions ou 
  suites mathématiques définies par récurrence. 
\vspace{12pt}
\begin{question}
  \'Ecrire une fonction récursive simple qui calcule le terme $n$ de la suite de 
  Fibonnaci, avec $u_0 = u_1 = 1$. Quelle est sa complexité en fonction
  de $n$ ? Peut-on l'améliorer (indice : utiliser des couples) ?
\end{question}

\vspace{12pt}
La récursion est un très bon outil pour résoudre les problèmes présentant la structure suivante :
\begin{itemize} \setlength{\itemsep}{0cm}\setlength{\parskip}{0cm}
\item un ou plusieurs cas de base très simples (par exemple ici : $0! = 1$)
\item un cas général que l'on peut décomposer en sous-problèmes plus
  simples (ici, pour connaître $n!$ il suffit de connaître $(n-1)!$).
\end{itemize}

\vspace{12pt}
\begin{question}
  On sait que $x^0 = 1$, $x^{2k} = (x^2)^k$ et $x^{2k+1} = x(x^2)^k$.
  En déduire une fonction récursive pour calculer $x^n$ ($x$ et $n$ donnés).\\
  Indication : étudier la parité de $n$.
\end{question}

\section{Types somme}

\begin{codesection}
\#type contact = Tel of int | Mail of string | Inconnu;;\\
Type contact defined.\\
\#Mail "\mymail";;\\
- : contact = Mail "\mymail"
\end{codesection}

Il est possible en \camli\ de définir de nouveaux types. Un type somme
est constitué d'un ensemble de valeurs associées à des \em
constructeurs\em. Ci-contre, \code{contact} est décrit par deux
constructeurs: \code{Tel}, associé à un entier, \code{Mail} associé
à une chaîne de caractères, et \code{Inconnu} qui n'est associé à rien
du tout; un contact sera donc soit un numéro de téléphone, soit une
adresse mail, soit un inconnu (étrange...).

\paragraph{Rappel :} On suppose connu les tuples : si \code{ta} et
\code{tb} sont des types \caml, \code{ta * tb} est le type des couples
d'un élément de type \code{ta}, et d'un élément de type \code{tb}. Par
exemple \code{(1, "blah") : int * string}. On peut faire des n-uplets
à plus de deux membres, comme \code{(1, "blah", 3.5) : int * string *
  float}.

\vspace{12pt}
\begin{question} 
  On souhaite écrire une fonction qui résout une équation du 
  second degré donnée par un triplet $(a,b,c)$. Définir un 
  type capable de représenter zéro, une ou deux solutions, puis
  écrire la fonction renvoyant un objet de ce type.
\end{question}

\subsection{Pattern matching}

\begin{codesection}
let contacter contact = match contact with \\
  | Mail m -> "Envoyer un mail à "\^{}m \\
  | Tel t -> "Appeler le "\^{}(string\_of\_int t);;
\end{codesection}

Il est facile de construire des valeurs d'un type somme, mais comment
les utiliser ensuite ? On va vouloir faire quelque chose comme ``si
c'est un numéro de téléphone, alors téléphoner, sinon envoyer un
mail''.

Cependant, l'instruction conditionnelle\\ \code{if  then  else}
n'est pas suffisante dans ce cas : on voudrait dire \code{if contact =
  Tel}, mais ça ne marche pas, car contact est de la forme \code{Tel
  \emph{entier}}. Il faut pouvoir dire ``si contact est de la forme
\code{Tel \emph{numéro}}, alors téléphoner à \code{numéro}''. C'est le
principe du \emph{pattern matching}, ou \emph{filtrage de motif}.

\begin{minipage}{400pt}
match $expr$ with\\
| $pattern_1$ -> $expr_1$\\
| $pattern_n$ -> $expr_2$\\
...
\end{minipage}

L'instruction essaye les motifs à gauche des \code{->}, de haut en
bas; lorsqu'un premier motif $pattern_n$ correspond \\ (il ``matche'')
à la valeur $expr$, les variables présentes \\ dans le motif reçoivent
la valeur correspondant dans $expr$, et l'expression à droite du
\code{->}, $expr_n$, est renvoyée.

\begin{question}
  Que fait la fonction \code{est\_ce\_moi} ?
\end{question}

\begin{codesection}
let est\_ce\_moi contact =\\
  let mon\_tel = 0102030405 in\\
  let mon\_mail = "\mymail" in\\
  match contact with\\
  | Mail mon\_mail -> true\\
  | Tel mon\_tel -> true\\
  | Mail \_ | Tel \_\\ | Inconnu -> false
\end{codesection}

\vspace{12pt}
  Il faut bien comprendre que les motifs permettent à la fois de faire
  des choix (comme \code{if..then..else}) et de nommer des variables
  (les identifiants présents dans le motif). Le motif \code{Mail m}
  par exemple va déclarer une nouvelle variable \code{m} valant
  l'adresse mail du contact (si le contact est bien de la forme
  \code{Mail mail}). Elle ne fait pas référence à une variable
  \code{m} précédente (qui, si elle existe, sera écrasée). En
  particulier, on ne peut pas mettre plusieurs fois la même variable
  dans un seul motif.

  Si un motif est constitué d'une seule variable, il matche n'importe
  quelle valeur, et lie la variable à cette valeur : \code{match
    a with b -> c} est équivalent (sans polymorphisme) à \code{let b =
    a in c}. Il existe aussi un motif acceptant tout, et ne déclarant
  pas de nouvelle variable : \code{\_}\\
  On peut aussi écrire des motifs pour les n-uplets : \code{($patt_1$,
    $patt_2$, ...)} est un motif correspondant aux n-uplets dont les
  membres correspondent aux motifs $patt_1$, $patt_2$, ...

\section{Listes}
  
\subsection{Types récursifs}

  Il est possible d'utiliser un type dans sa propre définition, sans
  même spécifier un \code{rec}. 
\vspace{12pt}

On programme un robot qui se déplace dans le plan. Un programme du
robot peut consister en deux choses: la commande \code{Stop}, qui
marque la fin du programme, et la commande \code{Move (p,suite)}, qui
indique au robot de bouger de se rendre au point \code{p : float *  float}
et d'exécuter ensuite le programme \code{suite}.
  
Définir un type \camli\ décrivant un programme. Quel est le programme
correspondant aux mouvements $((1,2),(-1,-3),(2.2,-3))$ ?

\begin{question}
  \'Ecrire une fonction qui, étant donnés un point de départ
  et un programme, calcule le point d'arrivée du robot.
\end{question}

\begin{question}
  \'Ecrire une fonction qui calcule la taille (le nombre de
  déplacements) du programme qu'on lui donne.
\end{question}

\subsection{Principe}

Une liste est la généralisation du type récursif utilisé dans la
question 5. La commande \code{Stop} est notée \code{[]}. Il s'agit de
la liste vide, qui ne contient aucun élément. La commande \code{Move
  (x,p)} est notée \code{x \lic p}: elle contient l'élément \code{x}
appelé tête de la liste, et la liste \code{p} appellée queue de la
liste. Ces deux constructions permettent à la fois d'écrire des
expressions pour construire des listes, et des motifs pour les
déconstruire.
  
On utilise une abbréviation: la liste des entiers de 1 à 3,
\code{1 \lic (2 \lic (3 \lic []))}, peut s'écrire de manière plus lisible
comme: \code{\li 1; 2; 3\il}
  
Contrairement aux tableaux, les listes ne peuvent pas être
modifiées. La manipulation des listes ne comporte donc que deux
possibilités: parcourir la liste pour en extraire des informations, ou
créer une nouvelle liste.

\subsection{Parcourir une liste}
%
\begin{codesection}
  let rec length = function \+\\
    | [] -> \+\\0 \-\\
    | h \lic t -> \+\\length t + 1;;
\end{codesection}

La fonction ci-contre calcule la longueur d'une liste en la
parcourant, élément par élément. Plus généralement, on parcourt une
liste comme on étudie un type récursif : on écrit une fonction qui
effectue un travail sur la tête de la liste et s'applique
récursivement sur la queue de la liste.

On a utilisé dans ce code la forme nouvelle \code{(function ...)},
équivalente à \code{(fun x -> match x with ...)}, sans nommer de
variable \code{x}. Attention, \code{function} prend implicitement un
paramètre (comme \code{fun}, mais on ne le nomme pas, on lui applique
directement des motifs), vous l'oublierez de temps en temps !

\vspace{12pt}
\begin{question}
  On utilise maintenant des listes pour programmer le robot. Décrire
  les mouvements $((1,2),(-1,-3),(2.2,-3))$, puis réécrire les fonctions
  calculant le point d'arrivée et le nombre de mouvements.
\end{question}

\subsection{Créer une liste}

  On sait créer manuellement des listes de longueur donnée. Comment créer des
  listes de longueur arbitraire?
  
\begin{codesection}
  let rec carres = function \+\\
    | 0 ->\+\\ {[]} \-\\
    | n ->\+\\ (n*n)\lic (carres (n-1));;
\end{codesection}

  Créer une liste est fondamentalement un problème récursif: si on
  sait construire la queue de la liste, on peut construire la
  liste en y ajoutant simplement la tête. 
  
  Par exemple, la fonction ci-contre calcule la liste des carrés des
  entiers plus petits que $n$.

\begin{question}
  \'Ecrire une fonction qui calcule la liste de diviseurs premiers
  d'un entier $n$, apparaissant autant de fois dans la liste que dans
  $n$.
\end{question}

\subsection{Transformation de listes}

\begin{codesection}
  let rec ajoute x = function \+\\
    | [] -> \+\\ {[]}\-\\
    | t::q -> \+\\ (t+x)::(ajoute x q);;\-\-\\
  \\
  let rec supprime\_impairs = function \+\\
    | [] | [\_] -> \+\\ {[]}\-\\
    | impair::pair::reste -> \+\\  pair::(supprime\_impairs reste);;
\end{codesection}

  On ne peut pas transformer les listes, puisqu'on ne peut pas les modifier! En 
  revanche, on peut créer une liste à partir des données lues dans une autre. Pour
  cela, il suffit en général d'écrire une fonction qui lit des données dans une
  liste, et qui renvoie une liste.
  
  Une modification peut impliquer de remplacer la tête par une autre tête,
  d'insérer des éléments avant ou après la tête, ou même d'éliminer la tête
  pour ne garder que la queue de la liste. Des exemples de modification sont
  donnés ci-contre. 
  
\vspace{12pt}
\begin{question}
  La fonction \code{map} prend en argument une liste \code{\li x1; x2; \ldots\ xn\il} 
  et une fonction \code{f} et renvoie la liste \code{\li f(x1); f(x2); \ldots\ f(xn)\il}.
  R\'eecrivez vous-même cette fonction.
\end{question}

\vspace{12pt}
\begin{question}
  Écrire la fonction \code{rev\_append}, telle que \code{rev\_append} ajoute a, retournée, devant b :\\
  \code{rev\_append [1;2;3] [4;5;6] = [3; 2; 1; 4; 5; 6]}\\
  
  En déduire (et écrire) une fonction \code{rev} qui retourne une liste.
\end{question}

\vspace{12pt}
\begin{question}
  \'Ecrire une fonction \code{insert} qui, étant donnés une liste triée \code{l} et un 
  élément \code{e}, renvoie la liste triée contenant \code{e} ainsi que les éléments
  de \code{l} (on parle d'insérer un élément dans une liste triée).\\

  En déduire (et écrire) une fonction qui applique le tri par insertion pour 
  trier une liste.
\end{question}

\vspace{12pt}
\begin{question}
  Implémenter une queue FIFO (on ajoute les éléments à une extrémité,
  on les retire à l'autre) et les opérations \code{enqueue} et
  \code{dequeue} (complexité constante amortie) pouvant 
  contenir un nombre arbitraire d'éléments.

  Indice : utiliser un couple de listes, les éléments ``de devant'' et
  les éléments ``de derrière''. Attention à l'ordre !
\end{question}

\vspace{12pt}
\begin{question}
  À faire à la fin, s'il vous reste du temps.
  
  Regarder le type, comprendre le fonctionnement et recoder les
  fonctions suivantes :
  \begin{itemize} \setlength{\itemsep}{0pt} \setlength{\parskip}{0pt}
  \item do\_list
  \item map2
  \item index
  \item assoc
  \item split, combine
  \item (difficile) it\_list, list\_it
  \end{itemize}
\end{question}

\begin{codesection}
\#let a::b = [];;\\
Uncaught exception: Match\_failure ("", 0, 15)
\end{codesection}

Les formes \code{let} acceptent en fait tout motif à la place de
l'identifiant (qui est un cas particulier de motif). Si la valeur liée
ne correspond pas au motif, une erreur est levée.

\section{Questions difficiles}

\begin{codesection}
let dernier = function \+\\
  | [] -> failwith "Erreur" \\
  | [x] -> x \\
  | \_::q -> dernier q
\end{codesection}
\begin{question}
  On dit qu'une fonction utilise la récursion terminale si elle
  renvoie le résultat d'un appel récursif, plutôt que le résultat
  d'une autre opération. Un exemple est donné ci-contre. 
  
  Expliquer pourquoi de telles fonctions peuvent être très 
  simplement réécrites sous la forme d'une boucle 
  \code{while}, et consomment une quantité fixe de mémoire.
  
  Proposer une méthode pour transformer des fonctions comme
  \code{facto}, \code{combine} ou \code{map} en fonctions
  à récursion terminale. Est-ce possible pour toutes les 
  fonctions?
\end{question}

\vspace{12pt}
\begin{question}
  \'Ecrire un programme qui provoque l'erreur suivante:
\end{question}

\begin{center}
  \tt This expression has type truc, but is used with type truc.
\end{center}

\vspace{20pt}
\begin{question} Dessiner un chameau \end{question}

\end{document}
