accumArray 学习笔记

2025-09-12 00:00    #haskell  

Haskell accumArray 学习笔记

核心概念 accumArray 是一个高效的数组构建函数，它的本质是 “分桶”与“归并”。它将列表中的数据按照索引（Index）放入对应的“桶”中，如果在同一个桶中遇到多个数据，则根据指定的规则进行合并。

函数签名速记

1accumArray :: (e -> a -> e) -> e -> (i, i) -> [(i, a)] -> Array i e

你可以把它看作由 4 个关键参数 组成：

  1. 怎么合 (Function)：冲突处理规则。当新数据进入已有数据的桶时，如何运算（如 (+), max, flip (:)）。
  2. 初始值 (Initial)：每个桶的默认状态（如 0, 1, []）。这也解决了稀疏数组的问题。
  3. 范围 (Bounds)：数组下标的起止范围（如 (1, 10)）。
  4. 数据源 (List)：待处理的 (索引, 值) 列表。

常用模式

  1. 统计/累加 用于直方图统计或求和。

    • 规则：(+)
    • 初始值：0

  2. 分组/收集 (Group By) 将同一索引的数据收集到一个列表中。

    • 规则：flip (:)
      • 注意：使用 flip 是因为 accumArray 传参顺序是 (旧值 -> 新值 -> 结果)，而 (:) 默认是 (新值 -> 旧值 -> 结果)。
    • 初始值：[] (或 "")
    • 特性：由于 (:) 是将元素加到头部，结果通常是倒序的（LIFO），如需正序通常配合 fmap reverse 使用。

例子1:将字符按索引分组

实战示例

 1-- 目标：将字符按索引分组
 2-- 输入：[(1, 'a'), (2, 'b'), (1, 'c')]
 3-- 范围：(1, 2)
 4
 5import Data.Array
 6
 7-- 构建数组
 8-- 1号桶过程：初始 "" -> 放入 'a' 变 "a" -> 放入 'c' 变 "ca"
 9let arr = accumArray (flip (:)) "" (1, 2) [(1, 'a'), (2, 'b'), (1, 'c')]
10
11-- 结果：array (1,2) [(1, "ca"), (2, "b")]
12
13-- 如果需要正序，可以对结果应用 reverse
14let finalArr = fmap reverse arr
15-- 最终结果：array (1,2) [(1, "ac"), (2, "b")]

例子2 : 数值累加

实战示例：统计各队总分 🏆

假设我们正在举行一场比赛，有 3 支队伍（编号 1, 2, 3）。数据源是一张记录表，上面记录了每次得分的队伍和分数。

我们需要计算：每支队伍的最终总分是多少？

 1import Data.Array
 2
 3-- 1. 数据准备
 4-- 格式：[(队伍编号, 单次得分)]
 5scores = [(1, 10), (2, 5), (1, 20), (3, 8), (2, 10)]
 6
 7-- 2. 构建数组
 8-- 核心逻辑：遇到相同索引，就做加法 (+)
 9-- 初始值：0 (因为还没得分时是 0)
10-- 范围：(1, 3) (代表 3 支队伍)
11
12let totalScores = accumArray (+) 0 (1, 3) scores
13
14-- 3. 运行过程解析：
15-- 1号队：0 + 10 + 20 = 30
16-- 2号队：0 + 5 + 10 = 15
17-- 3号队：0 + 8      = 8
18
19-- 最终结果：
20-- array (1,3) [(1,30), (2,15), (3,8)]

例子3: 计数

 1
 2import Data.Array
 3
 4-- 1. 原始数据
 5-- 假设这是几次掷骰子的结果，或者投票箱里的票
 6rawData = [1, 3, 1, 2, 1, 3]
 7
 8-- 2. 数据转换 (关键步骤)
 9-- 将每个数字 x 映射为 (x, 1)
10-- 含义：数字 x 每出现一次，就贡献计数值 1
11mappedData = [ (x, 1) | x <- rawData ]
12-- 转换结果：[(1, 1), (3, 1), (1, 1), (2, 1), (1, 1), (3, 1)]
13
14-- 3. 构建数组
15-- 规则：(+) 用加法累积次数
16-- 初始：0
17-- 范围：(1, 3) 假设数据只包含 1 到 3
18let frequency = accumArray (+) 0 (1, 3) mappedData
19
20-- 4. 运行结果解析：
21-- 1号桶：1 + 1 + 1 = 3 次
22-- 2号桶：1         = 1 次
23-- 3号桶：1 + 1     = 2 次
24
25-- 最终结果：
26-- array (1,3) [(1,3), (2,1), (3,2)]