Finding an item in a list and returning its index - OCaml

Question

I've wrote the following function to find a given item "x" in a given list "lst" and return its index if it's found, otherwise it would return an error:

exception Failure of string

let rec func x lst c = match lst with
    | [] -> raise(Failure "Not Found")
    | hd::tl -> if (hd=x) then c else func x tl (c+1)


let find x lst = func x lst 0

The function is fully working, I'm just wondering what is the memory consumption of it? Meaning does the memory consumption depend on the length of the list? or is it O(1)?

If it's not O(1) can someone please let me know what should I do to make it so?

Thank you

Answer 1

Your function consumes constant (O(1)) space, because it's tail recursive.

You can read about tail recursion at OCaml.org, here.

Update

Here is a non-tail-recursive solution:

exception Failure of string

let rec find x lst =
    match lst with
    | [] -> raise (Failure "Not Found")
    | h :: t -> if x = h then 0 else 1 + find x t

(I just noticed that PatJ already explained this, sorry :-)

Often the non-tail-recursive solution is more concise and elegant. It's too bad, but that's the way the world is sometimes.