Announcing decision diagrams

[Josef Svenningsson]

Hi,

A few weeks ago during the Hackathon in Gothenburg I started working
on a library for decision diagrams. The purpose was to use it in
cabal-install when figuring out which packages should be installed and
which version of them to choose. Why do we need something as complex
as decision diagrams for that? Simply because the problem is
NP-complete in general. Now, heuristics might do a good job at solving
this problem but it might be wise to have something like this library
as a fall-back.

So, I'm happy to announce the first version of my decision diagram
library.  The darcs repo can be found here:
http://www.cs.chalmers.se/~josefs/decisiondiagram

The status of the library is as follows: I'm beginning to trust the
correctness of the implementation. There are a few tests in place and
although I have more tests in mind the testing that I have already
done gives me quite a bit of confidence. As to the speed of the
library: it's pretty poor. I've used most of the tricks in the book on
implementing decision diagrams so complexity  wise it should be like
any other BDD implementation except for a few log factors here and
there. But I haven't cared anything about constant factors, so the
wall clock performance is pretty weak. As a benchmark I wrote a small
sudoku solver but my library choked on even an easy puzzle. I
nevertheless feel that this library is a good starting point and that
it will be able to handle all current packages that we have easily.

I am aware that the is a GSOC project coming up which is supposed to
tackle this issue as well. This package is by no means meant to
supersede that project before it has begun. I think we can benefit
from several approaches here since the underlying problem is
NP-complete and thus it's probably wise to evaluate more than one
option.

I haven't looked into how to use this package in cabal-install yet,
but I suspect it will be fairly easy. I'd appreciate any comments and
help on that though since I'm not familiar with the cabal-install code
base yet.

Happy cabaling,

Josef