Super new to Ocaml. How do I access the "nth" value of a list without using the List module?

Learning
1

Hi! I’m learning OCaml, and right now the syntax is super confusing to me. For example, if I had a list x = [1;2;3;4;5] and i wanted to access the 3rd element, 3, at index two obviously, how would I go about that?

2

OCaml “lists” are inductively defined linked lists. A list is either empty ([]) or an element followed by a list (elem::list).

You can think of the linked list definition as

type 'a list =
  | []
  | (::) of 'a * 'a list

To process a list, you have to use pattern matching and usually recursion as well:

match list with
| [] -> (* handle empty case *)
| x::xs -> (* handle non-empty case *)

Here, x is a newly defined variable bound to the element and xs is a new variable set to the “tail” of the list.

You cannot have O(1) indexing of linked lists. You must linearly traverse them. However, OCaml does have arrays, which are fixed-size containers with O(1) indexing. Arrays are written [|1; 2; 3|] and accessed with array.(index).

1 Like
3

Thanks for the response!
I’m a little confused, for example if I wanted to get to the third element of a list specifically, how would I use the head and tail and the “::”, do I just call the “::” twice to shift it over twice?

4

To get the third element, you would pattern match

match list with
| _::_::third::_ -> (* do stuff *)
| _ -> (* handle the case in which the above pattern match failed *)

(_ is a wildcard pattern, which matches anything.)

However, to get the element at some arbitrary index, you will have to use recursion.

1 Like
5

Thanks! Appreciate the help

6

There is also a convenience function in the list module:

val nth : 'a list -> int -> 'a.

It will raise exceptions though if you ask for an element outside the range of the list.

1 Like
7

So make a test first with List.length to avoid exception triggering.

8

Or call nth and handle the exception, they’re cheap in OCaml :slight_smile:

9

Do you know the cost of handling an exception, and of testing the pre-condition in this case?
Thanks

10

I don’t know the costs relative to each other, but I am saying that in general exceptions are not going to be a performance problem in OCaml, based on … f# - OCaml performance of exceptions - Stack Overflow

Some excerpts from there:

OCaml exception handling make raising and catching exceptions extremely fast … In OCaml, exceptions don’t cause performance problems. … Due to their convenience, OCaml exceptions are also often used as a pure control-flow mechanism (and not to signal a rare failure condition).

Anyway, my point is just that just allowing and handling an exception in OCaml is not something to worry about performance-wise.

1 Like
11

One downside to this, for longer lists, is that List.length traverses the entire list to find its length. If this is done frequently for longer lists it can be very expensive.

1 Like
12

I’m really interested in such metrics.

List.nth should be of complexity O(n).
Is the cost of List.length O(1) or O(n) ?

Thanks to advanced Ocamlers for their answer.

EDIT
It should be O(n) if I understand correctly ocaml/stdlib/list.ml :

let rec length_aux len = function
    [] -> len
  | _::l -> length_aux (len + 1) l

let length l = length_aux 0 l

So, what is the cost of handling exception (and of using Options types)?

1 Like
13

Checking the length and then taking the nth value is, roughly speaking, traversing the list twice. Just taking the value and handling the exception traverses it once only. So for a larger list the latter should be more performant.

14 
let rec nth n l =
if n>List.length l then failwith "erreur" 
else
match n,l with
	|_,[]->failwith "erreur"
	|0,p::q->p
	|n,p::q->nth (n-1) q

;;

1 Like
15

If the aim is just to avoid the exception, there is List.nth_opt in OCaml ≥4.05.

1 Like