\begin{question}
R�digez en Caml une fonction de signature: 

\begin{programme}
\begin{verbatim}
filtre : ('a -> bool) -> 'a list -> 'a list 
\end{verbatim}
\end{programme}

\noindent sp�cifi�e comme suit: \verb+filtre p l+ dresse la liste 
(pr�sent�e dans un ordre quelconque) des �l�ments de $\ell$ qui 
satisfont le pr�dicat $p$. 
Par exemple, \verb+filtre (fun x -> x>0) [-2;3;7;-1;0;11;-8]+ doit 
rendre (� l'ordre pr�s) la liste \verb+[3;7;11]+.
\end{question}

\begin{question}
R�digez en Caml une fonction de signature: 

\begin{programme}
\begin{verbatim}
cherche_paires : 'a list -> 'a list 
\end{verbatim}
\end{programme}

\noindent sp�cifi�e comme suit: \verb+cherche_paires l+ dresse la liste 
(pr�sent�e dans un ordre quelconque) des �l�ments qui apparaissent 
\emph{exactement} deux fois dans la liste $\ell$. 
Par exemple, \verb+cherche_paires [8;2;3;8;1;3;1;9;7]+ doit 
rendre (� l'ordre pr�s) la liste \verb+[8;3;1]+.
\end{question}

\begin{panneau}
Nous d�finissons la fonction: 

\begin{programme}
\begin{verbatim}
let rec castor c = match c with 
 | (_,[]) | (_,[_]) -> c 
 | (t,a::b::q) when a<=b -> let (t',r) = castor(t,b::q) in (t',a::r) 
 | (t,a::b::q) -> let (_,r) = castor(t,a::q) in (true,b::r) ;; 
\end{verbatim}
\end{programme}

\noindent
Clairement, le type de \verb+castor+ est 
\verb+(bool,'a list) -> (bool,'a list)+. 
Soient $b$ un bool�en, $\ell = (x_1,\ldots,x_n)$ une liste, 
et $(b',\ell')$ le r�sultat rendu par \verb+castor(b,l)+.
\end{panneau}

\begin{panneau}
Pour les trois questions suivantes, les preuves doivent se faire par 
induction structurelle.
\end{panneau}

\begin{question}
Montrez que $\ell'$ a m�me longueur que $\ell$.
\end{question}

\begin{panneau}
Pour les trois questions suivantes, nous supposons $n�1$; autrement dit, 
la liste $\ell$ n'est pas vide.
\end{panneau}

\begin{question}
Nous avons donc $\ell' = (y_1,\ldots,y_n)$. 
Montrez que les listes $\ell$ et $\ell'$ contiennent les m�mes �l�ments, 
� l'ordre pr�s.
\end{question}

\begin{question}
Montrez que $y_n$ est le plus grand �l�ment de $\ell$.
\end{question}

\begin{question}
Caract�risez les listes $\ell$ pour lesquelles l'�valuation de 
\verb+castor(false,l)+ donne un couple dont la premi�re composante 
est \verb+true+.
\end{question}

\begin{question}
Nous d�finissons la fonction: 

\begin{programme}
\begin{verbatim}
let rec pollux l = 
 match castor(false,l) with 
  | (false,r) -> r 
  | (true,r) -> pollux r ;; 
\end{verbatim}
\end{programme}

\noindent
Quel est le r�sultat rendu par \verb+pollux l+ o� 
\verb+l+ est une liste $(x_1,\ldots,x_n)$?
\end{question}

\begin{question}
L'unit� de co�t est la comparaison entre deux �l�ments d'une liste. 
Exprimez le co�t maximal de l'�valuation de \verb+pollux l+, 
en fonction de la longueur $n$ de la liste $\ell$.
\end{question}

\endinput

\begin{question}\DoubleEtoile
Par m�garde, Marcel \NomPropre{Malencontreux}, en saisissant 
la fonction \verb+castor+, a saisi � la ligne~3 \fbox{\texttt{a<b}} 
au lieu de \fbox{\texttt{a<=b}}. 
Il constate que, dans certains cas, cette fonction tourne ind�finiment. 
Expliquez!
\end{question}