[Haskell-cafe] Collection of sets containing no sets which are a subset of another in the collection

Gwern Branwen gwern0 at gmail.com
Sat Nov 14 09:13:48 EST 2009

On Sat, Nov 14, 2009 at 4:35 AM, Max Rabkin <max.rabkin at gmail.com> wrote:
> On Sat, Nov 14, 2009 at 9:21 AM, Mark Wassell <mwassell at bigpond.net.au> wrote:
>> Hi,
>> I am looking for a data structure that will represent a collection of sets
>> such that no element in the collection is a subset of another set. In other
>> words, inserting an element that is already a subset of another element will
>> return the original collection, and inserting an element that is a superset
>> of any elements will result in a collection with the superset added and the
>> subsets removed.
> I *think* what you're describing is a Union-Find structure. A
> functional union-find structure is described in
> http://www.lri.fr/~filliatr/ftp/publis/puf-wml07.ps (the language used
> is OCaml, but if you have any difficulty translating it to Haskell I'm
> sure this list will offer its help).
> --Max

http://hackage.haskell.org/package/union-find ?


More information about the Haskell-Cafe mailing list