Martin Hofmann wrote:
Thanks for the quick and short answer. Maybe I am already thinking too complicated.
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 where 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[1] 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. [1] http://www.cis.upenn.edu/~lhuang3/huang-iwpt-correct.pdf -- Live well, ~wren