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

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 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 --