Заменить кортежи в списке

Question

Итак, у меня есть следующий список кортежей:

val mylist = [(1,"h"),(3,"l"),(45,"j"),(3, "x")] : (int * string) list

Как я могу создать функцию, которая может удалить дубликат, но заменить первое вхождение значением первого дубликата?

Т.е. список выше стал бы:

val mylist = [(1,"h"),(3,"x"),(45,"j")] : (int * string) list

и если бы у меня был список:

val mylist = [(1,"h"),(3,"l"),(45,"j"),(3, "x"), (3, "f")] : (int * string) list

Это станет:

val mylist = [(1,"h"),(3,"f"),(45,"j")] : (int * string) list

---

РЕДАКТИРОВАТЬ: я создал эту функцию, которая удаляет дубликаты, но не заменяет значения:

fun removeVarDuplicates [] = []
  | removeVarDuplicates ((v, e)::xs) = (v, e)::removeVarDuplicates(List.filter (fn (y, ys) => y <> v) xs);

Answer 1

Ваше описание не совсем совпадает с вашим вторым примером. Вы сказали, что хотите заменить значение первым дубликатом, но во втором примере вы заменили (3,"l") с последним дубликатом ((3,"f") скорее, чем (3,"x")). И то, и другое можно сделать, хотя замена на последний дубликат значительно проще.

Чтобы заменить последним дубликатом, просмотрите окончательный список как полученный путем обновления однозначного списка пар ключ-значение. Напишите функцию, которая выполняет это обновление, а затем запустите эту функцию обновления в списке, начиная с пустого списка:

fun update (i,c) [] = [(i,c)]
|   update (i,c) ((j,d)::records) = 
        if i = j then
            (i,c)::records
        else
            (j,d) :: (update (i,c) records)

fun updateAll [] records = records
|   updateAll ((i,c)::pairs) records = updateAll pairs (update (i,c) records)

fun removeVarDuplicates pairs = updateAll pairs [];

Эта функция работает как и ожидалось для ваших двух примеров.

Для полноты, вот подход, в котором это первое дублированное значение, которое в конечном итоге сохраняется. Для этого добавьте логический флаг, который сообщит вам, было ли обновлено значение. При первом обновлении - установите флаг. Снимите флажки в конечном результате:

fun update (i,c) [] = [(i,c,false)]
|   update (i,c) ((j,d,t)::triples) = 
        if i = j then
            if t then (j,d,t) :: triples else (j,c,true)::triples
        else
            (j,d,t) :: (update (i,c) triples)

fun updateAll [] triples = triples
|   updateAll ((i,c)::pairs) triples = updateAll pairs (update (i,c) triples)

fun removeVarDuplicates pairs = 
    let
        val triples = updateAll pairs []
    in
        map (fn (x,y,_) => (x,y)) triples
    end;

Когда это работает против вашего второго примера:

- val mylist = [(1,"h"),(3,"l"),(45,"j"),(3, "x"), (3, "f")];
val mylist = [(1,"h"),(3,"l"),(45,"j"),(3,"x"),(3,"f")] : (int * string) list
- removeVarDuplicates mylist;
val it = [(1,"h"),(3,"x"),(45,"j")] : (int * string) list

Первое значение первого дубликата ключа "x" сохраняется, а не значение для второго дубликата ключа.

Для любой серьезной работы, связанной с ключами и значениями, вы должны рассмотреть возможность использования другой структуры данных, такой как хеш-таблица SML/NJ. Код, который я привел выше, ужасно неэффективен, в конечном итоге структура данных с O(n) уважать.