[Haskell-cafe] lazy data structure for best-first search
martin.hofmann at uni-bamberg.de
Wed Jun 24 21:53:21 EDT 2009
I am looking for a good (preferably lazy) way to implement some kind of
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,
More information about the Haskell-Cafe