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

[wren ng thornton]

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