Take the 2-minute tour ×

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.

share|improve this question
It reminds me of Java's LinkedHashSet. So I suppose a similar approach could be used for an immutable functional data structure. –  Petr Pudlák Jul 8 '13 at 11:02
If your type belongs to Ord, you could use a Data.Set to write and ordNub that takes O(n*log m), where n is the number of items, and m the number of unique items. If Hashable and not Ord, you could do the same with Data.HashSet. Would that be sufficiently un-inefficient? –  Daniel Fischer Jul 8 '13 at 12:16
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer


