不使用Data.Map，用Haskell创建纯函数式频率映射的惯用方法？

你的思路很有意思——完全用函数而非Data.Map来实现频率映射。原实现的递归逻辑是可行的，但确实可以借助Haskell的高阶函数特性来简化代码，同时保持纯函数的本质。

优化后的简洁实现 #

利用foldr（列表右折叠）可以直接构建这个频率函数，无需显式定义辅助递归函数：

frequencyMap :: Eq a => [a] -> a -> Int
frequencyMap = foldr (\x freqFn -> \y -> if y == x then 1 + freqFn y else freqFn y) (const 0)

代码解释 #

• foldr会遍历列表中的每个元素x，逐步累积出最终的频率函数：
  1. 初始累积值是const 0——对任何输入都返回0的函数，对应空列表的频率映射。
  2. 每处理一个元素x，就把当前的累积函数freqFn包装成一个新函数：当输入y等于x时，返回1 + freqFn y（在原有计数上加1）；否则直接调用freqFn y。

这种写法完全延续了你原实现的逻辑，但借助foldr消除了冗余的辅助函数，代码更紧凑、符合函数式编程的风格。

关于性能的说明 #

需要注意的是，这种纯函数式的频率映射本质上是一个闭包链，每次查询都需要遍历整个闭包链（对应原列表的长度），时间复杂度为O(n)。如果需要更高效的查询，还是得依赖Data.Map这类基于树或哈希表的结构，但如果你的场景对查询性能要求不高，这种纯函数实现的简洁性和无副作用特性会很有优势。

内容的提问来源于stack exchange，提问作者Kosmas Xenakis