Fiche Memo Listes, Tuples et Tableaux en OCaml (2024-2025) - PDF

MP2I — 2024 – 2025 Fiche Memo Listes, tuples et tableaux en OCaml - Gérard Rozsavolgyi Informatique MP2I Les list en OCaml...

MP2I — 2024 – 2025 Fiche Memo Listes, tuples et tableaux en OCaml - Gérard Rozsavolgyi Informatique MP2I Les list en OCaml Astuce Si on souhaite calculer tous les carrés des éléments d’une liste d’entiers, on En OCaml, list est un des types fondamentaux, il s’agit d’une structure de données abstraite peut procéder comme suit : comme la pile que nous avons étudiée, c’est à dire que pour les utiliser, on n’a pas besoin de connaître l’implémentation précise sous-jacente, qui est encapsulée mais simplement les 1 let rec carre_liste l = OCaml constructeurs et opérateurs nous permettant de les manipuler, ainsi que les complexités as- 2 match l with sociées. Le module List fournit un ensemble de fonctions utiles pour manipuler les list. 3 | [] -> [] 4 | hd::tl -> (hd * hd) :: carre_liste tl Si on veut faire la même chose avec des cubes, on peut bien sûr procéder de Création de listes la même façon : On peut créer une list de plusieurs façons différentes : 1 let rec cube_liste l = OCaml Céation d’une liste vide : [] 2 match l with Création d’une liste de taille fixée : ["Alice"; "Bob"; "Cliff"] 3 | [] -> [] Construction d’une liste par sa tête et queue , appelés aussi head et tail, comme dans 4 | hd::tl -> (hd * hd * hd) :: cube_liste tl l’exemple : 1 :: [2;3;4;5] qui donne - : int list = [1; 2; 3; 4; 5] la nouvelle Mais il est plus simple de réaliser tout cela avec List.map : Construction d’une liste par concaténation : [1;2] @ [3;4;5] qui construit la nou- liste(c’est une nouvelle strucutre). 1 let carre_list = List.map(fun x -> x * x);; OCaml velle liste - : int list = [1; 2; 3; 4; 5]. On peut également utiliser la fonction 2 let cube_list = List.map(fun x -> x * x * x);; List.append à deux arguments, équivalente à l’opérateur @ : List.append [1;2] [3;4;5] construit aussi la nouvelle List - : int list = [1; 2; 3; 4; 5]. Attention ! [1,2,3] est une liste comportant un unique élément, le tuple 1,2,3. Ne pas mélanger listes et tuples ou listes et tableaux en OCaml : Fonctions utiles sur les listes L’élément [|1; 2; 3; 4; 5|] est du type array où la taille est fixe mais Elle est donc du type (int * int * int) list. 1 dont le contenu est mutable contrairement aux list OCaml. (cf ci- dessous) Voici les opérations utiles à connaître sur les listes : Méthode Rôle List.append ou @ Concatène deux listes List.mem Vérifie si un élément est présent dans la liste Opérations de base sur les listes List.length Calcule la longueur d’une liste List.mem pour tester l’appartenance : List.mem 3 l0 1 :: [2;3;4;5];; renverra List.map Applique une fonction à chaque élément de la liste List.for_all Si un prédicat est vérifié sur tous les éléments de la liste List.length pour obtenir la longueur d’une liste. true. List.rev Inverse l’ordre des éléments dans la liste List.map pour appliquer une fonction à tous les éléments d’une liste (cf encadré ci- List.fold_left Accumule des valeurs en parcourant la liste de gauche à droite List.fold_right Accumule des valeurs en parcourant la liste de droite à gauche List.filter pour sélectionner certains éléments d’une liste selon un prédicat (fonc- dessous) List.filter Filtrage par prédicat de certains éléments de la liste List.iter Applique une fonction à effet de bord à chaque élément de la liste tion). List.nth Retourne le n-ième élément de la liste MP2I — 2024 – 2025 Fiche Memo Listes, tuples et tableaux en OCaml - Gérard Rozsavolgyi Informatique MP2I Exemples on la recode aisément aussi : List.mem 1 (* filtrage général selon un predicat 'a -> bool *) OCaml 2 let rec filter predicat liste = 1 List.length ["Alice"; "Bob"; "Cliff"];; OCaml 3 match liste with 2 int = 3 4 | [] -> [] 5 | hd::tl -> if predicat hd then hd::filter predicat tl Attention ! else filter predicat tl La complexité est bien en 𝒪(𝑛), vous ne révez pas, puis qu’on fait quelque 6 chose comme : List.for_all 1 let rec longueur lst = OCaml C’est une variante qui vérifie qu’un prédicat est vrai pour toute la liste : 2 match lst with 3 | [] -> 0 1 List.for_all pair [2;4;6;8];; OCaml | _ :: tl -> 1 + longueur tl 2 - : bool = true 1 4 A stocker quelque part si on l’utilise à plusieurs reprises … List.nth Renvoie le nème élément de la liste, mais pas en temps constant ! List.map La fonction à retenir entre toutes. Elle consiste à appliquer une fonction à tous les éléments List.iter d’une list : Passe en revue tous les éléments d’une liste et applique un effet de bord. 1 List.map (fun x -> x * x) [1;2;3;4];; OCaml Astuce 2 - : int list = [1; 4; 9; 16] List.iter peut notamment servir à faire des affichages, des écritures sur fi- On la retrouve dans array et il est possible (souhaitable) de la redéfinir lorsqu’on définit ses chier, ou effectuer des vérifications sur les éléments d’une liste. Par exemple, propres types de données (ensembles, arbres, etc.) pour vérifier qu’aucune chaine n’est vide dans une liste : Pour les listes, on peut par exemple la coder ainsi : 1 let validate_strings str_list = OCaml 1 let rec my_map f liste = match liste with OCaml 2 List.iter (fun s -> 2 | [] -> [] 3 if s = "" then 3 | hd::tl -> (f hd) :: my_map f tl 4 Printf.printf "Erreur : chaîne vide trouvée!\n" 5 ) str_list;; 6 validate_strings ["Hello"; ""; "World"; "OCaml"; ""];; List.filter Attention ! Pour filtrer, c’est à dire sélectionner seulement certains éléments d’une liste selon un critère codé sous la forme d’une fonction prédicat qui à un élément de la liste associe un booléen. List.iter est du type unit comme Printf.printf c’est à Par exemple pour obtenir les nombres pairs d’une liste : dire purement à effet de bord, avec comme unique valeur pos- sible (), semblable au void du C. Dans un notebook OCaml, let pair x = x mod 2 = 0;; OCaml 1 il faut parfois vider le buffer de sortie pour voir tous les affi- 1 2 filter pair [1;2;3;4;5;6;7];; chages en attente à l’aide de l’instruction flush stdout;;. 3 - : int list = [2; 4; 6]