[Haskell-cafe] k-minima in Haskell

[Kurt Hutchinson]

On 4/12/07, ajb at spamcop.net <ajb at 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..]