\documentclass{tpcaml}

\tp{1}{Rappels}

\begin{document}

\maketitle

\section{Structures de contrôle}

La structure de contrôle \verb+if c then a else b+ évalue \verb+a+ si
\verb+c+ est vraie, et évalue \verb+b+ sinon.

\vspace{12pt}
\begin{question}
  \'Ecrire la fonction valeur absolue \verb+abs+, de type 
  \verb+int -> int+.
\end{question}
\vspace{12pt}

La structure de contrôle \verb+for i = a to b do corps done+ exécute
\verb+corps+ une fois pour chaque valeur entière entre \verb+a+ et \verb+b+
inclus. 

\vspace{12pt}
\begin{question}
  \'Ecrire une fonction \verb+diviseurs+ qui compte le nombre de diviseurs
  d'un entier, de type \verb+int -> int+.
\end{question}
\vspace{12pt}

La structure de contrôle \verb+while c do corps done+ exécute \verb+corps+
jusqu'à ce que \verb+c+ devienne vraie. 

\vspace{12pt}
\begin{question}
  \'Ecrire une fonction \verb+premier+ qui détermine si un nombre est
  premier, qui s'arrête dès qu'elle a trouvé un diviseur, de type 
  \verb+int -> bool+.
\end{question}

\section{Tableaux}

\subsection{Bases}

On rappelle qu'un tableau est une suite numérotée d'éléments
$[|a_0\ldots a_{n-1}|]$. La fonction \verb+init_vect n f+ crée
le tableau $[|a_0\ldots a_{n-1}|]$ tel que $\forall i\, a_i = f(i)$. 

\vspace{12pt}
\begin{question}
  \'Ecrire une fonction \verb+poly(x,n)+ qui crée un tableau 
  $[|a_0\ldots a_{n-1}|]$ où $a_i = i(x+i)$, de type
  \verb+int * int -> int vect+.
\end{question}
\vspace{12pt}

La fonction \verb+vect_length(a)+ renvoie la taille $n$ du tableau
$[|a_0\ldots a_{n-1}|]$, et la fonction \verb+make_vect n x+
crée le tableau $[|a_0\ldots a_{n-1}|]$ où $\forall i\, a_i = x$. 

Pour lire la valeur de $a_i$, on écrit \verb+a.(i)+. Pour modifier
la valeur de $a_i$, on écrit \verb+a.(i) <- x+. 

\vspace{12pt}
\begin{question}
  On représente le polynôme $\sum_i=0^{n-1} a_ix^i$ par le tableau 
  $[|a_0\ldots a_{n-1}|]$. \'Ecrire une fonction 
  \verb+somme_polynomes(a,b)+ qui renvoie un tableau représentant
  la somme des polynômes $a$ et $b$. Attention, $a$ et $b$ n'ont
  pas nécessairement la même taille!
\end{question}

\subsection{Itération}

On rappelle que la fonction \verb+max a b+ renvoie le plus grand
des éléments \verb+a+ et \verb+b+, et que \verb+min_int+ est
le plus petit entier représentable par Caml.

\vspace{12pt}
\begin{question}
  \'Ecrire la fonction \verb+maximum+ qui calcule le plus grand
  élément d'un tableau, de type \verb+int array -> int+.
\end{question}
\vspace{12pt}

La technique employée ci-dessus s'appelle de l'itération (\em folding\em
en anglais) et consiste à parcourir un tableau élément par élément, tout
en le \em combinant \em avec un \em accumulateur \em dont la valeur
initiale est fixée et dont la valeur finale est renvoyée. 

Dans la question précédente, la combinaison est la fonction \verb+max+,
et la valeur initiale est \verb+min_int+, assurant que la valeur finale de
l'accumulateur sera la plus petite valeur présente dans le tableau.

\vspace{12pt}
\begin{question}
  \'Ecrire la fonction \verb+iter (x,f) a+ qui applique l'algorithme
  d'itération : \verb+x+ est la valeur initiale de l'accumulateur,
  et \verb+f+ est la fonction de combinaison. 

  Ainsi, \verb+iter (x,f) [| a ; b ; c ; d |]+ est équivalent à
  \verb+f (f (f (f x a) b) c) d+. 

  Utiliser cette fonction pour réécrire la fonction \verb+minimum+,
  ainsi que les fonctions \verb+minimum+, \verb+somme+ et 
  \verb+produit+.
