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

Dan Piponi dpiponi at gmail.com
Tue Jul 7 13:18:56 EDT 2009


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