On Thu, 12 Apr 2007, raghu vardhan wrote:
What's the best way to implement the following function in haskell: Given a list and an integer k as input return the indices of the least k elements in the list. The code should be elegant and also, more importantly, must not make more than the minimum O(k*length(list)) number of operations.
R M
I don't know about performance, but trying this problem I was struck again by the gorgeous, terse code that can be created: import Data.List import Data.Ord kminima :: (Enum a, Num a, Ord b) => Int -> [b] -> [a] kminima k lst = take k $ map fst $ sortBy (comparing snd) $ zip [0 ..] lst commented: kminima k lst = take k -- We want k items off the front $ map fst -- Just the list of indices $ sortBy (comparing snd) -- Sort the pairs by their snd $ zip [0 ..] lst -- Preserve indices in tuples Prelude> :l kminima.hs [1 of 1] Compiling Main ( kminima.lhs, interpreted ) Ok, modules loaded: Main. *Main> kminima 3 [71,71,17,14,16,91,18,71,58,75,65,79,76,18,4,45,87,51,93,36] [14,3,4] *Main> kminima 4 [10,9,8,7,6,5,4,3,2,1] [9,8,7,6] -- .~. Dino Morelli /V\ email: dino@ui3.info /( )\ irc: dino- ^^-^^ preferred distro: Debian GNU/Linux http://www.debian.org