\documentclass{article}
\usepackage{amssymb, amsmath, geometry, multicol, stmaryrd}
\usepackage{listings, xcolor}

\definecolor{red}{rgb}{0.8, 0.0, 0.0}
\definecolor{green}{rgb}{0.0, 0.8, 0.0}
\definecolor{blue}{rgb}{0.0, 0.0, 0.8}
\definecolor{orange}{rgb}{0.8, 0.5, 0.0}
\definecolor{lightgreen}{rgb}{0.6, 0.9, 0.6}

\lstloadlanguages{[Objective]Caml}
\lstdefinestyle{mystyle}{
    backgroundcolor=\color{white},
    commentstyle=\color{orange},
    keywordstyle=\color{blue},
    numberstyle=\tiny\color{blue},
    basicstyle=\footnotesize\ttfamily,             
    captionpos=b,
    numbers=none,
    numbersep=5pt,
    showspaces=false,
    showstringspaces=false,
    showtabs=false,
    tabsize=4
}
\lstset{style=mystyle,
        frameround=fttt,
        frame=trBL, 
        linewidth=15cm,
        aboveskip=5pt,
        belowskip=15pt,
        language=caml
}

\geometry{tmargin=.7in, bmargin=.75in, lmargin=.75in, rmargin = .75in}

\begin{document}
\setlength{\parindent}{0mm}

\title{OCaml - Listes}
\author{Aubin SIONVILLE}
\date{MPI Clemenceau - 2021-2023}
\maketitle

\section{Bases}

\subsection*{Dernier élément d'une liste}
    Fonction récursive retournant le dernier élément d'une liste d'un type quelconque.\\
    Cette fonction doit lever une exception si la liste est vide.
    \begin{lstlisting}
        let rec last (l: 'a list): 'a =
        match l with
        | x :: [] -> x
        | _ :: l' -> last l'
        | _ -> raise (Invalid_argument "liste vide");;
    \end{lstlisting}
    
    Fonction récursive retournant le dernier élément d'une liste d'un type quelconque.\\
    Cette fonction doit retourner \textbf{None} si la liste est vide et \textbf{Some(x)} si la liste contient au moins un élément et que le dernier élément est $x$

    \begin{lstlisting}
        let rec last_option (l: 'a list): 'a option =
        match l with
        | x :: [] -> Some(x)
        | _ :: l' -> last_option l'
        | _ -> None;;
    \end{lstlisting}

\subsection*{Miroir d'une liste}
    Fonction retournant la liste miroir d'une liste d'un type quelconque.
    \begin{lstlisting}
        let rev (l: 'a list): 'a list =
            let rec aux (l: 'a list) (res: 'a list): 'a list =
                match l with
                | [] -> res
                | x :: l' -> aux l' (x :: res)
            in aux l [];;
    \end{lstlisting}

    Fonction retournant la liste miroir d'une liste d'un type quelconque.
    En utilisant \textbf{List.fold\_left}.

    \begin{lstlisting}
        let rev_fold (l: 'a list) = List.fold_left (fun res x -> x :: res) [] l;;
    \end{lstlisting}

\subsection*{Concaténation de deux listes}
    Fonction permettant de calculer la concaténation de deux listes. \\
    Sans fonctionnelle d'itération.
    \begin{lstlisting}
        let concat (lg: 'a list) (ld: 'a list): 'a list =
            let rec verse (todo: 'a list) (lres: 'a list): 'a list =
                match todo with
                | [] -> lres
                | x :: l' -> verse l' (x :: lres)
            in verse (List.rev lg) ld;;
    \end{lstlisting}

    Fonction permettant de calculer la concaténation de deux listes.
    En utilisant \textbf{List.fold\_left}.

    \begin{lstlisting}
        let concat_fold (lg: 'a list) (ld: 'a list): 'a list =
            List.fold_left (fun res x -> x :: res) ld (List.rev lg);;
    \end{lstlisting}

\subsection*{Suppression de toutes les occurrences d'un élément}
    Fonction prenant en arguments une liste $l$ et un élément $x$ et calculant la liste $l$ privée de toutes les occurrences de $x$.
    \begin{lstlisting}
        let rec remove_all (l: 'a list) (x: 'a): 'a list =
            match l with
            | [] -> []
            | y :: l' ->
                if x = y then
                    remove_all l' x
                else y :: remove_all l' x;;
    \end{lstlisting}

\subsection*{Découpage de listes}
    Fonction prenant en arguments une liste $l$ et un indice $i$ et retournant deux listes : \\
    La sous-liste des éléments de $l$ d'indice inférieurs stricts à $i$ et la sous liste des éléments de $l$ d'indices supérieurs à $i$. \\
    La fonction devra être récursive et ne pas faire appel à des fonctions récursives auxiliaires.

    \begin{lstlisting}
        let decoupe (l: 'a list) (i: int): ('a list * 'a list) =
            let rec aux (g: 'a list) (d: 'a list) (i: int) =
                if i = 0 then (List.rev g, d)
                else match d with
                    | [] -> (List.rev g, d)
                    | x :: l' -> aux (x :: g) l' (i - 1)
            in aux [] l i;;
    \end{lstlisting}

    Fonction prenant en argument une liste $l$ et la découpant en deux listes\\
    Dans la première on rangera les éléments d'indices pairs dans $l$, dans la seconde on rangera les éléments d'indices impairs dans $l$. \\
    L'ordre des éléments dans les listes résultats devra être celui de la liste d'entrée.

    \begin{lstlisting}
        let un_sur_deux (l: 'a list): ('a list * 'a list) =
            let rec aux (lat: 'a list) (lres1: 'a list) (lres2: 'a list) =
                match lat with
                | [] -> (lres1, lres2)
                | a::[] -> (a::lres1, lres2)
                | a::b::l' -> aux l' (a::lres1) (b::lres2)
            in let (l1, l2) = aux l [] []
            in (List.rev l1, List.rev l2);;
    \end{lstlisting}

\subsection*{Palindrome}
    Fonction testant si une liste est un palindrome. \\
    La fonction devra être en $\mathcal{O}(n)$ où $n$ est la longueur de la liste.

    \begin{lstlisting}
        let palindrome (l: 'a list): bool =
            l = rev(l);;
    \end{lstlisting}

\newpage

\section*{Listes de listes}

    \subsection*{Mise à plat}

    Fonction prenant en argument une liste $l$ de listes et retournant la liste des éléments des sous-listes de $l$, en utilisant $@$ sans être en $\mathcal{O}(n^2)$.

    \begin{lstlisting}
        let flatten_a (l: 'a list list): 'a list =
            let rec aux (ll: 'a list list) (lres: 'a list): 'a list =
                match ll with
                | [] -> lres
                | x :: l' -> aux l' ((List.rev x) @ lres)
            in aux l [];;
    \end{lstlisting}

    Fonction prenant en argument une liste $l$ de listes et retournant la liste des éléments des sous-listes de $l$, en utilisant deux fonctions récursives auxiliaires. La fonction doit être récursive terminale.

    \begin{lstlisting}
        let flatten_rt (l: 'a list list): 'a list =
            let rec grand_pas (todo: 'a list list) (lres: 'a list): 'a list =
                match todo with
                | [] -> List.rev lres
                | x :: l' -> petit_pas x l' lres
            and petit_pas (une_list: 'a list) (todo: 'a list) (lres: 'a list): 'a list =
                match une_list with
                | [] -> grand_pas todo lres
                | x :: l' -> petit_pas l' todo (x :: lres)
            in grand_pas l [];;
    \end{lstlisting}

    Fonction prenant en argument une liste $l$ de listes et retournant la liste des éléments des sous-listes de $l$, en utilisant \textbf{List.fold\_left}.

    \begin{lstlisting}
        let flatten_f (l: 'a list list): 'a list =
            List.fold_left ( fun acc l -> 
                List.fold_left (fun acc x ->
                    x :: acc
                ) acc l
            ) [] l
            |> List.rev;;
    \end{lstlisting}

\newpage

\section*{Listes et comparaisons}

\subsection*{Mini et maxi}

    Fonction prenant en argument une liste $l$ et retournant un couple contenant le minimum et le maximum de $l$. La fonction doit être récursive et ne pas faire appel à des fonctions récursives auxiliaires. On lève une exception si la liste est vide.

    \begin{lstlisting}
        let min_max (l: 'a list): 'a * 'a =
            match l with
            | [] -> raise (Invalid_argument "Liste vide")
            | x :: [] -> (x, x)
            | x :: l' ->
                let mini, maxi = min_max l
                in (min x mini, max x maxi);;
    \end{lstlisting}

    Fonction prenant en argument une liste $l$ et retournant un couple contenant le minimum et le maximum de $l$. La fonction doit être récursive terminale et peut utiliser une fonction récursive auxiliaire. On lève une exception si la liste est vide.

    \begin{lstlisting}
        let min_max_rt (l: 'a list): 'a * 'a =
            let rec aux (l: 'a list) (mini: 'a) (maxi: 'a): 'a * 'a =
                match l with
                | [] -> (mini, maxi)
                | x :: l' -> aux l' (min x mini) (max x maxi)
            in 
            match l with
            | [] -> raise (Invalid_argument "Liste vide")
            | x :: l' -> aux l' x x;;
    \end{lstlisting}

    Fonction prenant en argument une liste $l$ et retournant un couple contenant le minimum et le maximum de $l$ en utilisant \textbf{List.fold\_left}. On lève une exception si la liste est vide.

    \begin{lstlisting}
        let min_max_f (l: 'a list): 'a * 'a =
            match l with
            | [] -> raise (Invalid_argument "Liste vide")
            | x :: l' ->
                List.fold_left (fun (mini, maxi) x ->
                    (min x mini, max x maxi)
                ) (x, x) l';;
    \end{lstlisting}

\subsection*{Sous-séquences croissantes}

    Fonction prenant en argument une liste $l$ et retournant une liste de sous-séquences de $l$ croissantes maximales pour l'extension à gauche. \\
    Exemple : $[1,2,4,8,5,3,4,5,1] -> [[1,2,4,8], [5], [3,4,5], [1]]$

    \begin{lstlisting}
        let sous-sequences-croissantes (l: 'a list): ('a list list) =
            let rec aux (ll: 'a list) (ltemp: 'a list) (lres: 'a list list): 'a list =
                match ll, ltemp with
                | [], [] -> List.rev lres
                | [], _ -> List.rev (ltemp :: lres)
                | x :: l', [] -> aux l' (x :: []) lres
                | x :: l', y :: l'' ->
                    if x >= y then aux l' (x :: ltemp) lres
                    else aux l' (x :: []) ((List.rev ltemp) :: lres)
            in aux l [] [];;
    \end{lstlisting}

\newpage

    \subsection*{Tris}

    Fonction prenant en arguments une liste de $\mathrm{'a}$ élément, un entier $k$ et une fonction sur les $\mathrm{'a}$ éléments à valeur dans $\llbracket 0, k \rrbracket$ et retournant la liste des éléments de $l$ triés par ordre croissant de leur valeur par la fonction $f$. La complexité de l'algorithme doit être en $O(\mathrm{max}(n,k))$.

    \begin{lstlisting}
        let rangement (l: 'a list) (k: int) (f: 'a -> int): 'a list =
            let aux = Array.make k [] in
            List.iter (fun x ->
                let i = (f x) in
                aux.(i) <- x :: aux.(i)
            ) l;
            let ll = Array.to_list aux in
            List.flatten ll;;
    \end{lstlisting}

\newpage

\section*{Utilisations classiques}

    \subsection*{Tri fusion}

    Fonction prenant en argument une liste $l$ et la triant par un tri fusion.

    \begin{lstlisting}
        let rec fusion (l1: 'a list) (l2: 'a list): 'a list =
            match l1, l2 with
            | [], _ -> l2
            | _, [] -> l1
            | x :: l1', y :: l2' ->
                if x <= y then x :: fusion l1' l2
                else y :: fusion l1 l2';;

        let rec tri_fusion (l: 'a list): 'a list =
            match l with
            | [] -> []
            | [x] -> [x]
            | _ ->
                let l1, l2 = List.split_at (List.length l / 2) l in
                fusion (tri_fusion l1) (tri_fusion l2);;
    \end{lstlisting}

    \subsection*{Files}

    Implémentation du type File avec deux listes. On assurera une complexité en $\mathcal{O}(1)$ pour chaque opération.

    \begin{lstlisting}
        type 'a file = 'a list * 'a list;;

        let file_vide: 'a file = ([], []);;

        let est_vide (f: 'a file): bool =
            match f with
            | [], [] -> true
            | _ -> false;;

        let enfiler (f: 'a file) (x: 'a): 'a file =
            match f with
            | l1, l2 -> (x :: l1, l2);;

        let defiler (f: 'a file): 'a file =
            match f with
            | [], [] -> raise (Invalid_argument "File vide")
            | l1, [] -> (List.rev l1, [])
            | l1, x :: l2 -> (l1, l2);;

        let tete (f: 'a file): 'a =
            match f with
            | [], [] -> raise (Invalid_argument "File vide")
            | l1, [] -> List.hd (List.rev l1)
            | l1, x :: l2 -> x;;
    \end{lstlisting}

    \subsection*{Permutations}

    Fonction prenant en argument une liste $l$ et retournant une liste de toutes les permutations de $l$.

    \begin{lstlisting}
        let rec permutations (l: 'a list): 'a list list =
            match l with
            | [] -> [[]]
            | x :: l' -> let ll = permutations l' 
                in List.fold_left (fun lres l ->
                    let rec aux (l: 'a list) (lres: 'a list list): 'a list list =
                        match l with
                        | [] -> lres
                        | x :: l' -> aux l' ((x :: l) :: lres)
                    in aux l lres
                ) [] ll;;
    \end{lstlisting}

    \subsection*{Liste des booléens}

    Fonction prenant en argument un entier $n$ et retournant la liste $2^n$ listes contenant $n$ booléens.

    \begin{lstlisting}
        let rec liste_bool (n: int): bool list list =
            if n = 0 then [[]]
            else
                let ll = liste_bool (n - 1) in
                List.fold_left (fun lres l ->
                    (true :: l) :: (false :: l) :: lres
                ) [] ll;;
    \end{lstlisting}


\end{document}