Replace tuples in a list

So I have a tuple list as follows:

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

How can I create a function that can remove the duplicate, but replace the first occurrence with the value of the first duplicate?

I.e. the list above would become:

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

and if I had the list:

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

This would become:

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

EDIT: I have created this function which removes the duplicates, but does not replace the values:

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

Solution

Your description doesn't quite mesh with your second example. You said that you wanted to replace the value with the first duplicate but in your second example you replaced (3,"l") with the last duplicate ((3,"f") rather than (3,"x")). Both can be done, though replacing by the last duplicate is significantly easier.

To replace by the last duplicate, view the final list as being obtained by updating an unambiguous list of key-value pairs. Write a function which does this update, and then run this update function on the list, starting with the empty list:

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 [];

This function works as expected for your two examples.

For completeness, here is an approach in which it is the first duplicated value which is ultimately retained. To do this, add a Boolean flag which will tell you if the value has been updated. The first time you update -- set the flag. Strip away the flags in the final result:

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;

When this is run against your second example:

- 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

The first value of the first duplicate key "x" is retained rather than value for the second duplicate key.

For any serious work involving keys and values you should consider using a different data structure such as SML/NJ's hash table . The code I gave above is frightfully inefficient with the final result a data structure with O(n) lookup.