[Haskell-cafe] Re: k-minima in Haskell

Fawzi Mohamed fmohamed at mac.com
Fri Apr 13 06:03:33 EDT 2007

For various reasons I had a similar problem that I solved iteratively 
simply with a sorted list of the actual best elements.

The only particular things were

1. keep element count (to easily know if the element should be inserted 
in any case)

2. keep the list in reverse order to have the biggest element as first, 
and make the common case (list stays the same) fast

3. make the list strict (avoid space leaks)

not the best in worst case of decreasingly ordered elements O(n*k), but 
good enough for me.

A set + explicit maximal element would probably be the best solution.


-- | keeps the score of the n best (high score)
-- (uses list, optimized for small n)
data NBest a = NBest Int [a] deriving (Eq)

-- | merges an element in the result with given ranking function
merge1 :: Int -> (a -> Double) -> a -> NBest a -> NBest a
merge1 n rankF fragment (NBest m []) | m==0 && n>0 = NBest 1 [fragment]
    | m==0 = NBest 0 []
    | otherwise = error "empty list and nonzero count"
merge1 n rankF fragment (NBest m (xl@(x0:xs)))
    | n>m = NBest (m+1) (insertOrdered fragment xl)
    | rankF fragment < (rankF x0) = NBest n (insertOrdered fragment xs)
    | otherwise = NBest m xl
      insertOrdered x (x1:xr) | rankF x >= rankF x1 = x:x1:xr
                              | otherwise =
                                  let r = insertOrdered x xr
                                  in x1 `seq` r `seq` x1:r where
      insertOrdered x [] = [x]

More information about the Haskell-Cafe mailing list