Сворачивание списка и подсчет всех вхождений произвольного количества уникальных и неизвестных сущностей

В дополнение к другим ответам я хотел бы обратить ваше внимание на концепцию моноидов. Это абстракция для объединения последовательности элементов (в том числе нулевой длины) с помощью ассоциативной операции.

В этом случае моноид будет картой элементов в числа (их количество), при этом пустой элемент будет пустой картой, а операция объединения объединяет две карты, суммируя значения ключей, присутствующих в обеих.

import Data.Foldable
import qualified Data.Map as M
import Data.Monoid

newtype CountMap k = CountMap { getCountMap :: M.Map k Int }
  deriving (Eq, Ord, Show, Read)

instance (Ord k) => Monoid (CountMap k) where
    mempty = CountMap M.empty
    mappend (CountMap m1) (CountMap m2) = CountMap $ M.unionWith (+) m1 m2

singleton :: k -> CountMap k
singleton x = CountMap $ M.singleton x 1

unique :: (Foldable f, Ord k) => f k -> [(k, Int)]
unique = M.toList . getCountMap . foldMap singleton

Хотя решения, описанные с помощью моноидов, не обязательно являются самыми короткими, они часто выражают основную идею более четко и на более высоком уровне, чем складки.

Также для структур, отличных от списков, например для деревьев, объединение элементов с помощью моноидов более естественно (и в некоторых случаях более эффективно): каждый лист преобразуется в соответствующее значение в моноиде, а затем значения объединяются снизу вверх.

См. также Моноиды и деревья пальцев.

Что о:

λ> :set -XTupleSections
λ> import qualified Data.Map.Strict as Map
λ> Map.fromListWith (+) $ fmap (,1) [Just "a", Just "b", Just "aab", Nothing, Just "aab"]
fromList [(Nothing,1),(Just "a",1),(Just "aab",2),(Just "b",1)]

мы просто сопоставляем список, чтобы сформировать пару (x,1), а затем используем fromListWith для создания Map.

countOccurences :: (Num a, Ord k) => [k] -> Map.Map k a
countOccurences = Map.fromListWith (+) . fmap (,1)

Сгиб позволяет вам перемещаться по списку, отслеживая некоторое состояние. В этом случае состояние, которое вы хотите сохранить, — это текущий список счетчиков каждой строки, просмотренной до сих пор.

Давайте смоделируем это состояние как Map String Int, где Map происходит от Data.Map.Strict.

Если m — это наше текущее состояние, мы можем выполнить следующие операции:

findWithDefault 0 str m -- returns the count for string str
                           returns 0 if the string isn't found

insert str count m      -- insert the tuple (str,count) into the map
                           (replaces previous value at key str)

empty                   -- the empty map

С этими операциями наша ступенчатая функция для сгиба может выглядеть так:

step :: Map String Int -> String -> Map String Int
step m str =
  let count = findWithDefault 0 str m
      m' = insert str (count+1) m
  in m'

Полная складка это:

countStrings :: [String] -> Map String Int
countStrings strs = foldl step empty strs

Обратите внимание, что здесь важно использовать Data.Map.Strict. Вы хотите, чтобы count+1 оценивалось с готовностью, а не сохранялось как преобразователь.

Попробуйте сгруппировать отсортированный список по равенству, а затем применить лямбда-функцию для подсчета вхождений,

import Data.List

entryCount :: Ord a => [a] -> [(a,Int)]
entryCount = map (\v -> (head v, length v)) . groupBy (==) . sort

Следовательно

entryCount [Just "a", Just "b", Just "aab", Nothing, Just "aab"]
[(Nothing,1),(Just "a",1),(Just "aab",2),(Just "b",1)]