Count the number of occurences of each element and return them as a list of tuples

Question

I have to write the elemFreqByFirstOcc :: Eq a => [a] -> [(a, Int)] that should count the occurences of each element in the list and return the elements and the results in a list of tuples.

For example:

elemFreqByFirstOcc "adbcba" == [('a',2),('d',1),('b',2),('c',1)]

elemFreqByFirstOcc [1,2,1,3,3,2,1,4,3,2,1,1,1,4,6,5] == [(1,6),(2,3),(3,3),(4,2),(6,1),(5,1)]

So far, I have this code, which works fine if all the elements in the list show up only once, but when an element shows up more times, they get counted each time. (So for the first example, it returns [('a',2),('d',1),('b',2),('c',1),('b',1),('a',1)])

elemFreqByFirstOcc :: Eq a => [a] -> [(a, Int)]
elemFreqByFirstOcc [] = []
elemFreqByFirstOcc [x] = [(x, 1)]
elemFreqByFirstOcc (x:xs) = zip [x] [(length $ filter (==x) (x:xs))] ++ elemFreqByFirstOcc xs

Answer 1

You need to filter out the items that you already counted, so:

elemFreqByFirstOcc :: Eq a => [a] -> [(a, Int)]
elemFreqByFirstOcc [] = []
elemFreqByFirstOcc (x:xs) = (x, length (filter (x ==) xs) + 1) : elemFreqByFirstOcc (filter (x /=) xs)