Steffen Mazanek wrote:
ok, but this still means, that you have to rewrite the algorithm to get an efficient qsearch for arbitrary k.
You mean the case when you only want the k-th minimum but not the others? Well, you can make this work with qsort, too. The fundamental solution would be to change the data type returned by qsort to better support random access to the k-th element. A binary search tree that only gets partially evaluated is well suited for that. But I think you can get the desired behavior without changing the type of qsort but by explicitly introducing the invariant that qsort doesn't change the length of the list. qsort [] = [] qsort (x:xs) = zip2nd ls (qsort ls) ++ [x] ++ zip2nd rs (qsort rs) where ls = filter ( < x) xs rs = filter (>= x) xs -- forces the second argument to have the same length -- as the first. zip2nd [] _ = [] zip2nd (_:xs) ~(y:ys) = y:zip2nd xs ys Now (assuming proper pivot again), qsort xs !! k only takes O(n) time to retrieve the k-th minimum because only the relevant recursive calls to qsort will be evaluated. The curious reader may recognize what should probably be coined the "blueprint technique".
Are there any popular algorithms whose overall complexity is improved by lazyness? Or where you get such special cases as free lunch?
Well, it's highly unlikely that algorithms get faster by introducing laziness. I mean, lazy evaluation means to evaluate only those things that are really needed and any good algorithm will be formulated in a way such that the unnecessary things have already been stripped off. But laziness allows to simplify and compose algorithms. Sometimes, seemingly different algorithms turn out to be two sides of the same coin when formulated with lazy evaluation. Isn't it great that finding the k-th minimum is not only an adaption of quicksort but can readily be obtained from it by _composing_ it with (!! k)? Regards, apfelmus