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列表类型来自哪里？

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.