union-find

Efficient union and equivalence testing of sets.

http://github.com/nominolo/union-find

Version on this page:0.2@rev:1
LTS Haskell 20.26:0.2@rev:2
Stackage Nightly 2022-11-17:0.2@rev:1
Latest on Hackage:0.2@rev:2

See all snapshots union-find appears in

BSD-3-Clause licensed and maintained by Thomas Schilling
This version can be pinned in stack with:union-find-0.2@sha256:22e97cd9aeb8c96bf7cd8d359d4eda635dc0e0a6cd91b9a07e5a203b00949c8d,1232

Module documentation for 0.2

  • Control
    • Control.Monad
      • Control.Monad.Trans
        • Control.Monad.Trans.UnionFind
  • Data
    • Data.UnionFind
      • Data.UnionFind.IO
      • Data.UnionFind.IntMap
      • Data.UnionFind.ST

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