Hello, 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, Steffen _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell