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

Here's what I came up with.

bestFirst :: (Ord o) => (a -> o) -> (a -> [a]) -> [a] -> [a]
bestFirst rate edges = go
    where
    go [] = []
    go (x:xs) = x : go (mergeOn rate (edges x) xs)

mergeOn :: (Ord o) => (a -> o) -> [a] -> [a] -> [a]
mergeOn f [] ys = ys
mergeOn f xs [] = xs
mergeOn f (x:xs) (y:ys)
    | f x <= f y = x : mergeOn f xs (y:ys)
    | otherwise = y : mergeOn f (x:xs) ys

The preconditions for bestFirst rate edges xs are: map rate xs must be nondecreasing, and for all x, map rate (edges x) must be nondecreasing, and all no less than x. Then I believe this is A*. At least in spirit it is, though there might be "too many merges" making the complexity worse. I'm not terribly good at analyzing those things.

Luke

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

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe