OCaml assertion fail

Question

Hey everyone I'm new to OCaml and having some problems. So I'm trying to do a recursive function that takes a non-empty list and returns the last element. My list can be any data type though. Here is what I have right now and it's currently failing on the assertion statement saying "This expression has type int but an expression was expected of type int list.

let rec last l = match l with

[] -> []

|[x] -> [x]

|_::t -> last t ;;

assert(last [1; 2; 3; 4] = 4);;

assert(last ["a"; "b"; "c"; "d"] = "d");;

Answer 1

I often find that a good way to deal with this kind of type errors, is to explicitly annotate the function with the type I want it to have - in this case, I expect that you want the first line to be something like this:

let rec last: 'a list -> 'a = fun l -> match l with

With that, the error changes to:

File "1/hest.ml", line 5, characters 9-10:
5 | |[x] -> [x]
             ^
Error: This expression has type 'a list
       but an expression was expected of type 'a
       The type variable 'a occurs inside 'a list

Which is a more helpful error. The problem is, as @PatJ writes in his answer, that as you have written the function you actually return a list with one element (or no elements, when the list is empty), but your usage of the function seems to indicate that you just want the last element.

You can either:

1. change your usage of the function, so the asserts compare with [4] and ["d"] instead of just the values.
2. change the function to return Some x and None instead of [x] and [], and change the asserts to assert against Some 1 and Some "d".
3. change the function to return x instead of [x] and throw an exception in the empty list case - that would be: failwith "empty list"

I think the second solution is the most natural one.

If you go for exceptions, then renaming the function to last_exn would convey to users that they have to beware that the function might throw.

Answer 2

The problem comes from the fact that your function is indeed returning a list, as can be seen in those two lines:

[] -> []

|[x] -> [x]

You want the second line to be |[x] -> x. Of course, you also need to handle the case of an empty list and effectively return something. You can either have it raise an exception, use an option type or have the caller specify a default value.

Answer 3

In this kind of cases, it's better to use an option type:

let rec last_opt l =
  match l with
  | [] -> None
  | [x] -> Some x
  | _x::t -> last_opt t

let () =
 assert (last_opt [1; 2; 3; 4] = Some 4);
 assert (last_opt ["a"; "b"; "c"; "d"] = Some "d"); (* Note that here you could use chars, i.e. 'a', 'b' etc. instead of strings "a", "b" etc. *)
 assert (last_opt [] = None)

If you really don't want an option type, you should handle the empty case with care :

let rec last l =
  match l with
  | [] -> raise (Failure "last")
  | [x] -> x
  | _x::t -> last t