CODEWITHSUNDEEP
haskell
Ed Holloway-George
Ed Holloway-George

Reputation: 5149

Function to show the lowest represented element in a list

If you have a list such as this in Haskell: 

data TestType = A | B | C deriving (Ord, Eq, Show) 

List1 :: [TestType]
List1 = [A,B,C,B,C,A,B,C,C,C]

Is it possible to write a function to determin which element is represented the least in a list (so in this case 'A')

My initial thought was to write a helper function such as this but now I am not sure if this is the right approach:

appears :: TestType -> [TestType] -> Int
appears _ [] = 0
appears x (y:ys) | x==y = 1 + (appears x ys)
                 | otherwise = appears x ys

I am still fairly new to Haskell, so apologies for the potentially silly question.

Many thanks

Upvotes: 1

Views: 185

Answers (4)

epsilonhalbe
epsilonhalbe

Reputation: 15967

A less elegant idea would be:

  • At first sort and group the list
  • then pairing the cases with their number of representations
  • at last sort them relative to their num of representations

In code this looks like

import Data.List                                                                 

sortByRepr :: (Ord a) => [a] ->[(a,Int)]
sortByRepr xx = sortBy compareSnd $ map numOfRepres $ group $ sort xx
              where compareSnd x y = compare (snd x) (snd y)
                    numOfRepres x = (head x, length x)

the least you get by applying head to the resulting list.

Upvotes: 1

Jani Hartikainen
Jani Hartikainen

Reputation: 43243

Slightly alternative version to Matt's approach

import Data.List
import Data.Ord

leastFrequent :: Ord a => [a] -> a
leastFrequent = head . minimumBy (comparing length) . group . sort

Upvotes: 7

Matt Fenwick
Matt Fenwick

Reputation: 49085

Here's another way to do it:

  1. sort the list
  2. group the list
  3. find the length of each group
  4. return the group with the shortest length

Example:

import GHC.Exts
import Data.List

fewest :: (Eq a) => [a] -> a
fewest xs = fst $ head sortedGroups 
where 
  sortedGroups = sortWith snd $ zip (map head groups) (map length groups)
  groups = group $ sort xs

Upvotes: 2

Daniel Fischer
Daniel Fischer

Reputation: 183858

You can build a map counting how often each item occurs in the list

import qualified Data.Map as Map

frequencies list = Map.fromListWith (+) $ zip list (repeat 1)

Then you can find the least/most represented using minimumBy or maximumBy from Data.List on the list of Map.assocs of the frequency map, or even sort it by frequency using sortBy.

module Frequencies where

import Data.Ord
import Data.List
import qualified Data.Map as Map

frequencyMap :: Ord a => [a] -> Map.Map a Int
frequencyMap list = Map.fromListWith (+) $ zip list (repeat 1)

-- Caution: leastFrequent will cause an error if called on an empty list!
leastFrequent :: Ord a => [a] -> a
leastFrequent = fst . minimumBy (comparing snd) . Map.assocs . frequencyMap

ascendingFrequencies :: Ord a => [a] -> [(a,Int)]
ascendingFrequencies = sortBy (comparing snd) . Map.assocs . frequencyMap

Upvotes: 2

Related Questions