[Haskell] Quicksearch vs. lazyness

Steffen Mazanek smazanek at steffen-mazanek.de
Mon Mar 19 08:09:38 EDT 2007


say, we want to find the k'th element in a sorted list.

In imperative languages it is much more efficient
to not use quicksort first and get the k'th element later,
but to use a quicksearch algorithm that sorts only
the relevant parts of the array.

In Haskell one could implement this idea as follows:

qsearch k [] = error ...
qsearch k (x:xs)
 | lsmaller >= k = qsearch k smaller
 | lsmaller == 0 && k > 1 = qsearch (k-1) greater
 | lsmaller == 0 = x
 | otherwise = qsearch (k-lsmaller) (x:greater)
 where smaller = filter (<= x) xs
           lsmaller = length smaller
           greater = filter (> x) xs

However, I was wondering whether it might be possible
to implement quicksort in a way that quicksearch is
done out of the box by lazy evaluation. Is there any way
to do this? From my understanding for small k's lazy
evaluation already does the trick for the naive quicksort
algorithm (quicksort smaller ++ [x] ++ quicksort greater),
doesn't it? Is there a search algorithm that makes better
use of lazy evaluation out of the box?

Best regards,


More information about the Haskell mailing list