1) Il existe de nombreuses fonctions travaillant sur les listes. En voici quelques-unes :
   List.length calcule la longueur d'une liste (nombre d'éléments)
   @ sert à concaténer deux listes, c'est-à-dire à former la liste composée successivement des éléments de la première et de la seconde
   List.rev permet de renverser une liste, c'est-à-dire de placer le premier élément en dernière place, etc...
Vous devez recréer ces trois fonctions en utilisant seulement des filtrages et l'opérateur permettant d'insérer UN élément au début d'une liste (5::[2;4] donne [5;2;4]).
Dans l'ordre, il est plus simple de définir List.length, puis List.rev, puis @.
List.length est une simple fonction récursive : si la liste est vide, on rend 0. Sinon, on rend 1 plus la longueur de la queue.
let rec longueur l = match l with
   |[] -> 0
   |t::q -> 1 + (longueur q);;
Pour définir List.rev, on se base sur un fait simple : quand on prend la tête d'une liste et qu'on la rajoute en tête d'une autre liste, les éléments dans la nouvelle liste sont dans l'ordre inverse que dans la première liste (de même que si vous avez une pile de papier et que vous les prenez un par un pour les mettre sur une autre pile, vous changez l'ordre). On applique donc simplement ce principe :
let renverse l =
   let rec aux li resu = match li with
       |[] -> resu
       |t::q -> aux q (t::resu)
in aux l [];;
Pour concaténer deux listes, on va prendre les éléments de la première et les mettre en tête de la seconde. Sauf que si on fait ça directement, on va inverser l'ordre des éléments de la première, ce qu'on veut éviter. On va donc avant de prendre les éléments de la première liste l'inverser :
let concatene l1 l2 =
   let rec aux li resu = match li with
      |[] -> resu
      |t::q -> aux q (t::resu)
in aux (renverse l1) l2;;

2) Vous devez écrire une fonction appartient qui prend en argument une liste et un objet quelconque (du même type que ceux de la liste) et qui dit si cet objet est un élément de la liste en rendant un booléen.
On fait ici une fonction récursive : on teste d'abord si la liste est vide. Dans ce cas, l'élément ne lui appartient pas et on rend false. Sinon, on prend la tête de la liste. Si elle est égale à l'élément, on a trouvé et on rend true. Sinon on recommence avec la queue de la liste.
let rec appartient liste a = match liste with
   |[] -> false
   |t::q -> if t = a then true else appartient q a;;
Mais c'est assez maladroit : le deuxième cas fait un test et rend un booléen. On peut donc directement calculer un booléen :
let rec appartient liste a = match liste with
   |[] -> false
   |t::q -> (t = a)||(appartient q a);;
Remarque : cette fonction existe déjà dans Caml, elle s'appelle List.mem.

3) Ecrivez une fonction fusion qui prend deux listes, dans lesquelles on suppose que chaque élément n'est présent qu'une fois, et qui rend la liste fusionnée, c'est-à-dire la liste des éléments des deux listes, sachant que chacun ne doit encore apparaître qu'une fois. Par exemple, fusion [5;2;4] [1;3;5] doit donner [1;3;5;2;4] (éventuellement dans un autre ordre).
L'idée est de faire une récurrence : on regarde si la première liste est vide. Dans ce cas, la liste fusionnée est simplement la deuxième. Dans le cas contraire, on enlève le premier élément de la première liste. Puis on regarde s'il est dans la deuxième : si c'est le cas, on le jette. Sinon, on le rajoute à la deuxième et on recommence.
let rec fusion l1 l2 = match l1 with
   |[] -> l2
   |t::q -> if appartient l2 t then fusion q l2 else fusion q (t::l2);;

4) Ecrivez une fonction enlève qui prend une liste et un élément de cette liste (on suppose qu'il appartient bien à la liste) et qui enlève cet élément de la liste (on suppose qu'il n'est qu'une fois dans la liste). Par exemple, enleve [5;2;4] 2 doit donner [5;4] (éventuellement dans un autre ordre).
Solution

> Haut de la page