[Haskell-cafe] lazy data structure for best-first search
wren ng thornton
wren at freegeek.org
Thu Jun 25 00:50:49 EDT 2009
Martin Hofmann wrote:
> 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?
If you have to re-sort the data at each step, then you will have to
explore/generate all options (or near enough) in order to select the
best first. This is a natural consequence of not having any "control"
over the order of generation.
If you can maintain that the results of each step are stored in an order
such that the priority function is monotone wrt the input sequences,
then you can start doing things like lazy cube pruning which allow
you to defer or prune sub-optimal options when generating the best-first
list to the next layer. As the expectation of monotonicity falls, you
end up exploring more suboptimal combinations unnecessarily.
More information about the Haskell-Cafe