Ocaml - 在检查列表中的重复项时参数类型

Question

我有一个基本的函数，它检查列表中是否有重复项，如果有则返回true，否则返回false。

    # 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
    ;;

但是当我尝试使用这段代码时，我遇到了错误

    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

我不是很理解为什么会发生这种情况，a->bool列表类型是从哪里来的？

- Rowhawn

Answer 1

类型('a -> bool) list来自于filter函数的类型和模式匹配h::t的组合。您要求使用列表中的单个元素h作为应用于列表t中每个元素的谓词。ML类型系统无法表达这种情况。 filter函数需要两个参数，一个是类型为'a -> bool的某个类型'a的参数，另一个是类型为'a list的第二个参数，其中'a是与第一个参数中的未知类型相同的类型。因此，h必须具有类型'a -> bool，而t必须具有类型'a list。

但是，您还编写了h::t，这意味着存在另一个未知类型'b，使得h具有类型'b，t具有类型'b list。将其放在一起，您将得到以下一组方程：

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

类型检查器会查看这个问题，然后决定可能有'a == 'b，从而得到更简单的问题。

'a -> bool == 'a

它找不到任何解决方案，所以它哀叫。

简化形式和原方程均无解。

---

你可能正在寻找 List.filter (fun x -> x = h) t，使用 List.exists 甚至更好。

- Norman Ramsey

Answer 2

为了完整回答这个问题，我发布了在数组中搜索重复值的最终函数：

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;;

当函数运行时：

# check_dup lstOne

- : bool = true

# check_dup lstTwo

- : bool = false

# 

- daniele3004