ocaml recurssion iteration- find last occurence of element in a list

Question

Assuming l is a List and elem is an element, how can I return the last occurence of the element elem in the list l? Also return -1 if the element does not exisit in l. I dont quite understand how to use recursion for iterating through the list...

let rec getLastOccurence l elem =

;;

Answer 1

This is a tail recursive algorithm for finding an integer in a list:

let find_index elt lst =
  (* Wrap inner function that accepts an accumulator to keep the interface clean *)
  let rec find_it elt acc = function
    | hd :: tl when elt = hd -> acc (* match *)
    | hd :: tl -> find_it elt (acc + 1) tl (* non-match *)
    | _ -> raise Not_found (* end of list *)
  in find_it elt 0 lst (* call inner function with accumulator starting at 0 *)
;;

Answer 2

let findi x l = 
  let rec loop i n l = 
    match l with 
    | y::tl -> loop (i+1) (if y = x then i else n) tl 
    | [] -> n 
  in 
  loop 0 (-1) l;;

Answer 3

Basically, you need two accumulators to keep track of the current index and the maximum index found for the element. Then you just recurse to the end of the list and return the "maximum index" value.

let rindex elem = 
  let rec find_index i max_found = function
    | (x::xs) when x = elem -> find_index (i+1) i xs
    | (_::xs) -> find_index (i+1) max_found xs
    | [] -> max_found
  in find_index 0 (-1);;

This can also be expressed pretty simply as a fold:

let rindex elem ls = 
  let find_index (i, max) elem' = (i+1, if elem' = elem then i else max)
  in snd (fold_left find_index (0, -1) ls);;