I've google around and have been unsuccessful in finding a name for a data-structure consisting of a list whose elements are unique.

I've seen "unique sorted lists", but I'm looking into the more general, not necessarily sorted, case.

Does anyone know a name and a source for such things? --e.g., a one word name for them.

Moreover, lists may be construed as initial algebras or the solutions to a family of recursive equations involving constructors, say, nil and cons. What possible equational algebra gives rise to lists without repetitions? That is, do they pop-out as a solution to some family or are they an algebraic data type that has certain equational constraints, if so which ones?

  • 1
    $\begingroup$ This is similar to an ordered dictionary. You might call it an ordered set. $\endgroup$ – Yuval Filmus Jul 31 '18 at 13:51
  • $\begingroup$ As mentioned above, I'm specifically avoiding the particular case of things being ordered. $\endgroup$ – Musa Al-hassy Jul 31 '18 at 15:48
  • 3
    $\begingroup$ In that case, you're interested in the set data structure. $\endgroup$ – Yuval Filmus Jul 31 '18 at 15:50
  • $\begingroup$ An order statistic tree is a tree that supports efficient select and rank queries (log n) which means it is an effcient list implementation. It is implemented on top a of a bst set data structure. $\endgroup$ – Anonymous Jul 31 '18 at 17:02
  • 1
    $\begingroup$ In that case, you're interested in an ordered set. We can continue this back and forth for a few more rounds, but the end result would be either an ordered set or a (regular) set. $\endgroup$ – Yuval Filmus Aug 1 '18 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.