A list with no duplicates or an ordered set

Question

Is there a library which provides a data structure, which preserves the order of items and does not contain any duplicates? And does there exist a proper name for such a data structure?

I expect it to behave like a list with nub applied after each operation on it. Of course I don't expect it to be implemented as ineffectively.

Answer 1

Here's one solution:

Use a fingertree with the Set monoid as your measure. Then on inserts, check membership first, using the measure of your full fingertree. This gives you O(log(n)) cons and snoc, O(1) deletes.

Here's another solution:

Pair a normal list with a normal Set and get basically the same effect. You get better constant factors, but O(log(n)) deletes.

Here's a question: What do you want to happen on insert of a duplicate? Should the existing position be preserved? The new position? Priority Queues may be close to what you want, depending.