[Haskell-cafe] Re: ANN: ListTree 0.1

[yairchu at gmail.com]

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... at freegeek.org> wrote:
> yair... 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
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-C... at haskell.orghttp://www.haskell.org/mailman/listinfo/haskell-cafe