\end{question}

\section{Listes}

\subsection{Bases}

Une liste est soit la liste vide \verb+[]+, soit de la forme
\verb+t::q+ où \verb+t+ est un élément appelé tête et \verb+q+
est une liste de même type appelée queue.

Pour travailler sur une liste, on applique du \em pattern matching \em:
\verb+function [] -> vide | t::q -> plein+ est une fonction qui
renvoie \verb+[]+ lorsque appelée sur une liste vide, et 
\verb+plein+ lorsque appelée sur une liste non vide. L'expression
\verb+plein+ peut utiliser les valeurs de \verb+t+ et \verb+q+.

Les fonctions qui traitent les listes sont le plus souvent récursives,
et \verb+plein+ fait l'essentiel de son travail en appelant 
la fonction sur \verb+q+.

\vspace{12pt}
\begin{question}
  Caml propose une fonction \verb+list_length+ de type
  \verb+'a list -> int+ qui renvoie le nombre d'éléments
  d'une liste. Réécrire cette fonction à la main. 
\end{question}
\vspace{12pt}

Pour créer une liste, on écrit le plus souvent une fonction récursive
qui crée une liste en renvoyant \verb+[]+ dans certains cas
et \verb+t::q+ dans d'autres, où \verb+t+ est une valeur calculée
par la fonction, et \verb+q+ est un appel récursif.

\vspace{12pt}
\begin{question}
  \'Ecrire une fonction récursive \verb+diviseurs(n,d)+
  qui calcule le nombre de diviseurs positifs de \verb+n+ supérieurs
  ou égaux à \verb+d+. On pourra remarquer qu'aucun nombre
  strictement supérieur à \verb+n+ ne divise \verb+n+.
\end{question}

\subsection{Itération}

L'itération fonctionne de la même manière sur les listes que sur
les tableaux. 

\vspace{12pt}
\begin{question}
  \'Ecrire une fonction récursive \verb+iter f x l+ telle que
  \verb+iter f x [ a ; b ; c ; d ]+ soit équivalente à 
  \verb+f (f (f (f x a) b) c) d+. Commencer par exprimer
  la relation de récurrence satisfaite par \verb+iter+. 

  En déduire une nouvelle implémentation de \verb+list_length+
  à l'aide de \verb+iter+, ainsi que les fonctions \verb+minimum+
  et \verb+maximum+.

  \'Ecrire les fonctions \verb+exists p l+ et \verb+for_all p l+
  de type \verb+('a -> bool) -> 'a list -> bool+ représentant 
  respectivement $\exists x\in l\,p(l)$ et $\forall x\in l\,p(l)$.
\end{question}

\subsection{Application}

L'application (\em mapping \em) consiste à prendre une fonction $f$
et une liste $[a_0\ldots a_{n-1}]$ et à calculer la liste 
$[f(a_0)\ldots f(a_{n-1})]$. 

\vspace{12pt}
\begin{question}
  Créer une fonction \verb+map f l+ qui calcule l'application de
  la fonction $f$ à la liste $l$. Commencer par exprimer la relation 
  de récurrence satisfaite par \verb+map+, et déterminer son type?

  En déduire une fonction qui calcule la liste des valeurs absolues
  des entiers d'une liste.
\end{question}

\subsection{Filtrage}

Le filtrage (\em filtering \em) consiste à prendre une propriété
binaire (vrai/faux) et une liste, et ne garder que les éléments
de la liste pour lesquels la propriété est vraie, dans le 
même ordre.

\vspace{12pt}
\begin{question}
  Créer une fonction \verb+filter p l+ qui filtre la liste
  \verb+l+ par la propriété \verb+p+. 
\end{question}

\vspace{12pt}
\begin{question}
  Prouver qu'on peut réécrire \verb+filter+ et \verb+map+ 
  à l'aide de \verb+iter+.
\end{question}

\end{document}