OCaml function to check if list is palindrome with floor(n/2) recursive calls and no list allocation

Question

I have this task on uni, I have researched for a long time, but I cannot find out, how to write this function. I need it to check if a list is a palindrome, call itself recursively at most floor(n/2) times and not allocate any auxiliary list (so I can use no list constructors). Any ideas? Tbh, I would like an algorithm than a full solution.

Answer 1

I have come up with this and it works:

let palindrom l =
let rec aux l0 l1 =
    match (l0, l1) with
    | _,[] -> (true,[])
    | hd :: tl, [x] -> (hd = x, tl)
    | _, hd1 :: tl1 -> let (pal, ll) = aux l0 tl1 in
          match ll with
          | [] -> (pal, [])
          | hd::tl -> (pal && hd1 = hd, tl) in
match l with
[] -> true
| _ -> fst (aux l l)