Hi, I haven't seen that paper. I certainly agree with their point that Haskell easily allows to separate the code of the search and pruning algorithms from the code of the search-space etc. It seems that my package and their paper focus on different algorithms. They mostly focus on pruning methods, and it seems that the order they search in is always depth-first, although sometimes with reordering of nodes' children. They also use a different structure for the search trees. Theirs is like Data.Tree's. My package uses monadic trees (like "ListT []") and so allows the iteration of the tree to be monadic, allowing to add stateful pruning to the mix (by adding a StateT to the tree's underlying monad). In their paper they also describe stateful pruning methods, but if I understand correctly, the consumption of the trees has to be made by their backtracking functions which are aware of their pruning methods. cheers, Yair On Sep 27, 9:35 pm, wren ng thornton <w...@freegeek.org> wrote:
yair...@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 _______________________________________________ Haskell-Cafe mailing list Haskell-C...@haskell.orghttp://www.haskell.org/mailman/listinfo/haskell-cafe