Function to find the most frequent element-CodePudding

I am trying to code a function that returns the element that appears the most in a list. So far I have the following

task :: Eq a => [a] -> a
task xs  = (map ((\l@(x:xs) -> (x,length l)) (occur (sort xs))))

occur is a function that takes a list and returns a list of pairs with the elements of the inputted list along with the amount of times they appear. So for example for a list [1,1,2,3,3] the output would be [(1,2),(2,1),(3,2)].

However, I am getting some errors related to the arguments of map. Can anyone tell me what I'm doing wrong?

CodePudding user response：

A map maps every item to another item, so here \l is a 2-tuple, like (1,2), (2, 1) or (3, 2). It thus does not make much sense to work with length l, since length :: Foldable f => f a -> Int will always return one for a 2-tuple: this is because only the second part of the 2-tuple is used in the foldable. But we do not need length in the first place.

What you need is a function that can retrieve the maximum based on the second item of the 2-tuple. We can make use of the maximumOn :: Ord b => (a -> b) -> [a] -> a from the exta package, or we can implement our own function to calculate the maximum on a list of items.

Such function thus should look like:

maximumSnd :: Ord b => [(a, b)] -> (a, b)
maximumSnd [] = error "Empty list"
maximumSnd (x:xs) = go xs x
    where go [] m = m
          go (x@(xa, xb):xs) (ya, yb)
              | xb > yb = go … …  -- (1)
              | otherwise = go … …  -- (2)

Here (1) should be implemented such that we make a recursive call but work with x as the new maximum we found thus far. (2) should make a recursive call with the same thus far maximum.

Once we have implemented the maxSnd function, we can use this function as a helper function for:

task :: Eq a => [a] -> (a, Int)
task xs  = maxSnd (occur xs)

or we can use fst :: (a, b) -> a to retrieve the first item of the 2-tuple:

task :: Eq a => [a] -> a
task xs  = (fst . maxSnd) (occur xs)

In case there are two characters with a maximum number of elements, the maximumSnd will return the first one in the list of occurrences.