Найти дубликаты в списке пар в OCaml

Question

Я пытаюсь реализовать своего рода словари в качестве структуры данных в OCaml для дидактических целей. При создании нового dict я могу передать список пар [(key:value);...] для инициализации dict, но, прежде чем вставлять их в dict, я должен проверить, является ли каждый ключ (в списке) уникальным. Как мне этого добиться?

Вот что я сделал:

| 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 - это тип представления representable для dict.

Пример ввода:

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)

Как сказано в комментариях, я могу проверьте ключ, в строке ( здесь ), прямо в диктовке, которую я создаю, но я не знаю, как этого добиться.

Answer 1

прежде чем вставлять их в dict, я должен проверить, является ли каждый ключ (в списке) уникальным. Как я могу достичь этого?

С очень простой вспомогательной функцией?

Ваш «ключ уникален» можно выразить по-другому: ключ 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