Skip to content

union find in haskell, based on ST Monad, made it easy to use

License

Notifications You must be signed in to change notification settings

overshiki/easy-union-find

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

3 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

introduction:

A haskell implementation of union-find data structure based on ST Monad.

It mainly follows this union-find repository. More specifically, the src/Data/UnionFind/ST.hs file in it.

However, I do have some modifications:

  1. the Root a constructor in Chain s a datatype does not depend on s state, while in union-find repository, the related data type Link s a has constructor Info {-# UNPACK #-} !(STRef s (Info a)) where STRef s is actually not necessary.
  2. I create StEq typelcass with eq function to handle the equality check (== symbol) of Point and Chain datatype, this is because they are always in an ST s monad and the normal (==) function does not fit in this type signature. In union-find repository, such a treatment does not exist, and it has resulted in a weird bug(as I believe).

to test:

run cabal test

It will run test/Main.hs for testing

About

union find in haskell, based on ST Monad, made it easy to use

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published