Use Ocaml Language.

Write a tail-recursive function split : a list -> a list * a list that takes a list and returns a pair of lists such that for all l, (fst (split l)) @ (snd (split l)) is a permutation of l. That is, it splits a list into two lists and returns a pair of the two lists. The lengths of the two lists should differ by at most one.

For example, split [1;2;3;4;5] can return ([1;2;3], [4;5]) or ([1;3;5], [2; 4]) or ([5;3], [4;2;1] but not ([], [1;2;3;4;5]) or ([1;2;3], [3;4;5]) or ([1], [5]).

The base code:

let split (l: 'a list) : 'a list * 'a list = raise ImplementMe ;;