Finding a "Count Sequence"

Question

Given a list of integers xs, let:

count :: [Integer] -> Integer -> Integer
count xs n = length . filter (==n) $ xs

count the number of times the integer n occurs in the list.

Now, given a "list" (some sort of array of integers, can be something besides a List) of length n, write a function

countSequence :: [Integer] -> Integer -> Integer -> Integer
countSequence xs n m = [count xs x | x <- [0..m]]

that outputs the "list of counts" (0th index contains number of times 0 occurs in the list, 1st index contains number of times 1 occurs in the list, etc) that has time compleity o(m*n)

The above implementation I've given has complexity O(m*n). In Python (which I'm more familiar with), it's easy to do this in O(m + n) time --- iterate through the list, and each element increment a counter in some other list, which is initialized to be all zeros and length (m+1).

How could I get a better implementation in Haskell? I'd prefer if it wasn't some trivial way to implement the Python solution (such as adding another input to the function to keep the "list of counts" in and then interating through it).

Answer 1

In O(n+m) (sort of, I think, maybe):

import Data.Ix (inRange)
import qualified Data.IntMap.Strict as IM

countSequence m =
  foldl' count IM.empty . filter (inRange (0,m))
    where count a b = IM.insertWith (+) b 1 a

gives

> countSequence 2 [1,2,3,1,2,-1]
fromList [(1,2),(2,2)]

I haven't used n because you also didn't use n and I'm not sure what it's supposed to be. I also moved the list to the last argument to put it in a position to be eta reduced.