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).
On fait une fonction auxiliaire qui a pour arguments deux listes : la liste (resu) des éléments testés et la liste (li) des éléments à tester. Si le premier élément de li est l'élément à enlever, on rend la liste resu concaténée avec la queue de li. Sinon, on met la tête de li dans resu et on recommence avec la queue de li.
let enleve liste a =
    let rec aux (t::q) resu = if t = a then q@resu else aux q (t::resu)
in aux liste [];;
Remarque : Caml nous avertit que l'on réalise un filtrage non exhaustif. En effet, lorsque l'on écrit « aux (t::q) », on suppose que l'argument de aux s'écrira toujours sous la forme « t::q ». Autrement dit, on suppose qu'on n'appliquera jamais aux à []. Cette supposition est ici justifiée car on a précisé dans l'énoncé que l'élément à enlever était bien dans la liste, qui est donc non vide.

5) Pour finir, une fonction intersection qui prend deux listes et rend la liste des éléments communs aux deux listes.
Solution

> Haut de la page