Introduction à la programmation fonctionnelle

Cours 6

kn@lmf.cnrs.fr
https://usr.lmf.cnrs.fr/~kn

Au menu

On va présenter plusieurs algorithmes avancés sur les listes :

Nous allons coder ces fonctions en direct. Leur code sera ensuite mis en ligne, après le TP.

Lors des révisions, il sera plus intéressant de regarder à nouveau la vidéo du cours plutôt que de lire le fichier de code final.

Sert de préparation à l'examen.

Exercices simples

Affichage générique d'une liste

Écrire une fonction pr_list :

string -> ('a -> unit) -> 'a list -> unit

Prenant en argument :

Le séparateur ne doit pas être affiché pour les listes de longueur 0 ou 1.

S'en servir pour écrire une fonction pr_ill affichant une liste de listes d'entiers.

List.filter, List.map, List.fold_left

  1. Donner le code de List.filter, List.map, List.fold_left
  2. Écrire List.rev en utilisant List.fold_left
  3. Écrire List.iter en utilisant List.fold_left
  4. Écrire List.map en utilisant List.fold_left et List.rev

Listes triées

  1. Insérer une valeur au bon endroit dans une liste triée insert : ('a -> 'a -> int) -> 'a -> 'a list -> 'a list
  2. Retirer les doublons d'une liste triée uniq : ('a -> 'a -> int) -> 'a list -> 'a list

Les deux fonction prennent en paramètre une fonction de comparaison comp : 'a -> 'a -> int telle que comp a b renvoie un entier négatif si a<b, nul si a=b et positif si a > b.
On suppose que les éléments de la liste donnée en argument sont ordonnés selon cette fonction comp.
La fonction prédéfinie compare peut être utilisée comme comparaison générique.

Algorithmes avancés

Liste des sous-listes

Écrire une fonction récursive

sublists : 'a list -> 'a list list

telle que sublists l qui renvoie la liste de toutes les sous-listes de l. Exemple:

sublists [ 1;2;3;4 ] ⇒ [ []; [ 4 ]; [ 3 ]; [ 3; 4 ]; [ 2 ]; [ 2; 4 ]; [ 2; 3 ]; [ 2; 3; 4 ]; [ 1 ]; [ 1; 4 ]; [ 1; 3 ]; [ 1; 3; 4 ]; [ 1; 2 ]; [ 1; 2; 4 ]; [ 1; 2; 3 ]; [ 1; 2; 3; 4 ] ]

(l'ordre n'est pas significatif)

Quick sort

Algorithme de tri efficace, basé sur le principe « diviser pour régner »

Attention, le pivot doit permettre de partager à peu près la liste en deux sous-listes de même tailles, sinon l'algorithme n'est pas efficace

Le TP permetra de comparer cet algorithme à un algorithme plus naïf