How to count list occurrences with a Data.Map?-CodePudding

Is there a way to use Data.Map in Haskell to find the number of occurrences in a given list, be it a character or an integer? For example: [Int] -> Map Int Int.

If it's possible to achieve, would you be able to do it without the use of fromList?

CodePudding user response：

You can produce a Map k Int that acts as a counter for the items in a list with fromListWith :: (Hashable k, Ord k) => (a -> a -> a) -> [(k, a)] -> Map k a. We can implement such function as:

{-# LANGUAGE TupleSections #-}

import Data.Hashable(Hashable)
import Data.HashMap(Map, fromListWith)

toCounter :: (Hashable a, Ord a) => [a] -> Map a Int
toCounter = fromListWith ( ) . map (,1)

Here we convert each element to a 2-tuple with 1 as the second item of the 2-tuple. In case there is a clash between two keys, we resolve this by summing up the number of times that item occurred.

This produces for example:

ghci> toCounter [1,4,2,5,1,3,0,2]
fromList [(0,1),(1,2),(2,2),(3,1),(4,1),(5,1)]

here for the list [1,4,2,5,1,3,0,2] 0, 3, 4 and 5 occur once, and 1 and 2 occur twice.

If it's possible to achieve, would you be able to do it without the use of fromList?

Yes, you can work with foldl' :: Foldable t => (b -> a -> b) -> b -> t a -> b and insertWith :: (Hashable k, Ord k) => (a -> a -> a) -> k -> a -> Map k a -> Map k a . I leave it as an exercise to convert the toCounter function to a fold pattern.