Цикл по списку и добавление в кортеж

Question

Я пытаюсь создать функцию, которая перебирает массив строк, добавляет слово в новый кортеж, который подсчитывает, сколько раз слово встречается в блоке текста.На языке OO это просто - создайте пару KV для каждого слова и сколько раз оно встречается.Я пытаюсь перевести этот код на Haskell, но не думаю, что это так просто.

countWords:: [String] -> [(String, Int)]

Я знаю, что мне нужно создать список кортежей, но я не уверен, как перебрать список, переданный функции с помощью рекурсии.

Answer 1

Довольно прямым переводом того, что вы, по-видимому, говорите, что будете делать в ОО, будет рекурсивное «зацикливание» для каждого слова в списке и либо обновление уже имеющейся записи, либо добавление ее как новой:

registerWord :: String -> [(String, Int)] -> [(String, Int)]
registerWord w ((w',c):ws)
    | w==w'       = (w,c+1) : ws
    | otherwise   = (w',c) : registerWord w ws
registerWord w [] = [(w,1)]

Затем делайте это для каждого слова, каждый раз обновляя регистр.Это легко сделать с помощью сгиба:

countWords :: [String] -> [(String, Int)]
countWords = foldr registerWord []

Эта вставка списка неудобна и неэффективна (как в FP, так и в OO), а именно O ( n ² ).Гораздо более приятным подходом является функционально-модульное мышление: вы фактически хотите сгруппировать одинаковые слова вместе.Для этого вам нужно сначала отсортировать их, чтобы равные слова фактически были смежными.Затем вам нужно заменить каждую группу дубликатов одним примером и количеством.Хороший функциональный конвейер:

countWords :: [String] -> [(String, Int)]
countWords = map (\gp@(w:_) -> (w, length gp)) . group . sort

Кстати, в этой функции нет ничего, что требовало бы, чтобы ключи были «словами» / строками, так что вы могли бы также обобщить сигнатуру до

countWords :: Ord a => [a] -> [(a, Int)]

(Другой, неэффективный подход будет еще более общим, требующим только Eq.)