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?
OCaml “lists” are inductively defined linked lists. A list is either empty (
) or an element followed by a 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 *)
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
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?
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.
Thanks! Appreciate the help
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.
So make a test first with List.length to avoid exception triggering.
nth and handle the exception, they’re cheap in OCaml
Do you know the cost of handling an exception, and of testing the pre-condition in this case?
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 … https://stackoverflow.com/a/12161946/20371
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.
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.
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.
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)?
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.
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
If the aim is just to avoid the exception, there is
List.nth_opt in OCaml ≥4.05.