Many of the most common sources of frustration and complaints about Haskell's packaging system have as their root cause limitations in the dependency solver in cabal-install.
To address some of these problems we have implemented a new dependency resolution algorithm with the following goals:
* to find solutions in more cases (by using backtracking),
* to produce better error messages,
* to be able to deal with private dependencies of packages,
* to be more configurable for the end user,
* to treat flags in a more uniform way,
* to be easier to extend or experiment with,
* to be faster, or at least not slower, than the old solver.
We explain the architecture of the new solver, which is inspired by Nordin and Tolmach's 2001 paper ``Modular Lazy Search for Constraint Satisfaction Problems. We also point out the rather subtle issues one has to solve in order to achieve all of the above goals.
The reimplementation of the solver is an ongoing effort, but ready for testing at http://darcs.haskell.org/cabal-branches/cabal-modular-solver/
We hope to also spark discussion on what features are on the "Most Wanted" list for Cabal dependency resolution.
From the Haskell Implementors Workshop 2011: http://www.haskell.org/haskellwiki/HaskellImplementorsWorkshop/2011