[Haskell-cafe] k-minima in Haskell

[Dino Morelli]

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 at ui3.info
/( )\   irc: dino-
^^-^^   preferred distro: Debian GNU/Linux  http://www.debian.org