Donnez le type de ces fonctions.

let est_croissante_entre_zero_et_un f =
  f 0 < f 1

let addition = fun x y -> x + y

(* Indice : en plus d’être d’ordre supérieur, cette fonction est polymorphe *)
let point_fixe f x = (f x) = x

On va maintenant créer des fonctions d’ordre supérieur pour manipuler des listes. On définit donc un type liste polymorphe de cette façon :

type 'a liste =
  | Fin
  | Element of 'a * liste

Écrivez les fonctions suivantes :

• Une fonction associer qui prend une fonction f et une liste l en paramètre, et qui donne la liste [ f l[0] ; f l[1] ; … ; f l[n] ] ;
• Une fonction filtrer qui prend une fonction et une liste, et qui ne garde que les éléments de la liste pour lesquels la fonction a renvoyé true ;
• Une fonction existe qui prend, encore une fois, une fonction booléenne f, et une liste, et renvoie true si un élément de la liste satisfait la condition exprimée par f.

let rec associer (f : 'a  -> 'b) (l : 'a liste) : 'b liste =
  match l with
  | Fin -> Fin
  | Element(x, suite) -> Element(f x, associer f suite)

let rec filtrer (f : 'a -> bool) (l : 'a liste) : 'a liste =
  match l with
  | Fin -> Fin
  | Element(x, suite) ->
    if f x then
      Element(x, filtrer f suite)
    else
      filtrer f suite

let rec existe (f : 'a -> bool) (l : 'a liste) : bool =
  match l with
  | Fin -> false
  | Element(x, suite) -> (f x) || (existe f suite)