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).
Can you expand on what you mean by an ordered/unordered API?
I suppose a nonunique 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))
.
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.
Ah right, I see. No, I’m not aware of a data structure like Haskell’s Data.Set.Ordered.
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?
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 purposebuilt 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