CODEWITHSUNDEEP
listrecursiontypesduplicatesocaml
Rowhawn
Rowhawn

Reputation: 1479

Ocaml - parameter type when checking for duplicates in a list

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?

Upvotes: 5

Views: 2182

Answers (2)

daniele3004
daniele3004

Reputation: 13930

For complete this answer I post the final function for search duplicate value in array:

let lstOne = [1;5;4;3;10;9;5;5;4];;

let lstTwo = [1;5;4;3;10];;

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

and when the function run:

# check_dup lstOne

- : bool = true

# check_dup lstTwo

- : bool = false

#

Upvotes: 0

Norman Ramsey
Norman Ramsey

Reputation: 202535

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.

Upvotes: 8

Related Questions