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
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.