When looking at some data structures available. I saw
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
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 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)).
i mean with ordered API that you can do operations like
cons. By the way look at haskell package
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 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.