Ocaml - parameter type when checking for duplicates in a list

Question

I've got a basic function which checks a list for duplicates and returns true if they are found, false otherwise.

    # let rec check_dup l = match l with
        [] -> false
      | (h::t) ->
        let x = (List.filter h t) in
        if (x == []) then
           check_dup t
        else
           true
    ;;

Yet when I try to use this code I get the error

    Characters 92-93:
          let x = (List.filter h t) in
                                 ^
    Error: This expression has type ('a -> bool) list
           but an expression was expected of type 'a list

I don't really understand why this is happening, where is the a->bool list type coming from?

Answer 1

The type ('a -> bool) list is coming from the type of filter and from the pattern match h::t in combination. You're asking to use a single element of the list, h, as a predicate to be applied to every element of the list t. The ML type system cannot express this situation. filter expects two arguments, one of some type 'a -> bool where 'a is unknown, and a second argument of type 'a list, where 'a is the same unknown type as in the first argument. So h must have type 'a -> bool and t must have type 'a list.

But you have also written h::t, which means that there is another unknown type 'b such that h has type 'b and t has type 'b list. Put this together and you get this set of equations:

'a -> bool == 'b
'a list == 'b list

The type checker looks at this and decides maybe 'a == 'b, yielding the simpler problem

'a -> bool == 'a

and it can't find any solution, so it bleats.

Neither the simpler form nor the original equation has a solution.

---

You are probably looking for List.filter (fun x -> x = h) t, and you would probably be even better off using List.exists.