So I already have a function that finds the number of occurrences in a list using maps.
occur :: [a] -> Map a a
occur xs = fromListWith (+) [(x, 1) | x <- xs]
For example if a list [1,1,2,3,3] is inputted, the code will output [(1,2),(2,1),(3,2)], and for a list [1,2,1,1] the output would be [(1,3),(2,1)].
I was wondering if there's any way I can change this function to use foldr instead to eliminate the use of maps.
You can make use of foldr where the accumulator is a list of key-value pairs. Each "step" we look if the list already contains a 2-tuple for the given element. If that is the case, we increment the corresponding value. If the item x does not yet exists, we add (x, 1) to that list.
Our function thus will look like:
occur :: Eq => [a] -> [(a, Int)]
occur = foldr incMap []where incMap thus takes an item x and a list of 2-tuples. We can make use of recursion here to update the "map" with:
incMap :: Eq a => a -> [(a, Int)] -> [(a, Int)]
incMap x = go
where go [] = [(x, 1)]
go (y2@(y, ny): ys)
| x == y = … : ys
| otherwise = y2 : …where I leave implementing the … parts as an exercise.
This algorithm is not very efficient, since it takes O(n) to increment the map with n the number of 2-tuples in the map. You can also implement incrementing the Map for the given item by using insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a, which is more efficient.