[Haskell-cafe] ANN: ListTree 0.1

[wren ng thornton]

yairchu at gmail.com wrote:
> Hi,
> I am pleased to announce the release of ListTree.
> ListTree is a package for combinatorial search and pruning of trees,
> and should be useful for problems such as those in Google Code Jam
> (where I, and possibly others* could make use of it), but possibly
> could even be useful for real applications!
> [...]
> One problem with my package (which I'll attempt fixing), however, is
> speed. I haven't used it during the competition, and the quick and
> dirty, less modular code, that I coded in the competition, which
> performs exactly the same algorithm, runs a 100 times faster! Both are
> fast enough, but this is still troubling.
> I guess I should look into "Stream Fusion" to try and make my package
> faster.

Have you seen Andrew Tolmach & Thomas Nordin's "Modular Lazy Search for 
Constraint Satisfaction Problems"? They describe a very similar project 
which incorporates many of the common optimizations in the field 
(backjumping, backmarking, forward-checking, fail-first,...) and provide 
their code as well.

     paper: http://web.cecs.pdx.edu/~apt/jfp01.ps
     code:  http://web.cecs.pdx.edu/~apt/CSP_jfp.hs

-- 
Live well,
~wren