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

[Fawzi Mohamed]

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.

Fawzi

-- | 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
    where
      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]