obdd: Ordered Reduced Binary Decision Diagrams

[ library, logic ] [ Propose Tags ]

Construct, combine and query OBDDs; an efficient representation for formulas in propositional logic.

This is mostly educational. The BDDs do not share nodes (there is no persistent BDD base) and this might introduce inefficiencies.

An important (for me, in teaching) feature is that I can immediately draw the BDD to an X11 window (via graphviz). For example, to show the effect of different variable orderings, try this in ghci (type q to close the drawing windows).

import Prelude hiding (not,(&&),(||),and,or,any,all)
import OBDD
let f [] = false; f (x:y:zs) = x && y || f zs
display $ f $ map variable [1,2,3,4,5,6]
display $ f $ map variable [1,4,2,5,3,6]

OBDD implements Ersatz.Boolean which re-defines Boolean operations from the Prelude. The recommended way of using this is shown in the previous example.

If you want better performance, use a library with a persistent BDD base, e.g., CUDD Haskell bindings, see this example.

Versions 0.2, 0.2.3, 0.2.5, 0.2.7, 0.3.1, 0.3.2, 0.3.3, 0.4.0, 0.5.0, 0.6.0, 0.6.1, 0.8.1, 0.8.2
Dependencies array, base (==4.*), containers (>=0.5), ersatz, mtl, process-extras, random, text [details]
License LicenseRef-GPL
Author Johannes Waldmann
Maintainer Johannes Waldmann
Category Logic
Home page https://github.com/jwaldmann/haskell-obdd
Source repo head: git clone git://github.com/jwaldmann/haskell-obdd.git
Uploaded by JohannesWaldmann at Sun May 20 20:02:39 UTC 2018
Distributions NixOS:0.8.1
Downloads 3212 total (47 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2018-05-20 [all 1 reports]
Hackage Matrix CI




Maintainer's Corner

For package maintainers and hackage trustees