Data structures for unique and ordered elements

Help
#1

When looking at some data structures available. I saw Data.Array with sort and cons which seems to be ordered. And i saw Data.Set which i guess has only unique elements and unordered API. If i make a matrix with these two properties and put some packages in them i get

Unordered Ordered
Not unique ?? Data.Array
Unique Data.Set, Data.HashSet ??

Are there any data structures that fill in the ??. In particular i’m looking for a solution to have unique and ordered API (bottom right).

#2

Can you expand on what you mean by an ordered/unordered API?

#3

I suppose a non-unique version of a set would be a “bag” or “multiset”, ie a set where you can also count the number of occurrences of each element. I’d recommend representing that as a Map a Int (or also HashMap) where insertion could be defined as alter (Just <<< maybe 0 (_+1)).

#4

i mean with ordered API that you can do operations like sort and cons. By the way look at haskell package Data.Set.Ordered and Data.Set (unordered).

Data.Set.Ordered

An OSet behaves much like a Set , with mostly the same asymptotics, but also remembers the order that values were inserted.

#5

Ah right, I see. No, I’m not aware of a data structure like Haskell’s Data.Set.Ordered.

#6

Could i make it just by wrapping the Array module with a new type and calling nub on every function? Or is that not a good idea?

#7

That’s probably not a bad idea, especially if it’s unlikely to contain more than, say, a thousand elements. There are some operations which will be slower than they would be with a more purpose-built approach. For example cons would be O(n) with the nubbed array approach, whereas you’d probably expect O(log n) for Data.Set.Ordered.

1 Like