1. define the function map f l that applies the function f to each element of the list l

map : ('a -> 'b) -> 'a list -> 'b list

2. Define the function shuffle x l that inserts the element x at each position inside the list l. For instance, shuffle 1 [2;3] evaluates to [ [1;2;3]; [2;1;3]; [2;3;1] ]

shuffle : 'a -> 'a list -> 'a list list

3. define the function flatten l that transforms a list of lists of elements of type T into a list of elements of type T. For instance, flatten [ [1;2]; [3;4;5] ] evaluates to [1;2;3;4;5].

flatten : 'a list list -> 'a list

4. Define the function perm l that evaluates to the list of all the permutations of the elements of the list l. For instance, perm [1;2;3] evaluates to [ [1; 2; 3]; [2; 1; 3]; [2; 3; 1]; [1; 3; 2]; [3; 1; 2]; [3; 2; 1] ].

perm : 'a list -> 'a list list

let rec map f l = match l with
  [] -> []
| x::xl -> f(x) :: map f xl;;
 
let rec shuffle y l = match l with
  [] -> [[y]]
| x::xl -> (y::x::xl) :: (map (fun l -> x::l) (shuffle y xl));;
 
let rec flatten ll = match ll with
  [] -> []
| x::xll -> x @ (flatten xll);;
 
let rec perm l = match l with
  [] -> [[]]
| x::xl -> flatten (map (shuffle x) (perm xl));;