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

Martin Hofmann martin.hofmann at uni-bamberg.de
Thu Jun 25 00:38:59 EDT 2009

Thanks for the quick and short answer. Maybe I am already thinking too

However, exactly your given preconditions I can not satisfy.

> The preconditions for bestFirst rate edges xs are:  map rate xs must
> be nondecreasing, 

Here lies my problem, because edges must also be applied to xs. So a
quick fix of bestFirst would be the following:

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

And here I am afraid, that my efficiency gets worse.

Or do I worry too much?


More information about the Haskell-Cafe mailing list