How to count one list against another, in O (n * log (n))?

Question

I am looking for a function that can efficiently count for each element in one list its occurrences in another list. It should return a sorted list of element / count tuples. Here is the specification:

countList :: Ord a => [a] -> [a] -> [(a, Integer)]
countList ['a', 'b', 'c', 'b', 'b'] ['a', 'b', 'x']
                               == [('a', 1), ('b', 3), ('x', 0)]
length (countList xs ys) == length ys

A naive implementation would be:

countList xs = sort . map (id &&& length . (\ y -> filter (== y) xs))

That O(n^2). However, as we have Ord a, this can be done a little faster using a better strategy. First, we can sort both lists, and then compare them in the fasion “staircase maze”.

For example, two lists are sorted here. If I did this strongly, I would use two pointers pointing to the first item in each list:

       i
       |
xs = ['a', 'b', 'b', 'b', 'c']
ys = ['a', 'b', 'x']
       |
       j

i, xs !! i == ys !! j, j. i , ys, j, . O(n*log(n)).

, - , , . Haskell?

Answer 1

2- , 1- , Data.Map. n1 log n2:

import Data.Map (fromList, toList, adjust)

countList :: Ord a => [a] -> [a] -> [(a, Int)]
countList l r = toList $ foldr (adjust (+1)) (fromList . zip r $ repeat 0) l

Answer 2

, , :

import Data.List (sort)

countList :: Ord a => [a] -> [a] -> [(a, Int)]
countList l1 l2 = countList' (sort l1) (sort l2)
  where countList' _     []  = []
        countList' xs (y:ys) = let xs'   = dropWhile (<  y) xs
                                   (a,b) = span      (== y) xs'
                                in (y, length a) : countList' b ys

main = print $ countList ['a', 'b', 'c', 'b', 'b'] ['a', 'b', 'x']