Haskell新手技术问题：仅用比较运算符实现列表元素频率统计

手动实现列表频率统计（无Data.Map依赖） #

嘿，作为Haskell新手，你能写出基于Data.Map的版本已经很赞了！如果要完全避开预定义的Map相关函数，咱们可以借助排序+递归统计的思路来实现，全程只用到比较运算符和基础递归，完全符合你的要求。

核心思路 #

1. 先排序：把列表中相同的元素集中到一起，这样后续统计只需要遍历一次，逐个累加连续相同元素的次数。这里我们用基于比较运算符的插入排序来实现（逻辑简单，适合新手理解）。
2. 递归统计：遍历排序后的列表，维护当前元素的计数，遇到不同元素时就把已统计好的键值对存入结果，再继续处理剩余列表。

完整实现代码 #

-- 插入排序：仅用比较运算符实现，将列表按升序排列
insertSort :: Ord a => [a] -> [a]
insertSort [] = []
insertSort (x:xs) = insert x (insertSort xs)
  where
    insert x [] = [x]
    insert x (y:ys)
      | x <= y    = x : y : ys
      | otherwise = y : insert x ys

-- 统计排序后列表的元素频率
countSorted :: Eq a => [a] -> [(a, Int)]
countSorted [] = []
countSorted (x:xs) = countHelper x 1 xs
  where
    countHelper current count [] = [(current, count)]
    countHelper current count (y:ys)
      | y == current = countHelper current (count + 1) ys
      | otherwise    = (current, count) : countHelper y 1 ys

-- 最终的频率统计函数：先排序，再统计
frequency :: Ord a => [a] -> [(a, Int)]
frequency = countSorted . insertSort

测试验证 #

输入你的示例列表：

frequency [0,2,2,0,2,5,0,2]

输出结果：

[(0,3),(2,4),(5,1)]

完全符合你的预期！

代码解释 #

• insertSort：递归实现插入排序，每次将当前元素插入到已排序列表的正确位置，全程只用了<=比较运算符。
• countSorted：接收已排序的列表，用辅助函数countHelper维护当前元素和它的计数。当遇到相同元素时计数加1，遇到不同元素则把当前统计结果加入列表，再切换到新元素继续统计。这里只用了==比较运算符。
• frequency：组合排序和统计函数，先对输入列表排序，再统计频率。

这样实现完全没有依赖Data.Map的任何预定义函数，只用到了基础的比较运算符和递归，非常适合新手理解Haskell的核心逻辑。

内容的提问来源于stack exchange，提问作者Amrita Deb