[Haskell-cafe] lazy data structure for best-first search
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