On 4/12/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> 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..]
_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe