Re: [Haskell-cafe] k-minima in Haskell

Kurt Hutchinson wrote:

On 4/12/07, ajb@spamcop.net wrote:

...

To get the indices, use the Schwartzian transform:

sortWith :: (Ord b) => (a -> b) -> [a] -> [a] sortWith f = mergeRuns . runs where runs = map (:[])

mergeRuns [] = [] mergeRuns [xs] = xs mergeRuns xss = mergeRuns (mergeRun xss)

mergeRun (xs1:xs2:xss) = mergeOne xs1 xs2 : mergeRun xss mergeRun xss = xss

mergeOne [] ys = ys mergeOne xs [] = xs mergeOne xs'@(x:xs) ys':(y:ys) = case compare (f x) (f y) of LT -> x : mergeOne xs ys' GT -> y : mergeOne xs' ys EQ -> x : y : mergeOne xs ys

getKMinima :: (Ord a) => [a] -> [Int] getKMinima k = map fst . take k . sortWith snd . zip [0..]

For my own edification, what is the benefit of this sortWith over sortBy?

f `on` g = \ x y -> f ( g x ) ( g y ) kminima k = map fst . take k . sortBy ( compare `on` snd ) . zip [0..]

possibly related (newbie question): pairs are instances of Ord, why not directly sort those (implying the item to be sorted is fst):

kminima k = \list -> map snd $ take k $ sort $ zip list [0..]