planning for ghc-6.10.1 and hackage [or: combining packages to yield new type correct programs]

[Duncan Coutts]

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