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

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

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

Candidates

  • No Candidates
Versions [RSS] 0.1.0.0, 0.2.0.0
Change log ChangeLog.md
Dependencies base (>=4.11.0.0 && <5), containers (>=0.5.11.0 && <0.7), hashable (>=1.2.7.0 && <1.5), hashtables (>=1.2.3.1 && <1.4), intern (>=0.9.1.2 && <1.0.0.0), mwc-random (>=0.13.6.0 && <0.16), primitive (>=0.6.3.0 && <0.8), random (>=1.1 && <1.3), reflection (>=2.1.4 && <2.2), unordered-containers (>=0.2.9.0 && <0.3), vector (>=0.12.0.2 && <0.14) [details]
License BSD-3-Clause
Copyright 2021 Masahiro Sakai
Author Masahiro Sakai
Maintainer masahiro.sakai@gmail.com
Revised Revision 2 made by MasahiroSakai at 2022-08-13T15:21:36Z
Category Data, Data Structures, Logic
Home page https://github.com/msakai/haskell-decision-diagrams#readme
Bug tracker https://github.com/msakai/haskell-decision-diagrams/issues
Source repo head: git clone https://github.com/msakai/haskell-decision-diagrams
Uploaded by MasahiroSakai at 2021-11-25T00:28:42Z
Distributions NixOS:0.2.0.0
Downloads 238 total (6 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-0.2.0.0

[back to package description]

decision-diagrams

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.