union-find: Efficient union and equivalence testing of sets.

[ algorithms, bsd3, data, library ] [ Propose Tags ] [ Report a vulnerability ]

The Union/Find algorithm implements these operations in (effectively) constant-time:

  1. Check whether two elements are in the same equivalence class.

  2. Create a union of two equivalence classes.

  3. Look up the descriptor of the equivalence class.


[Skip to Readme]

Downloads

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1, 0.2
Dependencies base (>=4.4 && <4.17), containers (>=0.3), transformers (>=0.2) [details]
License BSD-3-Clause
Author Thomas Schilling <nominolo@googlemail.com>
Maintainer Thomas Schilling <nominolo@googlemail.com>
Revised Revision 2 made by AndreasAbel at 2022-12-27T08:55:48Z
Category Algorithms, Data
Home page http://github.com/nominolo/union-find
Bug tracker http://github.com/nominolo/union-find/issues
Source repo head: git clone git://github.com/nominolo/union-find
Uploaded by ThomasSchilling at 2012-06-23T01:01:23Z
Distributions Fedora:0.2
Reverse Dependencies 4 direct, 11 indirect [details]
Downloads 15464 total (32 in the last 30 days)
Rating 2.0 (votes: 1) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]

Readme for union-find-0.2

[back to package description]

union-find

A simple Haskell library that implements Tarjan's Union/Find algorithm. Useful, for example, to implement unification in a type inference system.

The Union/Find algorithm implements these operations in (effectively) constant-time:

  1. Check whether two elements are in the same equivalence class.

  2. Create a union of two equivalence classes.

  3. Look up the descriptor of the equivalence class.

Installation

Using cabal (which comes with the Haskell Platform):

$ cabal install union-find

or in the checked-out repository:

$ cabal install