On Thu, 2008-10-02 at 14:08 +0100, Simon Marlow wrote:
Simon Marlow wrote:
So I'm not sure exactly how cabal-install works now, but I imagine you could search for a solution with a backtracking algorithm, and prune solutions that involve multiple versions of the same package, unless those two versions are allowed to co-exist (e.g. base-3/base-4). If backtracking turns out to be too expensive, then maybe more heavyweight constraint-solving would be needed, but I'd try the simple way first.
Attached is a simple backtracking solver. It doesn't do everything you want, e.g. it doesn't distinguish between installed and uninstalled packages, and it doesn't figure out for itself which versions are allowed together (you have to tell it), but I think it's a good start. It would be interetsing to populate the database with a more realistic collection of packages and try out some complicated install plans.
I've not tried it yet, but the main danger with simple backtracking solvers is that they try too many solutions and take too long. It is afterall an NP-complete problem and the complete search space is exponential. We do need to find solutions for installing all of hackage simultaneously and consistently. The current solver does this in a few tens of seconds (but it does no backtracking). My intuition is that I would not go for a complete solver unless it was a good deal more heavyweight. There is a good paper in this area[1] and is the basis of the solver for the debian packages that the Linspire guys wrote. [1] Modular Lazy Search for Constraint Satisfaction Problems http://citeseer.ist.psu.edu/nordin01modular.html So when we have more time we should look at using a more sophisticated solver along these lines. Duncan