TY - JOUR
AU - Jan Christiansen
AU - Frank Huch
AB - This paper presents an implementation of the ROBDD data structure in Haskell. It shows that lazy evaluation can be used to improve the performance of some ROBDD algorithms. While standard implementations construct the whole structure no matter which parts are demanded we use lazy evaluation to provide a more demand driven construction. To achieve this behavior we have to relax a property that guarantees that ROBDDs contain no redundant nodes. All measurements show that relaxing causes only a small number of additional nodes. Furthermore we present an equality check implementation that performs well although it does not make use of canoicity. The canonicity is lost because of the relaxing. The equality check implementation benefits highly from laziness.
BT - Trends in Functional Programming
N2 - This paper presents an implementation of the ROBDD data structure in Haskell. It shows that lazy evaluation can be used to improve the performance of some ROBDD algorithms. While standard implementations construct the whole structure no matter which parts are demanded we use lazy evaluation to provide a more demand driven construction. To achieve this behavior we have to relax a property that guarantees that ROBDDs contain no redundant nodes. All measurements show that relaxing causes only a small number of additional nodes. Furthermore we present an equality check implementation that performs well although it does not make use of canoicity. The canonicity is lost because of the relaxing. The equality check implementation benefits highly from laziness.
PY - 2006
SP - 55
EP - 71
T2 - Trends in Functional Programming
TI - A Purely Functional Implementation of ROBDDs in Haskell
VL - 7
ER -