Find.hs

type Bucket k v = [(v, [k])]

insert :: k -> v -> Bucket k v -> Bucket k v
insert k v bucket@((v0, ks):bucket')
    | v == v0   = (v0, k:ks) : bucket'
    | v <  v0   = (v,  k:[]) : bucket
    | otherwise = (v0, ks) : insert k v bucket'

query :: k -> k -> Int -> Bucket k v -> [v]
query k1 k2 n bucket@((v0, ks):bucket') =
    let sel     = filter (\k -> k >= k1 && k <= k2) ks
        rest    = n - length sel
    in  if rest > 0
            then sel ++ query k1 k2 rest bucket'
            else sel

fromPairs :: [(k, v)] -> [(v, [k])]
fromPairs = undefined