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

[Martin Hofmann]

I am looking for a good (preferably lazy) way to implement some kind of
best-first search. 

The problem is, the expansion of the 'best' node in the search space
forces other 'inferior' nodes to expand too. So my function

 expand :: Node -> ([Node],(Node -> [Node]))

does not only return some successor nodes, but also a function to expand
other Nodes with certain characteristics. 

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.

At the moment I am using StateT monad transformers, and retrieving the
affected Nodes from a map (to avoid going through whole space), but this
is not very elegant and I doubt whether it is efficient, too.

I have already read through Spivey's paper "Algebras for combinatorial
search". Unfortunately, he only proposes the use of heuristics and
best-first search in combination with his framework for future work.
Does anybody now some further papers on this topic? 

Thanks a lot in advance,

Martin