如何将基于Map的列表元素出现次数统计函数改写为使用foldr实现

当然可以！用foldr来实现元素出现次数统计完全可行，而且思路很直观——本质上就是用折叠操作一步步构建一个记录频次的结构。先给你提个小细节：你原来的类型签名有点小问题哦，应该写成occur :: (Ord a) => [a] -> Map a Int，毕竟我们统计的是出现次数，值的类型是整数，不是和键一样的类型~

完全替代Map的foldr实现（基于列表） #

如果你想彻底不用Map，我们可以直接用键值对列表来存储频次，通过foldr遍历每个元素并更新这个列表：

occur :: Eq a => [a] -> [(a, Int)]
occur = foldr updateCounts []
  where
    updateCounts x [] = [(x, 1)]
    updateCounts x ((k, v):rest)
      | x == k    = (k, v + 1):rest
      | otherwise = (k, v):updateCounts x rest

代码解释： #

• foldr updateCounts [] 表示从右往左遍历输入列表，用updateCounts函数把每个元素合并到初始为空的频次列表中。
• updateCounts函数负责处理单个元素和当前频次列表：
  • 如果频次列表是空的，直接把当前元素和次数1组成键值对加入列表；
  • 如果列表不为空，检查第一个键值对的键是否和当前元素相等：
    • 相等的话，就把该键的次数加1，剩下的列表保持不变；
    • 不相等的话，先保留第一个键值对，再递归处理剩下的列表，直到找到匹配的键或者遍历完列表。

测试一下你给的例子：

• 输入[1,1,2,3,3]，输出是[(1,2),(2,1),(3,2)]；
• 输入[1,2,1,1]，输出是[(1,3),(2,1)]，和你原来的Map版本结果一致。

这个版本的类型约束是Eq a（只需要元素能判断相等），不需要Ord a，但缺点是对于大列表来说，每次查找匹配键都是线性遍历，效率不如Map。

结合Map的高效foldr实现 #

如果你只是想用foldr重构原来的逻辑（保留Map的高效性），可以用foldr结合Map的insertWith函数，写法更简洁：

import qualified Data.Map as Map
import Data.Map (Map)

occur :: Ord a => [a] -> Map a Int
occur = foldr (\x -> Map.insertWith (+) x 1) Map.empty

代码解释： #

• foldr遍历每个元素x，把x传给Map.insertWith (+) x 1这个函数——它会将x插入到Map中，如果x已经存在，就把对应的次数加1；
• 初始值是Map.empty（空Map）。

这个版本和你原来的fromListWith (+)实现本质是等价的，因为fromListWith内部其实也是通过折叠来构建Map的，只是这个写法更明确地用了foldr。

内容的提问来源于stack exchange，提问作者m.18