decision-diagrams

Hackage:

Dev:

Binary Decision Diagrams (BDD) and Zero-suppressed Binary Decision Diagrams (ZDD) implementation in Haskell.

BDD is a data stucture suitable for representing boolean functions (can be thought as a compressed representation of truth tables) and many operations on boolean functions can be performed efficiently. ZDD is a variant of BDD suitable for representing (sparse) families of sets compactly.

BDD/ZDD uses hash-consing for compact representation and efficient comparison, and we use intern package for implementing hash-consing.

Comparison with other BDD packages for Haskell

Package name	Repository	BDD	ZDD	Style	Implementation	Hash-consing / Fast equality test
decision-diagrams (this package)	GitHub	✔️	✔️	pure	pure Haskell	✔️
zsdd	GitHub (deleted?)	✔️	✔️	monadic	pure Haskell	✔️
obdd	GitHub	✔️	-	pure	pure Haskell	-
HasCacBDD	GitHub	✔️	-	pure	FFI	✔️
hBDD (hBDD-CUDD, hBDD-CMUBDD)	GitHub	✔️	-	pure	FFI	✔️
cudd	GitHub	✔️	-	both pure*1 and monadic	FFI	✔️

*1: cudd's pure interface is different from normal Haskell data types (like ones in the containers package, for example) because it requires DDManager argument.

Please feel free to make a pull request for addition or correction to the comparision.