[Haskell] Re: Quicksearch vs. lazyness

[apfelmus]

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