Counting letters

ElementCounts.hs

import qualified Data.Map.Strict as M
import Data.Map.Strict (Map)
import Data.Tuple (swap)
import Data.List


-- task: map each element to how often it already occured before
-- count "abbcccghabc" -> [1,1,2,1,2,3,1,1,2,3,4]

-- useful helper function:
insertWithAndGet :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> (a, Map k a)
insertWithAndGet f k v m = (newValue, M.insert k newValue m)
  where newValue = maybe v (f v) $ M.lookup k m


-- using foldl
-- laziness not preserved because of foldl
count :: Ord a => [a] -> [Int]
count = reverse . snd . foldl f (M.empty, [])
  where
    f (m, ns) x = (newMap, n:ns)
      where (n, newMap) = insertWithAndGet (+) x 1 m


-- explicit recursion
count' :: Ord a => [a] -> [Int]
count' = go M.empty
  where
    go _ [] = []
    go m (x:xs) = n : go newMap xs
      where (n, newMap) = insertWithAndGet (+) x 1 m


-- abstracting over the recursion
someFold :: (x -> acc -> (n, acc)) -> acc -> [x] -> [n]
someFold _ _ [] = []
someFold f acc (x:xs) = n : someFold f newAcc xs
  where
    (n, newAcc) = f x acc

count'' :: Ord a => [a] -> [Int]
count'' = someFold (\x -> insertWithAndGet (+) x 1) M.empty


-- using the predefined mapAccumL
count''' :: Ord a => [a] -> [Int]
count''' = snd . mapAccumL (\m x -> swap $ insertWithAndGet (+) x 1 m) M.empty