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

[ algorithms, bsd3, data, library ] [ Propose Tags ]

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]
Versions 0.1, 0.2
Dependencies base (>=4.4 && <5), 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 1 made by phadej at Sat May 28 14:02:41 UTC 2016
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 Sat Jun 23 01:01:23 UTC 2012
Distributions Fedora:0.2, LTSHaskell:0.2, NixOS:0.2, Stackage:0.2
Downloads 12610 total (38 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]
Hackage Matrix CI

Modules

[Index]

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

For package maintainers and hackage trustees


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