List.assoc 使用 List.find

Question

我想用List.find实现List.assoc功能，这是我试过的：

let rec assoc lista x = match lista with
  | [] -> raise Not_found
  | (a,b)::l -> try (List.find (fun x -> a = x) lista)
            b
        with Not_found -> assoc l x;;

但它给了我这个错误：

此表达式的类型为 ('a * 'b) list 但表达式应为 'a list 类型类型变量 'a 出现在 'a * 'b

中

我不知道这是否是预期会发生的事情，或者我是否做错了什么。我也试过这个作为替代方案：

let assoc lista x = match lista with
    | [] -> raise Not_found
    | (a,b)::l -> match List.split lista with 
        | (l1,l2) -> let ind = find l1 (List.find (fun s -> compare a x = 0))
        in List.nth l2 ind;;

其中 find 是一个函数 returns 所请求元素的索引：

let rec find lst x =
    match lst with
    | [] -> raise Not_found
    | h :: t -> if x = h then 0 else 1 + find t x;;

对于这段代码，问题是函数的类型应该是 ('a * 'b) list -> 'a -> 'b，但它是 (('a list -> 'a) * 'b) list -> ('a list -> 'a) -> 'b, 所以当我尝试

assoc [(1,a);(2,b);(3,c)] 2;;

我得到：

此表达式的类型为 int，但表达式应为类型 'a 列表 -> 'a（指列表中对的第一个元素）

我不明白为什么我没有得到预期的函数类型。

Answer 1

首先，关于使您的 assoc 函数更符合 OCaml 的习惯的快速建议：让它将列表作为最后一个参数。

其次，您为什么要尝试在查找方面实现这一点？没有它更容易。

let rec assoc x lista =
  match lista with
  | [] -> raise Not_found
  | (a, b) :: xs -> if a = x then b else assoc x xs

OCaml 中列表的工作方式更简单，效率也更高。

将列表作为最后一个参数，甚至意味着我们可以更简洁地编写它。

let rec assoc x =
  function
  | [] -> raise Not_found
  | (a, b) :: xs -> if a = x then b else assoc x xs

关于您的问题，OCaml 会根据函数的使用方式推断出函数的类型。

find l1 (List.find (fun s -> compare a x = 0))

我们知道 l1 是一个 int 列表。所以我们必须试图在一个 int list 列表中找到它。所以：

List.find (fun s -> compare a x = 0)

必须 return 一个 int list 列表。一团糟。尝试重新考虑您的函数，您最终会得到更容易推理的东西。

List.assoc 使用 List.find

List.assoc using List.find

ocaml

list

find