[Haskell-cafe] lazy data structure for best-first search

Martin Hofmann martin.hofmann at uni-bamberg.de
Tue Jul 7 20:35:51 EDT 2009


Thanks Dan,

that gave me some new input I can continue working on.

Cheers,

Martin

Am Dienstag, den 07.07.2009, 10:18 -0700 schrieb Dan Piponi:
> On Wed, Jun 24, 2009 at 6:53 PM, Martin
> Hofmann<martin.hofmann at uni-bamberg.de> wrote:
> > I am looking for a good (preferably lazy) way to implement some kind of
> > best-first search.
> 
> > So in fact, after one expansion, I need to fold over my complete search
> > space, maybe updating other nodes and recompute the value of the cost
> > function for the affected nodes.
> 
> A bit late, but it just dawned on me that if I understand you
> correctly I may have stumbled on the same problem when I was
> implementing the code here
> http://blog.sigfpe.com/2009/07/monad-for-combinatorial-search-with.html
> 
> I tried to modify that code so that I could assign costs that were of
> type Float. But I found that it was computing costs for more of the
> graph than I wanted and that for infinite search spaces I'd never get
> termination. The code I ended up writing in that post solves your
> problem, in effect by storing costs lazily. That way you can compare
> the cost of A and B without having to force a full computation of the
> cost of both A and B and making it safe to fold over infinite search
> trees. In fact, my zipm function is essentially a fold with a lazy
> version of the mergeOn function that Luke Palmer suggests in another
> reply.
> 
> That code is best when the costs are all small non-negative integers,
> which may or may not be adaptable to your problem.
> --
> Dan
-- 
-------------------------



More information about the Haskell-Cafe mailing list