Отфильтровать список пар по ключу в OCaml

Question

У меня есть список пар, которые имитируют словарь, например [("key1",32);("key2",54);...], и мне нужна функция, которая может фильтровать список и возвращать новый список, удалять пары, которые имеют дубликаты ключей.

Пример: список типа [("key",32);("key",78);("anotherKey",12)] должен быть отфильтрован как [("key",32);("anotherKey",12)].

. Я добился этого с помощью Hashtable, но я предпочитаю решение, использующее вместо этого List. В приведенном ниже коде я не могу найти способ заменить хеш-таблицу списком, потому что в ветке else я не знаю, как правильно обновить список seen.

let getKey (k,v) = k;;

(* Hashtable *)
let filter (list : (string * int list) : (string * int) list =
    let seen = Hashtbl.create (List.length list) in
        List.filter ( fun pair -> let exists = not (Hashtbl.mem seen (getKey pair)) in
            Hashtbl.replace seen (getKey pair) (); exists) list
;;

(* List *)
let filter (list : (string * int) list) : (string * int) list = 
    let seen = [] in
        List.filter ( fun pair -> let exists =  List.mem (getKey pair) seen in 
            if exists then failwith("duplicate")
            else (* what to do here? *) ; true) list
;;

Answer 1

Не уверен, что понимаю, в чем проблема. Как по мне, решение может быть выражено довольно четко:

1. Возьмите элемент заголовка списка для дедупликации.
2. Если он не является членом списка результатов, добавьте элемент head к списку результатов
3. Если он уже является членом - пропустите его
4. Дублируйте (повторите 1-3) хвост

Реализация просто следует description:

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

let dedup list =
  let rec aux acc = function
    | [] -> List.rev acc
    | ((k, v) as hd)::tl ->
      if is_member k acc then aux acc tl
      else aux (hd::acc) tl
  in aux [] list
;;

utop # dedup [("key",32);("key",78);("anotherKey",12)];;
- : (string * int) list = [("key", 32); ("anotherKey", 12)]

Что касается стандартной библиотеки (и List в частности), вы не можете достичь своей цели, используя List.filter - потому что эта функция не накапливает результат, а просто перебирает элементы списка один за другим. Если вам нужен накопленный результат, вы должны использовать что-то. например, вместо fold_left, например:

let dedup_list list =
  List.fold_left (fun acc ((k, v) as el) -> if is_member k acc then acc else el::acc) [] list
  |> List.rev
;;

utop # dedup_list [("key",32);("key",78);("anotherKey",12)];;
- : (string * int) list = [("key", 32); ("anotherKey", 12)]