\documentclass{tpcaml}
% \includeversion{prof}
% \excludeversion{eleve}
\includeversion{eleve}
\excludeversion{prof}

\Newassociation{corrige}{Sol}{soltp4sup}
\renewcommand{\Sollabel}[1]{\textbf{\large Exercice #1}}
\Newassociation{corrigese}{Solse}{soltp4sup}
\renewcommand{\Solselabel}[1]{\textbf{\large Sujet d'étude #1}}
\Opensolutionfile{soltp4sup}

\title{TP 4 : Listes}

\begin{document}

\maketitle
\bigskip
Ce TP va vous permettre de manipuler les listes chaînées, ces
structures dynamiques qui peuvent contenir un grand nombre
d'informations, mais telles que la seule information extractible
simplement est celle placée dans leur première case.

Les seules choses que vous devez savoir concernant \textsc{Caml} et
les listes sont les suivantes :
\begin{itemize}
\item une liste se présente sous la forme \texttt{[x; y; z; ...]} ;
\item la liste vide s'écrit \texttt{[]} ;
\item l'opérateur permettant de constituer une liste de \emph{tête}
  \texttt{x} et de \emph{queue} \texttt{suite} est \texttt{x :: suite} ;
\item un canevas quasi universel pour une fonction manipulant des
  listes est le suivant :
  \medskip
  \begin{Programme}
    \caption{Canevas de fonction manipulant des listes}
    \medskip  
\begin{verbatim}
let majoliefonction l =
  match l with :
      []   ->      (* traitement pour la liste vide *)
    | t::q ->      (* traitement pour une liste de ttête t et de queue q*)
;;
\end{verbatim}
  \end{Programme}
\item il existe un opérateur \texttt{@} permettant de concaténer deux
  listes : \texttt{l1 @ l2} est la liste obtenue en mettant
  boût-à-boût les listes \texttt{l1} et \texttt{l2} ; cette fonction
  n'est cependant pas à placer au même rang que l'opérateur
  \texttt{::}. En effet, alors que ce dernier s'exécute en temps
  constant, l'opérateur \texttt{@} a un temps d'exécution
  proportionnel à la longueur de la première liste (expliquez
  pourquoi).
\end{itemize}
\medskip
\begin{Ex}[Itérateurs sur les listes]
  \begin{enumerate}
  \item Soit \texttt{l} une \texttt{'a list}. On dispose d'une
    fonction \texttt{traitement : 'a -> unit} qui effectue des
    effets de bords avec un élément de type \texttt{'a}.
    
    Construire une fonction \texttt{parcours : ('a -> 'b) -> 'a list
      -> unit} qui réalise ce traitement séquentiellement pour chacun
    des éléments de la liste \texttt{l}. Ainsi, si \texttt{l = [a1;
      a2; ... ; an]}, on veut réaliser dans l'ordre
    \texttt{traitement(a1)}, \texttt{traitement(a2)}, ... ,
    \texttt{traitement(an)}.
  \item Utiliser cet \emph{itérateur} pour écrire les fonctions
    suivantes :
    \begin{itemize}
    \item \texttt{imprime}, qui imprime une liste (d'entiers, pour
      simplifier les choses)
    \item \texttt{longueur}, qui renvoie la longueur d'une liste
    \item \texttt{maximum}, qui renvoie le plus grand élément d'une
      liste
    \end{itemize}
  \item Écrire une fonction \texttt{parcours\_a\_l\_envers} qui applique
    la fonction \texttt{traitement} à chaque élément d'une liste en
    commençant par le dernier.
  \end{enumerate}
  \begin{corrige}
  \end{corrige}
\end{Ex}
\medskip
\begin{Ex}[Le gentil petit ordinateur bêgue]
  \begin{enumerate}
  \item Écrire une fonction \texttt{begaie}, qui prend une liste
    \texttt{l = [a1; a2; ... ; an]} et calcule la liste \texttt{[a1;
      a1; a2; a2; a3; ... ; an; an]}.
  \item Même question, mais cette fois-ci chaque élément est répété un
    nombre de fois égal à son rang.
  \item Lors de mes essais de construction d'une fonction
    \texttt{begaieplus}, je suis tombé sur le programme suivant :
    \begin{Programme}
      \caption{Fonction \texttt{begaieplus} ne marchant pas}
      \medskip  
\begin{verbatim}
let rec begaieplus l =
  let rec begaieunelettre lettre liste k =
    match k with
        0 -> liste
      | _ -> lettre :: begaieunelettre lettre liste (k-1)
  and n = ref 0 in
    match l with
        [] -> []
      | t::q -> n := !n +1;
          begaieunelettre t (begaieplus q) !n;;
\end{verbatim}
    \end{Programme}
    Malheureusement, il ne marche pas. Essayez d'expliquer pourquoi.
  \end{enumerate}
  \begin{corrige}
  \end{corrige}
\end{Ex}
\newpage
\begin{Ex}[Miroir, mon beau miroir]
  \begin{enumerate}
  \item Écrire une fonction \texttt{miroir} renvoyant, pour une liste
    \texttt{l = [a1; a2; ... ; an]} donnée, la liste \emph{miroir}
    \texttt{[an; ... ; a2; a1]}.
  \item Déterminer la complexité de cette fonction, en fonction de la
    longueur $n$ de la liste \texttt{l}. Si votre fonction utilise
    l'opérateur \texttt{@}, n'oubliez pas de tenir compte de son temps
    d'exécution.
  \item Que pensez-vous de la fonction suivante ? Evaluez son
    efficacité.
    \begin{Programme}
      \caption{Fonction \texttt{miroir} avec une fonction auxilliaire}
      \medskip  
\begin{verbatim}
let miroir l =
  let rec miroiraux p q =
    match p with
        [] -> q
      | a::r -> miroiraux r (a::q)
  in
    miroiraux l [];;
\end{verbatim}
    \end{Programme}
  \end{enumerate}
  \begin{corrige}
  \end{corrige}
\end{Ex}
\begin{Ex}[Recherche d'une sous-liste]
  
  Soient \texttt{l1 = [a1; a2; ... ; an]} et \texttt{l2 = [b1; b2;
    ... ; bp]} deux listes d'objets de même type. On désire savoir si
  \texttt{l2} est une sous-liste de \texttt{l1}, i.e. s'il existe
  $i$ tel que \texttt{l2 = [ai; ...; ai+p]}. Écrire une fonction
  \texttt{cherche\_sous\_liste} renvoyant le rang de la première
  apparition de \texttt{l2} dans \texttt{l1} s'il y en a une. 
  \begin{corrige}
  \end{corrige}
\end{Ex}
\medskip
\begin{Ex}[Polynômes creux]

  On envisage de construire une bibliothèque de calcul sur les
  polynômes à coefficients entiers. Un polynôme est représenté par une
  liste chaînée de monomes, un monome $a\Xd^e$ étant représenté par un
  couple d'entiers $(a,e)$. Les monomes d'un polynôme sont classés par
  degré croissant et chaque monome a un coefficient non nul.

  On définit le type \texttt{monome} et le type \texttt{polynome} :

  \texttt{type monome = {coef:int; exp:int};;}

  \texttt{type polynome = monome list;;}

  de sorte que si \texttt{a} est un monome, \texttt{a.coef} et
  \texttt{a.exp} renvoient respectivement le coefficient et l'exposant
  du monome.
  \begin{enumerate}
  \item Écrire une fonction \texttt{sommepol} calculant la somme de
    deux polynômes.
  \item Écrire une fonction \texttt{produitpol} calculant le produit de
    deux polynomes.
  \item Sauriez-vous écrire une fonction \texttt{quotient} renvoyant
    le quotient (et le reste, pourquoi pas ?) de la division
    euclidienne d'un polynôme par un autre.
  \item Essayez d'imaginer un procédé similaire concernant les
    matrices creuses.
  \end{enumerate}
  \begin{corrige}
  \end{corrige}
\end{Ex}
\medskip
\begin{Ex}[Tri fusion]

  On souhaite trier une liste (d'entiers pour simplifier). Pour cela,
  on applique l'algorithme suivant, directement issu de la méthode
  ``diviser pour régner'' :
  \begin{itemize}
  \item découpage de la liste en deux sous-listes de longueur
    approximativement égales ;
  \item tri (récursif) des deux sous-listes ;
  \item fusion des deux sous-listes triées en une liste elle-même
    triée.
  \end{itemize}
  \begin{enumerate}
  \item Écrire la fonction \texttt{decoupe} de découpage.
  \item Écrire la fonction \texttt{fusion} effectuant la fusion de
    deux listes triées.
  \item Assemblez tout cela en une fonction \texttt{trifusion} triant
    une liste d'entiers passée en argument.
  \end{enumerate}
  \begin{corrige}
  \end{corrige}
\end{Ex}
\medskip
\begin{Ex}[Tri rapide]

  Dans l'algorithme de tri rapide (\emph{quick sort} des anglophones),
  on met encore en oeuvre la méthode ``diviser pour régner'', mais la
  fonction de découpage (et donc aussi celle de fusion) est différente
  : à partir d'un \emph{pivot} (un élément particulier de la liste),
  on construit deux sous-listes : celles constituée des éléments plus
  petits que le pivot, et celles constituées des éléments plus grands.
  \begin{enumerate}
  \item Construire cette nouvelle fonction de découpage.
  \item Construire la fonction de fusion associée.
  \item En déduire une fonction \texttt{qsort} triant une liste.
  \end{enumerate}
  \begin{corrige}
  \end{corrige}
\end{Ex}
\medskip
\begin{Ex}[Un petit tour dans les sources]

  La bibliothèque \textsc{Caml} contient la fonction de tri suivante :
  \begin{Programme}
    \caption{Le fichier source \texttt{sort.ml}}
    \medskip  
\begin{verbatim}
(* Merging and sorting *)

let merge order =
  merge_rec where rec merge_rec = fun
    [] l2 -> l2
  | l1 [] -> l1
  | (h1::t1 as l1) (h2::t2 as l2) ->
      if order h1 h2 then h1 :: merge_rec t1 l2 else h2 :: merge_rec l1 t2
;;

let sort order l =
  let rec initlist = function
      [] -> []
    | [e] -> [[e]]
    | e1::e2::rest ->
        (if order e1 e2 then [e1;e2] else [e2;e1]) :: initlist rest in
  let rec merge2 = function
      l1::l2::rest -> merge order l1 l2 :: merge2 rest
    | x -> x in
  let rec mergeall = function
      [] -> []
    | [l] -> l
    | llist -> mergeall (merge2 llist) in
  mergeall(initlist l)
;;
\end{verbatim}
  \end{Programme}
  Expliquez son fonctionnement.
  \begin{corrige}    
  \end{corrige}
\end{Ex}
\Closesolutionfile{soltp4sup}
\clearpage
\titre{Corrigé (partiel) du TP 4 : Listes}
\Readsolutionfile{soltp4sup}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 

\begin{Ex}
  
  \begin{corrige}
    
  \end{corrige}
\end{Ex}