Roc 语言 List.drop_swap 详解:O(1) 交换删除语义与 REPL 快照验证
Roc 语言 List.drop_swap 详解:O(1) 交换删除语义与 REPL 快照验证
List.drop_swap 是 Roc 标准库 List 模块中一个典型的"交换删除"(swap-remove)操作:它删除指定索引处的元素,但把最后一个元素移动到被删位置,因此不保持剩余元素的原有顺序。本文以仓库中 REPL 快照测试 为骨架,逐条解读其边界行为,并深入到 Builtin.roc 的源码实现,说明它为什么是 O(1)、为什么与 drop_at 语义不同,以及 Roc 如何用快照测试固化这类语言级行为。
一、drop_swap 是什么:交换删除(swap-remove)语义
在大多数编程语言的标准库中,"按索引删除元素"有两种实现策略:
- 平移删除(shift):把被删元素之后的所有元素依次前移一位,保持相对顺序,但平均开销为 O(n);
- 交换删除(swap-remove):把最后一个元素直接覆盖到被删位置,再收缩长度,只需 O(1),但剩余元素的顺序被破坏。
List.drop_swap 属于后者。在 Builtin.roc 中,其声明与文档注释给出了权威定义:
## Removes the item at the given index by moving the last item into its
## place, so the order of the remaining items is not preserved. This is O(1),
## unlike `drop_at`, which shifts every later item down.
##
## Returns the list unchanged if the index is out of bounds.
## ```roc
## expect [1.I64, 2, 3, 4].drop_swap(1) == [1, 4, 3]
## ```
drop_swap : List(a), U64 -> List(a)
核心要点有三:
- 删除指定索引元素,末位元素补位,顺序不保证;
- 复杂度 O(1),与需要平移后续元素的
drop_at(见 Builtin.roc)形成鲜明对比; - 索引越界时返回原列表,不做任何修改。
二、从 REPL 快照逐条读懂 drop_swap 的完整行为
list_drop_swap.md 是一个 type=repl 的 REPL 快照文件,其 # SOURCE 段记录了 5 条交互输入,# OUTPUT 段给出了对应的求值结果。下面逐条解读。
场景一:删除中间元素
» [1.I64, 2, 3, 4, 5].drop_swap(1)
[1, 5, 3, 4]
删除索引 1 处的元素 2,最后一个元素 5 被移动到索引 1,随后末尾被裁剪。注意结果中的元素顺序变为 [1, 5, 3, 4]:5 顶替了原来 2 的位置,而 3、4 保持原位——这正是"顺序不保留"的直观体现。如果使用 drop_at,结果会是保持顺序的 [1, 3, 4, 5]。
场景二:删除最后一个元素
» [1.I64, 2, 3].drop_swap(2)
[1, 2]
当被删索引恰好是最后一个元素(索引 2 即长度 3 的末位)时,交换操作把末位元素与自身交换,再裁剪一位,等价于直接去掉末尾元素,结果 [1, 2],此时与 drop_at 行为一致。
场景三:越界索引返回原列表
» [1.I64, 2, 3].drop_swap(9)
[1, 2, 3]
索引 9 远超列表长度 3。按照文档约定,drop_swap 越界时原样返回列表,不做任何修改,也不会抛错。这与 list_get、list_set 等需要 Try 包装的访问操作不同,是一个静默的"无害操作"。
场景四:对堆分配字符串列表的交换删除
» heap = ["one long heap-allocated string that will not fit inline", "two long heap-allocated string that will not fit inline", "three long heap-allocated string that will not fit inline"]
assigned `heap`
这里刻意构造了一个元素为长字符串的列表。Roc 对短字符串有"内联(inline)"优化(小字符串直接存放在值内,无需堆分配),而这三个字符串过长、无法内联,因此每个元素都是堆分配的,用于验证 drop_swap 在涉及堆分配数据时同样正确工作。
» heap.drop_swap(0)
["three long heap-allocated string that will not fit inline", "two long heap-allocated string that will not fit inline"]
删除索引 0 处的第一个字符串,第三个(最后一个)字符串被移动到索引 0,结果仅剩两个元素,且 three... 排在了最前面——交换删除的顺序破坏在此体现得更加明显。
场景五:原列表保持不变(不可变语义)
» heap
["one long heap-allocated string that will not fit inline", "two long heap-allocated string that will not fit inline", "three long heap-allocated string that will not fit inline"]
在调用 heap.drop_swap(0) 之后再次求值 heap,得到的是完整的三元素原列表。这说明 drop_swap 与其他 List 函数一样遵循函数式语言的不可变语义:它返回一个新列表,而不会原地修改调用者。这也是快照测试中特意安排这两条连续指令的原因——既展示交换删除的结果,又验证原列表未被污染。
三、源码级实现:为什么它是 O(1)
在 Builtin.roc 中,drop_swap 的实现只有短短几行:
drop_swap = |list, index| {
len = List.len(list)
if index < len {
List.drop_last(list_swap_unsafe(list, index, len - 1), 1)
} else {
list
}
}
整个算法由三个原子步骤组成:
- 边界检查:
if index < len先判断索引是否在界内,越界直接返回原列表list(对应场景三); - 交换:
list_swap_unsafe(list, index, len - 1)将被删索引index与末位索引len - 1的元素互换。list_swap_unsafe在 Builtin.roc 中声明为"由编译器实现、不执行边界检查"的底层原语:
正因为外层已经用# Implemented by the compiler, does not perform bounds checks list_swap_unsafe : List(item), U64, U64 -> List(item)index < len保证了index与len - 1都在界内,这里才能安全地使用_unsafe变体换取性能; - 裁剪末尾:
List.drop_last(..., 1)删除交换后的最后一个元素。drop_last(见 Builtin.roc)从末尾去掉 n 个元素,此处n = 1正好移除被换到末尾的原目标元素。
从实现可以推断:整个操作不涉及任何逐元素平移,固定为"一次边界比较 + 一次原地交换 + 一次尾部裁剪",因此无论列表多长都是常数时间操作,即文档注释所强调的 O(1)。
顺带一提,list_swap_unsafe 并不只服务于 drop_swap。例如 Builtin.roc 中 List.swap(交换任意两个索引的元素)也复用了它;而有序删除 drop_at 由于需要维持相对顺序、逐个前移后续元素,代价是 O(n)。两者适用场景不同:需要保持顺序用 drop_at,追求常数时间且不在意顺序(如实现集合、去重、批量清理)用 drop_swap。
四、快照测试机制:Roc 如何固化语言级行为
list_drop_swap.md 属于 Roc 仓库的 REPL 快照测试体系,文件采用四个固定小节组织:
| 小节 | 作用 | 本文件内容 |
|---|---|---|
# META |
元信息(ini 格式) | description=List.drop_swap removes an element by swapping it with the last one、type=repl |
# SOURCE |
REPL 输入(以 » 提示符开头) |
上述 5 条指令 |
# OUTPUT |
期望输出,指令间以 --- 分隔 |
5 段求值结果 |
# PROBLEMS |
诊断/编译问题列表 | NIL(无问题) |
type=repl 表明该快照会启动 REPL 逐条执行 # SOURCE 中的命令,并把实际输出与 # OUTPUT 逐段比对。整个快照测试由 src/snapshot_tool/main.zig 驱动,其 CLI 入口提供了几个关键选项(见该文件 --help 文本):
roc snapshot [options] [snapshot_paths...]:运行指定快照文件或目录;--check-expected:校验EXPECTED/OUTPUT段与实际输出一致;--update-expected:用实际输出更新期望段;--trace-eval:输出解释器跟踪信息(仅适用于单个 REPL 快照)。
因此,list_drop_swap.md 不仅是一份文档,更是一份可自动执行的回归测试:任何对 drop_swap 实现(或 REPL 求值、输出格式化)的改动,只要偏离上述 5 段期望输出,快照校验就会失败,从而把"交换删除的语义细节"固化为语言级契约。
五、底层测试佐证:零大小列表的容量行为
除了 REPL 快照,drop_swap 还有专门的底层(low-level)评估测试。src/eval/test/eval_low_level_tests.zig 中的用例 low_level - zero-sized list drop_swap reports zero capacity 验证了极端情况:
.name = "low_level - zero-sized list drop_swap reports zero capacity",
.source =
\\{
\\x : List({})
\\x = [{}, {}, {}]
\\r = List.drop_swap(x, 0)
\\(List.len(r), List.capacity(r))
\\}
,
.expected = .{ .inspect_str = "(2, 0)" },
该用例使用元素类型为 {}(零大小类型)的列表执行 drop_swap(x, 0),期望结果是 (2, 0)——即新列表长度为 2,容量为 0。这验证了两件事:
- 对零大小元素,编译器可以完全不分配存储空间(容量为 0 是合法的);
- 交换删除后容量语义与
drop_at、drop_first等删除族操作保持一致(同文件紧邻的多个用例均断言了同样的(2, 0)行为)。
这从求值器层面补充确认了 drop_swap 与其它 List 删除函数在底层表示上的一致性。
六、相关函数与延伸阅读
drop_swap 位于 List 删除/子集操作族中,读者可在 src/build/roc/Builtin.roc 的 List 模块内对照阅读:
drop_at:按索引删除但保持顺序,O(n),Builtin.roc;drop_first/drop_last:从头部/尾部批量删除,Builtin.roc;List.swap:交换任意两个索引的元素,同样是 O(1),其 REPL 快照见 list_swap.md、list_swap_oob.md、list_swap_same_index.md;drop_if:按谓词条件删除,快照见 list_drop_if.md。
同一目录 test/snapshots/repl/ 下还有 list_drop_first、list_drop_last 等系列快照,可作为理解 Roc List API 语义与快照测试格式的完整素材。若想亲自复现本文的全部行为,可在仓库根目录构建 roc 可执行文件(参考 BUILDING_FROM_SOURCE.md),然后以 REPL 模式逐条输入本文 # SOURCE 段的指令,观察输出是否与快照一致。