\documentclass[10pt]{article}

\usepackage{amsmath,amssymb,fancybox,fancyhdr,lastpage,a4,mdwlist}

\topmargin-0.5cm
\headheight20pt
\textheight23cm
\textwidth17.5cm
\oddsidemargin-1cm
\evensidemargin0cm
\parindent0pt

\def\[{[\![}
\def\]{]\!]}

\begin{document}

\renewcommand{\labelenumi}{\arabic{enumi})}
\renewcommand{\labelenumii}{\alph{enumii})}
\renewcommand{\labelenumiii}{\roman{enumiii})}

\pagestyle{fancy}
\lhead{{\bf MPSI option info}}
\chead{}
\rhead{TP 3~: arbres, types}
\lfoot{\sl Lyc\'ee Chateaubriand}
\cfoot{}
\rfoot{\thepage/\pageref{LastPage}}

\renewcommand{\footrulewidth}{0.4pt}

\begin{enumerate}

\item
La fonction r\'ecursive s'\'ecrit facilement :
\begin{verbatim}
let rec taille = function
  | [] -> 0
  | _ :: q -> 1 + taille q
;;
\end{verbatim}

\item
On utilise un accumulateur qui commencera à la liste vide \texttt{[]} et contiendra à la fin toutes les valeurs de la liste \texttt{l} ins\'er\'ees dans l'ordre inverse :
\begin{verbatim}
let miroir l =
  let rec parcours accu = function
    | [] -> accu
    | t::q -> parcours (t::accu) q
  in parcours [] l
;;
\end{verbatim}

\item
Pour les fonctions suivantes, on fait comme le sugg\`ere l'\'enonc\'e et on force le type des arguments :
\begin{verbatim}
let new_file () : 'a file = [], [];;
\end{verbatim}

\item
Une file est vide si et seulement si les deux listes \texttt{arrive} et \texttt{repart} sont vides :
\begin{verbatim}
let est_vide (f : 'a file) = (f = ([], []));;
\end{verbatim}

\item
On peut utiliser \texttt{fst} et \texttt{snd} pour r\'ecup\'erer \texttt{arrive} et \texttt{repart} :
\begin{verbatim}
let enfile x (f : 'a file) : 'a file = (x::(fst f), snd f);;
\end{verbatim}

On peut aussi utiliser un \texttt{match ... with} :
\begin{verbatim}
let enfile x (f : 'a file) : 'a file =
  match f with
  | arrive, repart -> (x :: arrive), repart
\end{verbatim}

\item
Le sujet ne pr\'ecisait rien, mais on peut utiliser \texttt{failwith "File vide"} pour renvoyer une erreur si les deux listes \texttt{repart} et \texttt{arrive} sont vides :
\begin{verbatim}
let defile (f : 'a file) : 'a * 'a file =
  match f with
  | a, t::q -> t, (a, q)  (* s'il y a une valeur dans repart *)
  | a, [] -> match miroir a with
             | [] -> failwith "File vide"
             | t::q -> t, ([], q)
;;
\end{verbatim}


\stepcounter{enumi}

\item
On ajoute les tailles des deux listes :
\begin{verbatim}
let longueur (f : 'a file) = match f with
    a, r -> (taille a) + (taille r)
;;
\end{verbatim}

\item
On se rappelle que \texttt{\textasciicircum} fait la concat\'enation de deux chaines de caract\`eres :
\begin{verbatim}
let elements (f : int file) =
  let rec ecrire = function
    | [] -> ""
    | a::[] -> string_of_int a
    | t::q -> string_of_int t ^ ">>>" ^ (ecrire q)
  in ecrire (miroir (fst f) @ snd f)
;;
\end{verbatim}

\item
\begin{verbatim}
let arbre_ex = N(N(N(V, 2, V), 15, N(V, 22, V)), 28, N(V, 41, V));;
\end{verbatim}
On peut aussi \'ecrire une fonction \texttt{feuille} qui simplifie l'\'ecriture de \texttt{N(V, x, V)} :
\begin{verbatim}
let feuille x = N(V, x, V);;
let arbre_ex = N(N(feuille 2, 15, feuille 22), 28, feuille 41);;
\end{verbatim}

\item
Les deux fonctions ont la m\^eme forme, la \texttt{hauteur} utilise le \texttt{max} des hauteurs des fils gauche et droite, et la \texttt{taille} utilise la somme :
\begin{verbatim}
let rec hauteur = function
  | V -> -1
  | N (g, _, d) -> 1 + max (hauteur g) (hauteur d)
;;

let rec taille = function
  | V -> 0
  | N (g, _, d) -> 1 + (taille g) + (taille d)
;;
\end{verbatim}

\item
C'est comme \texttt{somme} mais avec \texttt{e +} si on trouve un n{\oe}ud \'etiquett\'e par \texttt{e} au lieu de \texttt{1 +} :
\begin{verbatim}
let rec somme = function
  | V -> 0
  | N (g, e, d) -> e + (somme g) + (somme d)
;;
\end{verbatim}

\item
On ne peut pas faire autrement que d'utiliser une concat\'enation de listes (\texttt{@}) :
\begin{verbatim}
let rec liste_etiquettes = function
  | V -> []
  | N (g, e, d) -> e :: (liste_etiquettes g) @ (liste_etiquettes d)
;;
\end{verbatim}

\item
On utilise un \texttt{match ... with} avec un \texttt{when e = f} :
\begin{verbatim}
let rec descendants e = function
  | V -> []
  | N (_, f, _) as a when e = f -> liste_etiquettes a
  | N (g, _, d) -> (descendants e g) @ (descendants e d)
;;
\end{verbatim}

\item
C'est plus compliqu\'e.
Une fa\,con de l'\'ecrire, avec une fonction r\'ecursive, est la suivante :
\begin{verbatim}
let hamming n =
  let rec aux h2 h3 h5 n =
    if n=0 then []
    else
      let e2, hp2 = defile h2 in
      let e3, hp3 = defile h3 in
      let e5, hp5 = defile h5 in
      let e = min (min e2 e3) e5 in
      e::(aux (enfile (2*e) (if e=e2 then hp2 else h2))
              (enfile (3*e) (if e=e3 then hp3 else h3))
              (enfile (5*e) (if e=e5 then hp5 else h5))
              (n-1))
  in aux (enfile 1 (new_file())) (enfile 1 (new_file()))
         (enfile 1 (new_file())) n
;;
\end{verbatim}

\item
La suite est plus compliqu\'ee.
\begin{verbatim}
type dict = char arbre;;

let rec estDansDict mot (db : dict) = match (mot, db) with
  | (_, V) -> false
  | ([], N (gauche, lettre, droit)) -> lettre = '$'
  | (l::fin_mot, N (gauche, lettre, droit)) ->
      if l = lettre then estDansDictBin fin_mot gauche
      else estDansDictBin mot droit
;;

let contenuDict (db : dict) =
  let rec parcours prefixe = function
    | V -> []
    | N (gauche, lettre, droit) ->
        if lettre = '$'
        then (miroir prefixe)::(parcours prefixe droit)
        else (parcours (lettre::prefixe) gauche) @ (parcours prefixe droit)
  in parcours [] db
;;

let rec ajoutDict mot (db : dict) : dict =
  match mot, db with
  | ([], V) -> N (V, '$', V)
  | ([], N (gauche, lettre, droit)) ->
     if lettre = '$' then db else N (V, n, db)
  | (car::fin_mot, V) -> N (ajoutDict fin_mot V, car, V)
  | (car::fin_mot, N (gauche, lettre, droit)) ->
     if lettre = car
     then N (ajoutDict fin_mot gauche, lettre, droit)
     else N (gauche, lettre, ajoutDict mot droit)
;;
\end{verbatim}

\end{enumerate}

\end{document}