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->布尔列表类型是从哪里来的？

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。

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 

#