Haskell - compute frequencies of elements in a list

Question

I need to compute a frequency map of an input list. My attempt:

f :: (Eq a, Ord a) => (a -> a) -> Map.Map a Int -> Map.Map a Int
f x m = Map.alter id (Map.findWithDefault 0 x m + 1) m

freqs :: (Eq a, Ord a) => [a] -> Map.Map a Int
freqs xs = foldr f (Map.fromList []) xs

Needless to say, the above does not compile.

There seems to be at least one question for frequency counts, yet, in my case, there are requirements:

1. Need to use Map.alter
2. Need to use foldr (Map.findWithDefault might come in handy, too.)

Question: What am I missing here?

Answer 1

As your question doesn't state the thought process behind your current non-compiling solution attempt, I can't really tell where it went wrong or how to fix it, so instead I'll walk you along my own thought process in attempting to solve this problem with the given constraints.

Before I do that, some general observations, that might help inform your own further attempts:

• In exercises like this, you're usually not expected to use the stuff that the exercise states you must use (here: Map.alter and foldr) in very convoluted or unusual ways. Often, you're in fact expected find out more about their exemplar prototypical usage (i.e., what they're considered to be "good for"), which often fits the task at hand so well that it'll be rather simple — at least in retrospect.
• Map.alter is for modifying a single entry of a Map, identified by its key — maybe adding or removing it, maybe just changing the associated value.
• foldr is for processing a Foldable in general or specifically a list. In imperative languages, you'd use a loop and an accumulator variable (or accumulator data structure) in mostly the same situations.
• If an exercise states that something "might come in handy, too", there's often a straight forward solution without it and another, maybe similarly straight forward one, that might require it. Thus, don't try to shove these things in from the beginning, just keep them in mind in case you'll see a clear use for them.

In this answer, I'll assume that the Map module is imported as suggested in its documentation:

import Data.Map (Map)
import qualified Data.Map as Map

So the task seems to be counting number of occurrences for all distinct elements of a list, using Map.alter and foldr, returning the result as a Map from elements to number or occurrences.

Idea: Let's start with an empty map, and look at the elements of the list one by one, generating updated maps accounting for the elements seen so far.

Can we use Map.alter for getting from one of these maps to the subsequent one? Let's look at its signature:

alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a 

So if we pass a function from Maybe a to Maybe a and a key, we'll get a function that "changes" a map (takes one such map as an argument and returns a map of the same type). The documentation doesn't spell out what the Maybe a argument will be passed to that function we pass as first argument to Map.Alter, but it seems quite plausible that it's Just the previous value at the key in question if present, and Nothing otherwise. The role of the return value is clear from the examples given in the documentation: Nothing "deletes" the entry (i.e., omits it from the resulting Map), Just x "modifies" the value of the entry at the given key to x if already present or "inserts" the key-value par with the given key and value x if it wasn't already in the passed Map.

So we need a function we can plug as first argument into Map.alter. That function will receive Just the previous count for the element at question or Nothing if it didn't occur yet and will have to return Just the new count considering one more occurrence of the element, i.e., increase it by one. We can easily write that function:

inc :: Maybe Int -> Maybe Int
inc Nothing = Just 1
inc (Just n) = Just $ n + 1

We have to use foldr. Probably it's to handle all elements from the input list. Let's look at its signature:

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

We know we are dealing with not just any Foldable, but specifically with a list, so for our case, this becomes

foldr @[] :: (a -> b -> b) -> b -> [a] -> b

(In GHCi, you can query this with :t foldr @[].)

We can use our input list as the third argument (of type [a]). Type b is the type of both, the end result and of the intermediate results (which one might consider accumulators). From our idea stated above, we can conclude that Map a Int fits nicely as b. The second argument of foldr is the "start value" of the "accumulator". According to said idea, it must be Map.empty.

So what's still missing is the first argument, a function from a (type of the elements of the list) and b (the Map a Int representing the counts so far) to b (another Map a Int, representing the counts updated with the occurrence of that element). I'll call that function considerOccurence, because it gives us a map of updated tallies considering one more occurrence of a specific element. It's type must be Ord a => a -> Map a Int -> Map a Int. With Map.alter and our inc from above, we can easily implement it:

considerOccurence :: Ord a => a -> Map a Int -> Map a Int
considerOccurence x previousCounts = Map.alter inc x previousCounts

or in point-free notation:

considerOccurence :: Ord a => a -> Map a Int -> Map a Int
considerOccurence = Map.alter inc

Now we can plug considerOccurence into foldr to get the function we want for the overall task:

freqs :: Ord a => [a] -> Map a Int
freqs xs = foldr considerOccurence Map.empty xs

or in point-free notation

freqs :: Ord a => [a] -> Map a Int
freqs = foldr considerOccurence Map.empty

In case you want it all in a single top-level function:

freqs :: Ord a => [a] -> Map a Int
freqs = foldr considerOccurence Map.empty
  where
    considerOccurence = Map.alter inc
    inc Nothing = Just 1
    inc (Just n) = Just $ n + 1

Let's test it:

>>> freqs "Missisippi"
fromList [('M',1),('i',4),('p',2),('s',3)]