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: [EMAIL PROTECTED]
/( )\ irc: dino-
^^-^^ preferred distro: Debian GNU/Linux http://www.debian.org
_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
