折叠列表并计算任意多个唯一和未知实体的所有出现次数

Question

我正在使用 Control.Foldl 库来遍历任意长的列表并计算任意多个唯一实体的所有出现次数。即，列表可能是

形式

[Just "a", Just "b", Just "aab", Nothing, Just "aab"]

我的结果应该是

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

现在的问题是我没有先验的这些实体的名称，我想在折叠时动态更新结果。

我的问题是我不知道如何根据 foldl 中的 Fold a b 数据类型来描述此计算。具体来说，在折叠的每一步我都需要遍历结果列表并询问我是否看到了当前项目，但我看不到使用 foldl.

来描述它的方式

Answer 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 被急切求值，而不是存储为 thunk。

Answer 2

考虑按相等性对排序列表进行分组，然后应用 lambda 函数计算出现次数，

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)]

Answer 3

怎么样：

λ> :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)

Answer 4

除了其他答案，我还想提请您注意 monoids. It's an abstraction for combining a sequence of elements (including 0-length) using an associative 操作的概念。

在这种情况下，幺半群将是元素到数字（它们的计数）的映射，空元素是空映射，合并操作合并两个映射，对两个映射中存在的键的值求和。

{-# Language DerivingVia        #-}
{-# Language DerivingStrategies #-}

import Data.Foldable
import qualified Data.Map as M
import Data.Monoid
-- https://hackage.haskell.org/package/monoidal-containers
import Data.Map.Monoidal

newtype CountMap k = CountMap { getCountMap :: M.Map k Int }
  -- (<>)   = M.unionWith (+)
  -- mempty = M.empty
  deriving (Semigroup, Monoid)
  via MonoidalMap k (Sum Int)

  deriving
  stock (Eq, Ord, Show, Read)

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

虽然使用幺半群描述的解决方案不一定是最短的解决方案，但它们通常比折叠更清晰、更高层次地表达了主要思想。

同样对于列表以外的结构，例如树，使用幺半群组合元素更自然（在某些情况下更有效）：每个叶子都转换为它在幺半群中的对应值，然后将值组合到底部向上。

另见 Monoids and Finger Trees。

折叠列表并计算任意多个唯一和未知实体的所有出现次数

Folding over a list and counting all occurrences of arbitrarily many unique and unknown entities

haskell

fold