\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}\noindentClairement, 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}\noindentQuel 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}\DoubleEtoilePar 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}