在OCaml中的配对列表中查找重复项

Question

出于教学目的，我正在尝试在OCaml中实现一种字典作为数据结构。创建新字典时，我可以传递一个对对[(key:value);...]的列表以初始化字典，但是在将它们插入字典之前，我应该检查（列表中的）每个键是否唯一。我怎样才能做到这一点？

这是我所做的：

| Dict(initList) ->
    let rec evaluateList (initList : (ide * exp) list) (env : evT env) : (ide * evT) list =
        match initList with
            | [] -> []
            | (key, value)::t -> (key, eval value env)::(evaluateList t env)
    in DictValue(evaluateList initList env)

DictValue是字典的可重复类型。

输入示例：

let myDict = Dict([
    ("apple",   Eint(430));
    ("banana", Eint(312));
]);; (* Ok *)

let myDictWrong = Dict([
    ("apple", Eint(12));
    ("apple", Eint(13))
]);; (* Wrong *)

编辑：所以，这种情况是我正在写一种解释器，它具有eval之类的功能

let rec eval (e : exp) (environment : evT env) : evT = match e with
    | ...
    .
    .
    | Dict(initList) ->
    let rec evaluateList (initList : (ide * exp) list) (env : evT env) : (ide * evT) list =
        match initList with
            | [] -> []
 (*here*)   | (key, value)::t -> (key, eval value env)::(evaluateList t env)
    in DictValue(evaluateList initList env)

如评论中所述，我也许可以直接在我正在创建的字典中（here）中检查键，但是我不知道该如何实现。

Answer 1

在将它们插入字典之前，我应该检查（列表中的）每个键是否唯一。我怎样才能做到这一点？

具有非常简单的辅助功能？

您的“键是唯一的”可以用另一种方式表示：添加列表时，列表中不存在键X。对？

所以，如何检查密钥是否已经存在？如果键等于列表的head元素中的键，或者存在于列表的尾部，则该键存在。您看到这种递归模式了吗？因此，该实现实际上按照以下说明进行：

let rec is_member key = function
  | [] -> false
  | (k, _)::tail ->
    if k = key then true
    else is_member key tail
;;

is_member "foo" [("foo", 1); ("bar", 2); ("baz", 3)];;
- : bool = true

is_member "foo" [("not-a-foo", 1); ("bar", 2); ("baz", 3)];;
- : bool = false