Reprenez quelques fonctions du TD sur les listes et programmez les en utilisant

• une définition directe,
• la fonction List.fold_right.

Programmez la fonction renverse comme nous l'avons fait en TD, puis comparer l'efficacité de votre fonction avec celle de la fonction List.rev, qui fait la même chose.

Expliquez la démarche que vous suivez pour faire cette comparaison en mettant des commentaires dans votre fichier Caml.

La fonction List.map permet d'appliquer une fonction à tous les éléments d'une liste.

Écrivez une fonction pam qui prend en arguments :

• une valeur,
• une liste de fonctions

et qui renvoie la liste des valeurs obtenues en appliquant les fonctions de la liste à la valeur. Par exemple : pam 3 [ (fun x -> x+1) ; (fun x -> x*x) ; (fun x -> 42-x) ] donnera [4; 9; 39].

Essayez de deviner le type de cette fonction sans regarder le résultat donné par Caml.

Écrivez la fonction pam uniquement à partir de la fonction map.

Programmez une fonction insere qui permet d'insérer un élément à sa place dans une liste triée.

Programmez ensuite le tri par insertion : tri_insertion en utilisant la fonctions insere

Programmez une fonction fusionne qui permet de fusionner deux listes triées en une seule liste triée.

Attention : vous n'avez pas le droit d'utiliser la fonction insere pour programmer fusionne.

Programmez une fonction separe qui permet de séparer une liste quelconque en deux listes de taille équivalente.

Programmez maintenant le tri fusion : tri_fusion en utilisant les fonctions separe et fusionne.

Comparez l'efficacité de vos deux algorithmes. Qu'en pensez-vous ?

Comparez également l'efficacité de vos deux algorithmes avec l'efficacité de l'algorithme de Caml :

let tri_caml l = List.sort compare l;;

Expliquez la démarche que vous suivez pour faire cette comparaison en mettant des commentaires dans votre fichier Caml.

Imaginez la situation suivante : vous avez une liste de points dans le plan, c'est à dire une liste de paires de flottants (type float*float list).

Vous aimeriez trier cette liste selon la hauteur de points, c'est à dire suivant leur seconde coordonnée.

Comment pourrait-on profiter des capacités de Caml à manipuler des fonctions pour généraliser nos fonctions de tri pour les permettre de fonctionner dans ce cas là, ou bien dans d'autres cas (tri en sens inverse, tri par ordre alphabétique, ...).

(Bonus)

Un algorithme de tri est dit stable quand il ne modifie pas l'ordre relatifs des éléments « égaux ». (Par exemple, lorsque vous triez vos fichiers par taille croissante, vous aimeriez que pour les fichiers de même taille, l'ordre soit toujours l'ordre alphabétique.)

Est-ce que vos programmes de tri par insertion et de tri fusion sont stables ?

Sinon, pouvez-vous les rendre stables ?