Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

return the nth element of a list in OCaml?

I am new to Ocaml, just want to make sure how to perform a simple function such as return the nth element of a list by using recursive function?

Prototype like get_nth (list, n) with int list * int -> int

for example get_nth ([1,2,3], 1) -> 2

Thank you

like image 902
Allan Jiang Avatar asked Mar 20 '12 21:03

Allan Jiang


3 Answers

You may not notice but List.nth function is already there in List module.

If you want to write it using recursion:

let rec get_nth = function
    | [], _ -> raise (Failure "get_nth")
    | _, n when n < 0 -> raise (Invalid_argument "get_nth")
    | x::_, 0 -> x
    | x::xs, n -> get_nth(xs, n-1)
like image 177
pad Avatar answered Dec 27 '22 23:12

pad


Using tuples as parameters like this is not common in OCaml. Usually you would use currying and define your function like this:

let get_nth list n = ...

This would have the signature 'a list -> int -> 'a. Also note that you have a 'a paramter here, which means, there is no real reason to restrict your function to ints alone.

Now let's look at the problem. If you want to get the zeroth element, what would your function look like?

let get_nth list 0 = List.head list (* this is not actually valid in OCaml *)

now if you have a function to get the nth element from a list of m items (N.B. n > m), how could you use that function to build another function which get's the n+1st element from a list of m+1 elements? Let that function for n+1 elements be get_nth'

let get_nth' list n' = get_nth (List.tail list) (n'-1)

Now all you need to do is to combine the two and you are done. I'll leave that last part up to you.

If you follow this advice you will get something which is more complicated, than it has to be. However it is easier to understand what is happening this way.

like image 27
LiKao Avatar answered Dec 28 '22 01:12

LiKao


(In my opinion) A simpler solution without using a tuple can be:

let rec get_nth mylist index = match mylist with
    | [] -> raise (Failure "empty list")
    | first::rest -> 
        if index = 0 then first 
        else get_nth rest (index-1)
;;
like image 29
Omar Avatar answered Dec 28 '22 01:12

Omar