This expression has type 'a list but an expression was expected of type 'a

Question

I have a function in OCaml which should merge two lists:

let rec merge (list1, list2) = 
    match (list1, list2) with
        ([], []) -> merge (List.tl list1, List.tl list2) :: List.hd list1 :: List.hd list2
        |(_, []) -> merge (List.tl list1, list2) :: List.hd list1
        |([], _) -> merge (list1, List.tl list2) :: List.hd list2;;

but for some reason the compiler doesn't let this code through exitting with:

Error: This expression has type 'a list but an expression was expected of type 'a The type variable 'a occurs inside 'a list

How can I specify that these are lists of 'a I'm trying pass, not 'a?

Lhooq Lhooq · Accepted Answer · 2017-10-19T08:16:52

First of all, this function won't work. If the two lists are empty you merge the tail and concatenate the head of each of them but...well...they are empty...

Anyway, your problem is that you're using the :: operator (concatenation) whose type is 'a -> 'a list -> 'a list so the left member should be an element and the right one a list, here the left one is the list and the right one the element so it can not work.

About your question, since the type is inferred, you can't tell the compiler that you're right and he's wrong, in this case the error was truly explicit :

 List.tl l (* 'a list *) :: List.hd l (* 'a *)

will always return an error because you have an infinite type (since :: is of type 'a -> 'a list -> 'a list, I let you try to determine a finite type 'a that could match with your concatenation)

So, I guess what you want to do is something like this :

let rec merge (list1, list2) = 
    match list1, list2 with
        | [], _ -> list2;;
        | hd :: tl, _ -> hd :: merge tl list2

This expression has type 'a list but an expression was expected of type 'a

1 Answers