CODEWITHSUNDEEP
functional-programmingocaml
id2341677
id2341677

Reputation: 319

Keeping a counter at each recursive call in OCaml

I am trying to write a function that returns the index of the passed value v in a given list x; -1 if not found. My attempt at the 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 to me (it will return -1 every time) because it redefines i at each pass. I have some obscure ways of doing it with separate functions in my head, none which I can write down at the moment. I know this is a common pattern in all programming, so my question is, what's the best way to do this in OCaml?

Upvotes: 4

Views: 5409

Answers (3)

hugomg
hugomg

Reputation: 69934

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

A basic trick you can do is create a helper function that receives extra arguments corresponding to the variables you want to "mutate". Note how I added an extra parameter for the i and also "mutate" the current list head 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) ;;

This kind of tail-recursive transformation is a way to translate loops to functional programming but to be honest it is kind of low level (you have full power but the manual recursion looks like programming with gotos...).

For some particular patterns what you can instead try to do is take advantage of reusable higher order functions, such as map or folds.

Upvotes: 3

pad
pad

Reputation: 41290

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

let index(x, v) =
    let rec loop x i =
        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 may forget this assumption somewhere and treat it as other indices. In OCaml, it's better to treat this exception using option type so the compiler forces you to take care of None every time:

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

Upvotes: 7

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66818

This is pretty clearly a homework problem, so I'll just make two comments.

First, values like i are immutable in OCaml. Their values don't change. So succ i doesn't do what your comment says. It doesn't change the value of i. It just returns a value that's one bigger than i. It's equivalent to i + 1, not to i++.

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

Upvotes: 4

Related Questions