OCaml expected type 'a

Question

I am attempting to make a function such that it outputs a list that removes adjacent duplicates

let rec rem_adj_duplicates l = 
    let rec utn l n = match l with
        [] -> n
        | (x :: y :: xs) -> if (x != y) then utn (y::xs) (n::x)
            else utn (y::xs) n
    in utn l []

I get the following error:

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

Why does n want to be type 'a instead of 'a list?

Jeffrey Scofield Jeffrey Scofield · Accepted Answer · 2014-02-17T02:14:05

You have this:

if (x != y) then
    utn (y::xs) (n::x)
else
    utn (y::xs) n

In the first call you have n :: x, which says that x is a list and n is a non-list. Furthermore it says that the second argument to utn is a list. In the next call you have just n, which must be of the same type as the other call. Thus, n shows up as both a list and a non-list.

Possibly you wanted to have x :: n rather than n :: x?

Update

You say you're not allowed to use the @ operator. This is actually reasonable, as using it in the way you wanted is not a good way to solve the problem. (Adding things one at a time to the end of a list is slow, i.e., quadratic time in the length of the list.)

I may be giving away too much, but a common way to solve this problem is to build the list in reverse order and reverse it at the end. This takes only linear time.

OCaml expected type 'a

1 Answers