[Haskell-cafe] k-minima in Haskell

[Vincent Kraeutler]

Kurt Hutchinson wrote:
> 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..]


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..]



-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 249 bytes
Desc: OpenPGP digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070412/59c8bd89/signature.bin