decision-diagrams: Binary Decision Diagrams (BDD) and Zero-suppressed Binary Decision Diagrams (ZDD)

[ bsd3, data, data-structures, library, logic ] [ Propose Tags ]


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


  • No Candidates
Versions [RSS],
Change log
Dependencies base (>= && <5), containers (>= && <0.7), hashable (>= && <1.5), hashtables (>= && <1.4), intern (>= && <, mwc-random (>= && <0.16), primitive (>= && <0.8), random (>=1.1 && <1.3), reflection (>=2.1.4 && <2.2), unordered-containers (>= && <0.3), vector (>= && <0.14) [details]
License BSD-3-Clause
Copyright 2021 Masahiro Sakai
Author Masahiro Sakai
Revised Revision 2 made by MasahiroSakai at 2022-08-13T15:21:36Z
Category Data, Data Structures, Logic
Home page
Bug tracker
Source repo head: git clone
Uploaded by MasahiroSakai at 2021-11-25T00:28:42Z
Distributions NixOS:
Downloads 229 total (14 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2021-11-25 [all 1 reports]

Readme for decision-diagrams-

[back to package description]


Hackage: Hackage Hackage Deps Hackage CI

Dev: Build Status Coverage Status

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.