C'est peu dire que c'est un grand classique. C'est l'intersection d'ensembles (avec répétitions, ce qui ne change rien) représentés par des listes triées.
let rec communs xs ys = match xs,ys with | [],_ -> [] | _,[] -> [] | x::rx, y::ry -> if x < y then communs rx ys else if y < x then communs xs ry else (* x=y *) x::communs rx ry ;;
On notera l'utilisation de l'idiome match xs,ys with… afin de décomposer les deux listes à la fois. On aurait aussi très bien pu écrire :
let rec communs xs ys = match xs with | [] -> [] | x::rx -> match ys with | [] -> [] | y::ry -> …
Mais c'est tellement moins beau.