Keeping a counter for every recursive call in OCaml

Question

I am trying to write a function that returns the index of the passed value v to a given list x ; -1 if not found. My attempt at a solution:

 let rec index (x, v) = let i = 0 in match x with [] -> -1 | (curr::rest) -> if(curr == v) then i else succ i; (* i++ *) index(rest, v) ;; 

This is obviously wrong for me (it will return -1 every time), because it overrides i on each pass. I have some obscure ways to do this with individual functions in my head, none of which I can write at the moment. I know this is a common template in all programs, so my question is: what is the best way to do this in OCaml?

Answer 1

You cannot mutate variables in OCaml (well, there is a way, but you really shouldn't do simple things like this)

The main trick you can do is to create a helper function that receives additional arguments corresponding to the variables you want to mutate. Notice how I added an additional parameter for i , as well as "mutate" the current head of the list in a similar way.

 let rec index_helper (x, vs, i) = match vs with [] -> -1 | (curr::rest) -> if(curr == x) then i else index_helper (x, rest, i+1) ;; let index (x, vs) = index_helper (x, vs, 0) ;; 

Such a recursive tail conversion is a way of translating loops into functional programming, but to be honest, it's kind of low level (you have full power, but manual recursion looks like programming with gotos ...).

For some specific patterns that you can try to make, you need to use reusable functions of a higher order, such as a map or folds.

Answer 2

Mutation is not a common way to solve problems in OCaml. For this task, you must use recursion and accumulate results by changing the index i under certain conditions:

 let index(x, v) = let rec loop xi = match x with | [] -> -1 | h::t when h = v -> i | _::t -> loop t (i+1) in loop x 0 

Another thing is that using -1 as an exceptional case is not a good idea. You can forget this assumption somewhere and treat it like other indices. In OCaml, it is best to handle this exception using the option type, so that the compiler forces you to take care of None every time:

 let index(x, v) = let rec loop xi = match x with | [] -> None | h::t when h = v -> Some i | _::t -> loop t (i+1) in loop x 0 

Answer 3

This is a pretty clear homework problem, so I’ll just make two comments.

First, values ​​like i are immutable in OCaml. Their values ​​do not change. Therefore, succ i does not do what your comment says. It does not change the value of i . It simply returns a value greater than i . This is equivalent to i + 1 , not i++ .

Secondly, the essence of recursion is to imagine how to solve a problem, if you already have a function that solves the problem! The only trick is that you are allowed to pass this other function to a smaller version of the problem. In your case, the smaller version of the problem is the one where the list is shorter.