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

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

Please see the README on GitHub at https://github.com/msakai/haskell-decision-diagrams#readme


[Skip to Readme]
Versions [RSS] [faq] 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.13) [details]
License BSD-3-Clause
Copyright 2021 Masahiro Sakai
Author Masahiro Sakai
Maintainer masahiro.sakai@gmail.com
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
Downloads 103 total (85 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2021-11-25 [all 1 reports]

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees

Candidates


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.