Counting unique elements in a list

Question

Is there a straight-forward combination of standard higher-order funtions to count the unique elements in a list?

For example the result for

[1, 1, 4, 0, 4, 4]

would be something like

[(1,2), (4,3), (0,1)]

Answer 1

If order is not important this works:

map (\xs@(x:_) -> (x, length xs)) . group . sort

group . sort will give you a list of lists where all elements that are equal to each other are grouped into the same sublist (without sort, only consecutive equal elements would be grouped together). The map then turns each sublist into a (element, lengthOfSublist)-tuple.

If you want to order the result by first occurrence, you can use zip before the sort to add an index to each element, then, after grouping, sort again by that index and then remove the index.

Answer 2

The simplest thing would be to sort the items into order, use "group" to put them into sub-lists of equal elements, and then count the items in each sub-list.

map (\xs -> (head xs, length xs)) . group . sort

Answer 3

If the list contains only integers, you could also use

 import qualified Data.IntMap as I

 countElems1 :: [Int] -> [(Int, Int)]
 countElems1 = I.toList . foldr (\k -> I.insertWith (+) k 1) I.empty 

(Remember to compile with optimization though, otherwise this will be 2x slower than the group . sort method. With -O2 it is slightly faster by 14%.)

You could also use one of the multiset packages which makes the function as simple as

 import qualified Math.Combinatorics.Multiset as S
 countElems4 = S.toCounts . S.fromList

but being less efficient.

All of the above solutions ignore the original order.

Answer 4

What your talking about is just run length encoding on sorted data: the free online book Real World Haskell has a great example of this. You will want to sort the list before you put it through the runLengthEncoder.

Answer 5

Using Data.Map and tuple sections:

 count = Map.fromListWith (+) . map (, 1)

(Add Map.toList if you need a list.)